Approximation Algorithms for the Priority Facility Location Problem with Penalties

develop a mentation This paper considers the priority facility primal-dual 3-approximation algorithm for procedure, the authors further improve the location problem with penalties： The authors this problem. Combining with the greedy aug- previous ratio 3 to 1.8526.

Bicriteria Approximation Algorithm for Quarantining-vaccination-cure Problem

In this paper, we propose a model for the epidemic control problem, the goal of which is to minimize the total cost of quarantining, vaccination and cure under the constraint on the maximum number of infected people allowed. A (1+ε+ε3 , 1+ ε+1/ε )- bicriteria approximation algorithm is given.

An Approximation Algorithm for the Common Due Date Scheduling Problem

In this paper,attention is paid to study an algorithm for the common due datetotal weighted tardiness problem of single machine scheduling. Anapproximation alsorithm is given. It performs well in the sense of worst-casebehaviour and its worst-case performance ratio is 2.

Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs

The connected dominating set （CDS） problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs （UDGs）. This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set （IS） in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones.

An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties

In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties.In this problem,we are given m dedicated machines in parallel and n customer orders.Each order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated machine.An order is either rejected,in which case a rejection penalty has to be paid,or accepted and manufactured on the m dedicated machines.The objective is to find a solution to minimize the sum of the maximum delivery completion time of the accepted orders and the penalty of the rejected orders which is determined by a submodular function.We design an LP rounding algorithm with approximation ratio of n+1 for this problem.

Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem

We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)problem.Specifically,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner trees.Similarly,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)problem.In addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)problem.We obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.

An Approximation Algorithm Based on Seeding Algorithm for Fuzzy k-Means Problem with Penalties

As a classic NP-hard problem in machine learning and computational geometry,the k-means problem aims to partition the given dataset into k clusters according to the minimal squared Euclidean distance.Different from k-means problem and most of its variants,fuzzy k-means problem belongs to the soft clustering problem,where each given data point has relationship to every center point.Compared to fuzzy k-means problem,fuzzy k-means problem with penalties allows that some data points need not be clustered instead of being paid penalties.In this paper,we propose an O(αk In k)-approximation algorithm based on seeding algorithm for fuzzy k-means problem with penalties,whereαinvolves the ratio of the maximal penalty value to the minimal one.Furthermore,we implement numerical experiments to show the effectiveness of our algorithm.

Approximation Algorithm for Weighted Weak Vertex Cover

The problem of efficiently monitoring the network flow is regarded as the problem to find out the minimum weighted weak vertex cover set for a given graphG=(V,E). In this paper, we give an approximation algorithm to solve it, which has the approximation ratio lnd+1, whered is the maximum degree of the vertex in graphG, and improve the previous work. Keywords weak vertex cover - NP-hard - approximation algorithm NoteThis work is supported by the Ministry of Science and Technology of China (Grant No.2001CCA03000), the National Natural Science Foundation of China (Grant No.60273045), and the Shanghai Science and Technology Development Foundation (Grant No.025115032).

Exact and Approximation Algorithms for the Multi-Depot Capacitated Arc Routing Problems

In this work,we investigate a generalization of the classical capacitated arc routing problem,called the Multi-depot Capacitated Arc Routing Problem(MCARP).We give exact and approximation algorithms for different variants of the MCARP.First,we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination version.Second,for the multi-depot rural postman problem,i.e.,a special case of the MCARP where the vehicles have infinite capacity,we develop a(2-1/2k+1)-approximation algorithm(k denotes the number of depots).Third,we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.Lastly,we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.

Approximation Algorithm for Bottleneck Steiner Tree Problem in the Euclidean Plane

A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.

APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.

An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance

We consider the design of semidefinite programming （SDP） based approximation algorithm for the problem Max Hypergraph Cut with Limited Unbalance （MHC-LU）： Find a partition of the vertices of a weighted hypergraph H = （V, E） into two subsets V1, V2 with ｜｜V2｜ - ｜1/1 ｜｜ ≤ u for some given u and maximizing the total weight of the edges meeting both V1 and V2. The problem MHC-LU generalizes several other combinatorial optimization problems including Max Cut, Max Cut with Limited Unbalance （MC-LU）, Max Set Splitting, Max Ek-Set Splitting and Max Hypergraph Bisection. By generalizing several earlier ideas, we present an SDP randomized approximation algorithm for MHC-LU with guaranteed worst-case performance ratios for various unbalance parameters τ = u/｜V｜. We also give the worst-case performance ratio of the SDP-algorithm for approximating MHC-LU regardless of the value of τ. Our strengthened SDP relaxation and rounding method improve a result of Ageev and Sviridenko （2000） on Max Hypergraph Bisection （MHC-LU with u = 0）, and results of Andersson and Engebretsen （1999）, Gaur and Krishnamurti （2001） and Zhang et al. （2004） on Max Set Splitting （MHC-LU with u = ｜V｜）. Furthermore, our new formula for the performance ratio by a tighter analysis compared with that in Galbiati and Maffioli （2007） is responsible for the improvement of a result of Galbiati and Maffioli （2007） on MC-LU for some range of τ.

Approximation Algorithms for Discrete Polynomial Optimization

In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks,error-correcting codes,among many others.In particular,we focus on three types of optimization models:(1)maximizing a homogeneous polynomial function in binary variables;(2)maximizing a homogeneous polynomial function in binary variables,mixed with variables under spherical constraints;(3)maximizing an inhomogeneous polynomial function in binary variables.We propose polynomial-time randomized approximation algorithms for such polynomial optimizationmodels,and establish the approximation ratios(or relative approximation ratios whenever appropriate)for the proposed algorithms.Some examples of applications for these models and algorithms are discussed as well.

A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

In this paper,we consider the-prize-collecting minimum vertex cover problem with submodular penalties,which generalizes the well-known minimum vertex cover problem,minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties.We are given a cost graph and an integer.This problem determines a vertex set such that covers at least edges.The objective is to minimize the total cost of the vertices in plus the penalty of the uncovered edge set,where the penalty is determined by a submodular function.We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem.When the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor of.When the submodular penalty cost function is linear,the approximation factor of the proposed algorithm is reduced to,which is the best factor if the unique game conjecture holds.

Asymptotic optimality for consensus-type stochastic approximation algorithms using iterate averaging

This paper introduces a post-iteration averaging algorithm to achieve asymptotic optimality in convergence rates of stochastic approximation algorithms for consensus control with structural constraints. The algorithm involves two stages. The first stage is a coarse approximation obtained using a sequence of large stepsizes. Then, the second stage provides a refinement by averaging the iterates from the first stage. We show that the new algorithm is asymptotically efficient and gives the optimal convergence rates in the sense of the best scaling factor and ＇smallest＇ possible asymptotic variance.

Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

This paper considers the integrated production and delivery scheduling on a serial batch machine,in which split is allowed in the delivery of the jobs.The objective is to minimize the makespan,i.e.,the maximum delivery completion time of the jobs.Lu et al.(Theor Comput Sci 572:50–57,2015)showed that this problem is strongly NP-hard,and presented a 32-approximation algorithm.In this paper,we present an improved 43-approximation algorithm for this problem.We also present a polynomial-time algorithm for the special case when all jobs have the identical weight.

Differential Approximation Algorithm of FSMVRP

Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling cost by vehicles. We give differential approximation algorithms for the fleet size and mix vehicle routing problem （FSMVRP） with two kinds of vehicles, the capacities of which are respectively nlk and n2k, n2 〉 nl ≥ 1, k ≥ 1. Using existing theories for vehicle routing problems and feature of the algorithms represented in the paper, we also prove that the algorithms give（1-6n＋3/（n＋1）2k＋n＋1）differential approximation ratio for （k, nk） VRP, n 〉 1and （1-6n2＋3n/n1k＋n2k）2k）differential approximation ratio for （nlk, n2k）VRP, n2 〉 nl 〉 1.

Approximation Algorithms for Stochastic Combinatorial Optimization Problems

Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems by modeling the uncertainty by a probability distribution over possible realizations.Traditionally,the main focus in stochastic optimization has been various stochastic mathematical programming(such as linear programming,convex programming).In recent years,there has been a surge of interest in stochastic combinatorial optimization problems from the theoretical computer science community.In this article,we survey some of the recent results on various stochastic versions of classical combinatorial optimization problems.Since most problems in this domain are NP-hard(or#P-hard,or even PSPACE-hard),we focus on the results which provide polynomial time approximation algorithms with provable approximation guarantees.Our discussions are centered around a few representative problems,such as stochastic knapsack,stochastic matching,multi-armed bandit etc.We use these examples to introduce several popular stochastic models,such as the fixed-set model,2-stage stochastic optimization model,stochastic adaptive probing model etc,as well as some useful techniques for designing approximation algorithms for stochastic combinatorial optimization problems,including the linear programming relaxation approach,boosted sampling,content resolution schemes,Poisson approximation etc.We also provide some open research questions along the way.Our purpose is to provide readers a quick glimpse to the models,problems,and techniques in this area,and hopefully inspire new contributions.

A Tight Approximation Algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line

In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand.The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint.The authors show that this problem has no polynomialtime algorithm with performance ratio less than 2 on condition that P≠NP,and then provide a 2-approximation algorithm.

Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

The constrained minimum vertex cover problem on bipartite graphs （the Min-CVCB problem） is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε〉 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size （ku, kl）, our algorithm constructs a vertex cover of size （ku^＊, kl^＊）, satisfying max{ku^＊/ku, kl^＊/kl} ≤ 1 ＋ ε.