This paper presents approximation algorithms for two extensions of the set cover problem: a graph-based extension known as the Max-Rep or Label-Cover(MAX)problem, and a color-based extension known as the Red-Blue Set ...
详细信息
This paper presents approximation algorithms for two extensions of the set cover problem: a graph-based extension known as the Max-Rep or Label-Cover(MAX)problem, and a color-based extension known as the Red-Blue Set Cover problem. First, a randomized algorithm guaranteeing approximation ratio root n with high probability is proposed for the Max-Rep (or Label-Cover(MAX)) problem, where n is the number of vertices in the graph. This algorithm is then generalized into a 4 root n-ratio algorithm for the nonuniform version of the problem. Secondly, it is shown that the Red-Blue Set Cover problem can be approximated with ratio 2 root n log beta, where n is the number of sets and beta is the number of blue elements. Both algorithms can be adapted to the weighted variants of the respective problems, yielding the same approximation ratios. (C) 2006 Elsevier B.V. All rights reserved.
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 ***,the main focus in st...
详细信息
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 ***,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 *** this article,we survey some of the recent results on various stochastic versions of classical combinatorial optimization *** 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 *** discussions are centered around a few representative problems,such as stochastic knapsack,stochastic matching,multi-armed bandit *** 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 *** also provide some open research questions along the *** purpose is to provide readers a quick glimpse to the models,problems,and techniques in this area,and hopefully inspire new contributions.
We consider a purchase/inventory control problem in which the purchase price and demand are stochastic, a common situation encountered by firms that replenish in a foreign currency or from commodity markets. More spec...
详细信息
We consider a purchase/inventory control problem in which the purchase price and demand are stochastic, a common situation encountered by firms that replenish in a foreign currency or from commodity markets. More specifically, we assume that the demand follows a Poisson arrival process and that the log-price evolves according to a general Wiener process. Under these circumstances, the optimal policy is a state dependent base-stock policy that can be described as a series of threshold prices. An iterative procedure for determining the optimal thresholds has been derived earlier but, even for the simplest price process, the solution quickly becomes numerically intractable. To deal with this, we propose an approximation that allows us to derive simple heuristics for finding thresholds that are close to optimal. For certain price processes the heuristics are just a series of closed-form expressions. The computational complexity is reduced significantly, and the numerical study shows that the new heuristics perform considerably better than earlier suggested heuristics.
We study the load-balanced capacitated vehicle routing problem (LBCVRP): the problem is to design a collection of tours for a fixed fleet of vehicles with capacityQto distribute a supply from a single depot between a ...
详细信息
We study the load-balanced capacitated vehicle routing problem (LBCVRP): the problem is to design a collection of tours for a fixed fleet of vehicles with capacityQto distribute a supply from a single depot between a number of predefined clients, in a way that the total traveling cost is a minimum, and the vehicle loads are balanced. The unbalanced loads cause the decrease of distribution quality especially in business environments and flexibility in the logistics activities. The problem being NP-hard, we propose two approximation algorithms. When the demands are equal, we present a((1-1Q)rho+3/2)-approximation algorithm that finds balanced loads. Here, rho is the approximation ratio for the known metric traveling salesman problem (TSP). This result leads to a 2.5-1/Q approximation ratio for the tree metrics since an optimal solution can be found for the TSP on a tree. We present an improved2- approximation algorithm. When the demands are unequal, we focus on obtaining approximate solutions since finding balanced loads is NP-complete. We propose an algorithm that provides a4-approximation for the balance of the loads. We assume a second approach to get around the difficulties of the feasibility. In this approach, we redefine and convert the problem into a multi-objective problem. The algorithm we propose has a 4 factor of approximation.
We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by "proper" functions, a class o...
详细信息
We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by "proper" functions, a class of 0-1 functions indicating the number of edges crossing each cut. We also provide quasipolynomial-time approximation algorithms for finding two-edge-connected spanning subgraphs of approximately minimum degree of a given two-edge-connected graph, and a spanning tree (branching) of approximately minimum degree of a directed graph. The degree of the output network in all cases is guaranteed to be at most (1 + epsilon) times the optimal degree, plus an additive O(log(1+epsilon)n) for any epsilon > 0. Our analysis indicates that the degree of an optimal subgraph for each of the problems above is well estimated by certain polynomially solvable linear programs. This suggests that the linear programs we describe could be useful in obtaining optimal solutions via branch and bound. (C) 2004 Wiley Periodicals, Inc.
Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V-l,...,V-k. The clustered traveling sal...
详细信息
Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V-l,...,V-k. The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.
The task of finding the largest subset of vertices of a graph that induces a planar subgraph is known as the Maximum Induced Planar Subgraph problem (MIPS). In this paper, some new approximation algorithms for MIPS ar...
详细信息
The task of finding the largest subset of vertices of a graph that induces a planar subgraph is known as the Maximum Induced Planar Subgraph problem (MIPS). In this paper, some new approximation algorithms for MIPS are introduced. The results of an extensive study of the performance of these and existing MIPS approximation algorithms on randomly generated graphs are presented. Efficient algorithms for finding large induced outerplanar graphs are also given. One of these algorithms is shown to find an induced outerplanar subgraph with at least 3n/(d + 5/3) vertices for graphs of n vertices with maximum degree at most d. The results presented in this paper indicate that most existing algorithms perform substantially better than the existing lower bounds indicate.
We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search algorithm yields a PTAS. F...
详细信息
We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.
Let G = (V, E) be a complete undirected graph, with node set V = {v(1),...,v(n)} and edge set E. The. edges (vi, vi) E E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = {k(i)...
详细信息
Let G = (V, E) be a complete undirected graph, with node set V = {v(1),...,v(n)} and edge set E. The. edges (vi, vi) E E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = {k(i)}(i=1)(p) (Sigma(i=1)(p) k(i) less than or equal to \V\), the minimum K-cut problem is to compute disjoint subsets with sizes {k(i)}(i=1)(p), minimizing the total weight of edges whose two ends are in different subsets. We demonstrate that for any fixed p it is possible to obtain in polynomial time an approximation of at most three times the optimal value. We also prove bounds on the ratio between the weights of maximum and minimum cuts.
A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-...
详细信息
A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-time algorithms are provided for approximating the problem of finding a feedback vertex set of G with smallest weight. When the weights of all vertices in G are equal, the performance ratio attained by these algorithms is 4 - (2/n). This improves a previous algorithm which achieved an approximation factor of O(root log n) for this case. For general vertex weights, the performance ratio becomes min {2 Delta(2), 4 log(2)n} where Delta denotes the maximum degree in G. For the special case of planar graphs this ratio is reduced to 10. An interesting special case of weighted graphs where a performance ratio of 4 - (2/n) is achieved is the one where a prescribed subset of the vertices, so-called blackout vertices, is not allowed to participate in any feedback vertex set. It is shown how these algorithms can improve the search performance for constraint satisfaction problems. An application in the area of Bayesian inference of graphs with blackout vertices is also presented.
暂无评论