SONET ADMs are the dominant cost factor in the WDM/SONET rings. Recently several articles (Belvaux et al., European J. Oper. Res. 108 (1) (1998) 26-35;Calinescu and Wan, Traffic partition in WDM/SONET rings to minimiz...
详细信息
SONET ADMs are the dominant cost factor in the WDM/SONET rings. Recently several articles (Belvaux et al., European J. Oper. Res. 108 (1) (1998) 26-35;Calinescu and Wan, Traffic partition in WDM/SONET rings to minimize SONET ADMs, submitted for publication;Gerstel et al., Proc. IEEE INFOCOM'98, vol. 1, pp. 94-101;Liu et al., Proc. INFOCOM, vol. 2, 2000, pp. 1020-1025;Sutter et al., Oper. Res. 46 (5) (1998) 719-728) proposed a number of heuristics for traffic partition so as to use as few SONET ADMs as possible. Most of these heuristics assumes wavelength-continuity, i.e., the same wavelength is allocated on all of the links in the path established for a traffic stream. It was first observed and argued by Gerstel et al. that the number of ADMs can be potentially reduced by allowing a traffic stream to be locally transferred from one ADM in a wavelength to another ADM in a different wavelength at any intermediate node, in other words, the traffic streams are splittable. In this paper, we study two variations of this minimum ADM problem with splittable traffic streams: all traffic streams have prespecified routings, and all traffic streams have no prespecified routings respectively. Both variations are shown to be NP-hard. For the former variation, a heuristic with approximation ratio at most 5/4 is proposed. For the latter variation, a similar heuristic with approximation ratio 3/2 is proposed. (C) 2002 Published by Elsevier Science B.V.
We analyze the worst-case performance of a simple algorithm for the breakpoint median problem (BMP), a well-known problem in computational biology. BMP is the special case of the min-cost traveling salesman problem on...
详细信息
We analyze the worst-case performance of a simple algorithm for the breakpoint median problem (BMP), a well-known problem in computational biology. BMP is the special case of the min-cost traveling salesman problem on a complete graph G = (V, E), in which the edge cost vector c is an element of R-E has the form 1 - x*, with x* a convex combination of the incidence vectors of the Hamiltonian circuits of G. The performance guarantee shown is 5/3, which improves on the previously known guarantee of 2. We also consider the signed variant of BMP and prove that a similar approach yields a performance guarantee of 3/2 (again improving over the previously known 2). Our proofs are based on formulating the problem as a suitable integer linear program and then defining a feasible dual solution for the associated linear programming relaxation in two phases, in a so-called additive bounding fashion.
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.
暂无评论