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.

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.

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.

Approximation Algorithms on k-Correlation Clustering

In this paper,we consider the k-correlation clustering problem.Given an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of“+”edges within clusters and“−”edges between clusters.This problem is NP-hard.We design an approximation algorithm with the approximation ratio{a,(2-k)a+k-1/k},where a is the weighted proportion of“+”edges in all edges.As a varies from 0 to 1,the approximation ratio varies from k-1/k to 1 and the minimum value is 1/2.

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 Algorithms for Graph Partition into Bounded Independent Sets

The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.

Approximation Algorithms for Multi-vehicle Stacker Crane Problems

We study a variety of multi-vehicle generalizations of the Stacker Crane Problem(SCP).The input consists of a mixed graph G=(V,E,A)with vertex set V,edge set E and arc set A,and a nonnegative integer cost function c on E∪A.We consider the following three problems:(1)k-depot SCP(k-DSCP).There is a depot set D⊆V containing k distinct depots.The goal is to determine a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized,where each closed walk corresponds to the route of one vehicle and has to start from a distinct depot and return to it.(2)k-SCP.There are no given depots,and each vehicle may start from any vertex and then go back to it.The objective is to find a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized.(3)k-depot Stacker Crane Path Problem(k-DSCPP).There is a depot set D⊆V containing k distinct depots.The aim is to find k(open)walks including all the arcs of A such that the total cost of the walks is minimized,where each(open)walk has to start from a distinct depot but may end at any vertex.We present the first constant-factor approximation algorithms for all the above three problems.To be specific,we give 3-approximation algorithms for the k-DSCP,the k-SCP and the k-DSCPP.If the costs of the arcs are symmetric,i.e.,for every arc there is a parallel edge of no greater cost,we develop better algorithms with approximation ratios max{9/5,2−1/2k+1},2,2,respectively.All the proposed algorithms have a time complexity of O(|V|3)except that the two 2-approximation algorithms run in O(|V|2log|V|)time.

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.

Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal

Given a weighted graph G=(V,E)with weight w:E→Z+,a k-cycle transversal is an edge subset A of E such that G−A has no k-cycle.The minimum weight of kcycle transversal is the weighted transversal number on k-cycle,denoted byτk(Gw).In this paper,we design a(k−1/2)-approximation algorithm for the weighted transversal number on k-cycle when k is odd.Given a weighted graph G=(V,E)with weight w:E→Z+,a k-clique transversal is an edge subset A of E such that G−A has no k-clique.The minimum weight of k-clique transversal is the weighted transversal number on k-clique,denoted byτapproximation algorithm for the weighted transversal number on k(Gw).In this paper,we design a(k2−k−1)/2-k-clique.Last,we discuss the relationship between k-clique covering and k-clique packing in complete graph Kn.

IMPROVED RESULTS ON THE ROBUSTNESS OF STOCHASTIC APPROXIMATION ALGORITHMS

This paper is a continuation of the research carried out in [1]-[2], where the robustnessanalysis for stochastic approximation algorithms is given for two cases: 1. The regression functionand the Liapunov function are not zero at the sought-for x^0, 2. lim supnot zero, here {ξ_i} are the measurement errors and {a_n} are the weighting coefficients in thealgorithm. Allowing these deviations from zero to occur simultaneously but to remain small, thispaper shows that the estimation error is still small even for a class fo measurement errors moregeneral than that considered in [2].

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.

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.

Approximation Algorithms for Steiner Connected Dominating Set

Steiner connected dominating set （SCDS） is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP- hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of （2 ＋ 1/（m - 1））H（min（△, k）） ＋O（1）, which outperforms the previous best result （c ＋ 1）H（min（△, k）） ＋ O（1） in the case of m ≥ 1 ＋1/（c - 1）, where c is the best approximation ratio for Steiner tree, A is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0 ≤ m ≤ min（△, k） and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2 ln（min（△, k）） ＋ O（1）, which can also be improved to 2 lnk if the optimal solution is greater than c·e^2c＋1/2（c＋1）.

Approximation Algorithms for Vertex Happiness

We investigate the maximum happy vertices(MHV)problem and its complement,the minimum unhappy vertices(MUHV)problem.In order to design better approximation algorithms,we introduce the supermodular and submodular multi-labeling(SUP-ML and SUB-ML)problems and show that MHV and MUHV are special cases of SUP-ML and SUB-ML,respectively,by rewriting the objective functions as set functions.The convex relaxation on the I ovasz extension,originally presented for the submodular multi-partitioning problem,can be extended for the SUB-ML problem,thereby proving that SUB-ML(SUP-ML,respectively)can be approximated within a factorof2-2/k(2/k,respectively),where k is the number of labels.These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k,respectively,using the same approximation algorithms.For the MUHV problem,we also show that it is approximation-equivalent to the hypergraph multiway cut problem;thus,MUHV is Unique Games-hard to achieve a(2-2/k-e)-approximation,for anyε>0.For the MHV problem,the 2/k-approximation improves the previous best approximation ratio max{1/k,1/(△+1/g(△)},where△is the maximum vertex degree of the input graph and g(△)=(√△+√△+1)2△>4△2.We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovasz extension for SUP-ML;we then prove an upper bound of 2/k on the integrality gap of this LP relaxation,which suggests that the 2/k-approximation is the best possible based on this LP relaxation.Lastly,we prove that it is Unique Games-hard to approximate the MHV problem within a factor of S2(log2 k/k).

Approximation Algorithms for 3D Orthogonal Knapsack

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 ＋ ε and 8 ＋ ε, as well as an algorithm with approximation ratio 7 ＋ ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 ＋ ε and 5 ＋ ε, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.

Approximation algorithms for nonnegative polynomial optimization problems over unit spheres

We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some efficient algorithms are presented and numerical results are reported to show the efficiency of our proposed algorithms.

Comparison of two kinds of approximate proximal point algorithms for monotone variational inequalities

This paper proposes two kinds of approximate proximal point algorithms （APPA） for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter＇s APPA in the paper ＂Error bounds for proximal point subproblems and associated inexact proximal point algorithms＂ published in 2000. They are both prediction- correction methods which use the same inexactness restriction; the only difference is that they use different search directions in the correction steps. This paper also chooses an optimal step size in the two versions of the APPA to improve the profit at each iteration. Analysis also shows that the two APPAs are globally convergent under appropriate assumptions, and we can expect algorithm 2 to get more progress in every iteration than algorithm 1. Numerical experiments indicate that algorithm 2 is more efficient than algorithm 1 with the same correction step size,

A Note on an Economic Lot-sizing Problem with Perishable Inventory and Economies of Scale Costs:Approximation Solutions and Worst Case Analysis

This paper presents an economic lot-sizing problem with perishable inventory and general economies of scale cost functions. For the case with backlogging allowed, a mathematical model is formulated, and several properties of the optimal solutions are explored. With the help of these optimality properties, a polynomial time approximation algorithm is developed by a new method. The new method adopts a shift technique to obtain a feasible solution of subproblem and takes the optimal solution of the subproblem as an approximation solution of our problem. The worst case performance for the approximation algorithm is proven to be （4√2 ＋ 5）/7. Finally, an instance illustrates that the bound is tight.

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.

MODIFIED APPROXIMATE PROXIMAL POINT ALGORITHMS FOR FINDING ROOTS OF MAXIMAL MONOTONE OPERATORS

In order to find roots of maximal monotone operators, this paper introduces and studies the modified approximate proximal point algorithm with an error sequence {e k} such that || ek || \leqslant hk || xk - [(x)\tilde]k ||\left\| { e^k } \right\| \leqslant \eta _k \left\| { x^k - \tilde x^k } \right\| with ?k = 0￥ ( hk - 1 ) < + ￥\sum\limits_{k = 0}^\infty {\left( {\eta _k - 1} \right)} and infk \geqslant 0 hk = m\geqslant 1\mathop {\inf }\limits_{k \geqslant 0} \eta _k = \mu \geqslant 1 . Here, the restrictions on {η k} are very different from the ones on {η k}, given by He et al (Science in China Ser. A, 2002, 32 (11): 1026–1032.) that supk \geqslant 0 hk = v < 1\mathop {\sup }\limits_{k \geqslant 0} \eta _k = v . Moreover, the characteristic conditions of the convergence of the modified approximate proximal point algorithm are presented by virtue of the new technique very different from the ones given by He et al.