Maximizing the Differences Between a Monotone DR-Submodular Function and a Linear Function on the Integer Lattice

In this paper,we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular(DR-submodular)function and a nonnegative linear function on the integer lattice.As it is almost unapproximable for maximizing a submodular function without the condition of nonnegative,we provide weak(bifactor)approximation algorithms for this problem in two online settings,respectively.For the unconstrained online model,we combine the ideas of single-threshold greedy,binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation ratio.For the online streaming model subject to a cardinality constraint,we provide a one-pass(3-√5)/2 weak approximation ratio streaming algorithm.Its memory complexity is(k log k/ε),and the update time for per element is(log^(2)k/ε).

Pricing Decisions in Dual-Channel Closed-Loop Supply Chain Under Retailer’s Risk Aversion and Fairness Concerns

This paper studies the price decisions in a dual-channel closed-loop supply chain with a risk-averse retailer and a risk-neutral manufacturer by modeling and analyzing three cases:(1)the retailer does not have fairness concerns;(2)the retailer has fairness concerns and the manufacturer considers it;and(3)the retailer has fairness concerns and the manufacturer does not consider it.The effects of risk aversion and fairness concerns on the pricing decisions,profits and demand are examined in differing scenarios.

A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

In this paper,we consider the generalized prize-collecting Steiner forest problem,extending the prize-collecting Steiner forest problem.In this problem,we are given a connected graph G=(V,E)and a set of vertex sets V={V1,V2,…,Vl}.Every edge in E has a nonnegative cost,and every vertex set in V has a nonnegative penalty cost.For a given edge set F⊆E,vertex set Vi∈V is said to be connected by edge set F if Vi is in a connected component of the F-spanned subgraph.The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized.Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors

In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.

A Note on Submodularity Preserved Involving the Rank Functions

In many kinds of games with economic significance,it is very important to study the submodularity of functions.In this paper,wemainly study the problem of maximizing a concave function over an intersection of two matroids.We obtain that the submod-ularity may not be preserved,but it involves one maximal submodular problem(or minimal supermodular problem)with some conditions.Moreover,we also present examples showing that these conditions can be satisfied.

Simultaneous Approximation of Multi-criteria Submodular Function Maximization

Recently intensive interest has been raised on approximation of the NPhard submodular maximization problem due to their theoretical and practical significance.In this work,we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization.We address the existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric,respectively,along with algorithmic corollaries.We offer complete characterization of the symmetric case and partial results on the asymmetric case.

An Almost Tight Lower Bound for the Scheduling Problem to Meet Two Min-Sum Objectives

In this note,we provide an almost tight lower bound for the scheduling problem to meet two min-sum objectives considered by Angel et al.in Oper.Res.Lett.35(1):69–73,2007.

Local search yields a PTAS for fixed-dimensional k-means problem with penalties

We study a problem called the k-means problem with penalties(k-MPWP),which is a natural generalization of the typical k-means problem.In this problem,we have a set D of client points in R^(d),a set F of possible centers in R^(d),and a penalty cost Pj>O for each point j∈D.We are also given an integer k which is the size of the center point set.We want to find a center point set S■F with size k,choose a penalized subset of clients P■D,and assign every client in D\P to its open center.Our goal is to minimize the sum of the squared distances between every point in D\P to its assigned centre point and the sum of the penalty costs for all clients in P.By using the multi-swap local search technique and under the fixed-dimensional Euclidean space setting,we present a polynomial-time approximation scheme(PTAS)for the k-MPWP.