In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs;the demand...
详细信息
In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs;the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints, Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem.
It is proved that computing the maximum diameter ratio (also known as the local density) of a graph is APX-complete. The related problem of finding a maximum subgraph of a fixed diameter d greater than or equal to 1 i...
详细信息
It is proved that computing the maximum diameter ratio (also known as the local density) of a graph is APX-complete. The related problem of finding a maximum subgraph of a fixed diameter d greater than or equal to 1 is proved to be even harder to approximate. (C) 2002 Elsevier Science B.V. All rights reserved.
We study the general partitioning problem and the discrepancy problem in dense hypergraphs. Using the regularity lemma (Szemeredi, Problemes Combinatories et Theorie des Graphes (1978), pp. 399-402) and its algorithmi...
详细信息
We study the general partitioning problem and the discrepancy problem in dense hypergraphs. Using the regularity lemma (Szemeredi, Problemes Combinatories et Theorie des Graphes (1978), pp. 399-402) and its algorithmic version proved in Czygrinow and Rodl (SIAM J. Comput., to appear), we give polynomial-time approximation schemes for the general partitioning problem and for the discrepancy problem. (C) 2002 Elsevier Science B.V. All rights reserved.
We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax-by≤z+c, where a and b are nonnegative and the va...
详细信息
We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax-by≤z+c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective *** integer programs are optimization problems with constraints of the type ax+by≤z+c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we *** algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex *** that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality.
We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax - by≤z + c, where a and b are nonnegative and th...
详细信息
We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax - by≤z + c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions. Nonmonotone integer programs are optimization problems with constraints of the type ax + by≤z + c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe. The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover. Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integral
The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is...
详细信息
The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is important to locate a small number of centers in the network such that every node is nearby at least one center. Finding a dominating set of minimum size is NP-complete, and the best known approximation is logarithmic in the maximum degree of the graph and is provided by the same simple greedy approach that gives the well-known logarithmic approximation result for the closely related set cover problem. We describe and analyze new randomized distributed algorithms for the dominating set problem that run in polylogarithmic time, independent of the diameter of the network, and that return a dominating set of size within a logarithmic factor from optimal, with high probability. In particular, our best algorithm runs in O (log n log, Delta) rounds with high probability, where n is the number of nodes, Delta is one,plus the maximum degree of any node, and each round involves a constant number of message exchanges among any two neighbors;the size of the dominating set obtained is within O (log Delta) of the optimal in expectation and within O(log n) of the optimal with high probability. We also describe generalizations to the weighted case and the case of multiple covering requirements.
It is proved that computing the maximum diameter ratio (also known as the local density) of a graph is APX-complete. The related problem of finding a maximum subgraph of a fixed diameter d greater than or equal to 1 i...
详细信息
It is proved that computing the maximum diameter ratio (also known as the local density) of a graph is APX-complete. The related problem of finding a maximum subgraph of a fixed diameter d greater than or equal to 1 is proved to be even harder to approximate. (C) 2002 Elsevier Science B.V. All rights reserved.
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, th...
详细信息
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1 + delta can be achieved by a quadratic-time algorithm for any given constant delta > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved by a low-degree polynomial-time algorithm if no vertex is given a weight, while a ratio of 5 can be achieved by a low-degree polynomial-time algorithm otherwise. (C) 2001 Academic Press.
We introduce the following optimization version of the classical pattern matching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a two-dimensional rectangul...
详细信息
We introduce the following optimization version of the classical pattern matching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a two-dimensional rectangular pattern, find the maximum number of non-overlapping occurrences of the pattern in the text. Unlike the classical two-dimensional pattern matching problem, the maximum two-dimensional pattern matching problem is NP-complete. We devise polynomial time approximation algorithms and approximation schemes for this problem. We also briefly discuss how the approximation algorithms can be extended to include a number of other variants of the problem. (C) 2001 Elsevier Science B.V. All rights reserved.
We examine the bandwidth problem in circular-arc graphs, chordal graphs with a bounded number of leaves in the clique tree, and k-polygon graphs (fixed k). We show that all of these graph classes admit efficient appro...
详细信息
We examine the bandwidth problem in circular-arc graphs, chordal graphs with a bounded number of leaves in the clique tree, and k-polygon graphs (fixed k). We show that all of these graph classes admit efficient approximation algorithms which are based on exact or approximate bandwidth layouts of related interval graphs. Specifically, we obtain a bandwidth approximation algorithm for circular-arc graphs that executes in O(n log(2) n) time and has performance ratio 2, which is the best possible performance ratio of any polynomial time bandwidth approximation algorithm for circular-arc graphs. For chordal graphs with at most k leaves in the clique tree, we obtain a performance ratio of 2k in O(k(n+m)) time, and our algorithm for k-polygon graphs has performance ratio 2k(2) and runs in time O(n(3)).
暂无评论