In this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph G. This problem is known to be APX-hard, for both the edge and the vertex connectivi...
详细信息
In this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph G. This problem is known to be APX-hard, for both the edge and the vertex connectivity case. Here we prove that the APX-hardness still holds even if one restricts the edge costs to an interval [1, 1 + epsilon], for an arbitrary small epsilon > 0. This result implies the first explicit lower bound on the approximability of the general version (i.e., for arbitrary graphs) of the problem. On the other hand, if the input graph satisfies the sharpened beta-triangle inequality, then a (2/3 + 1/3 (.) beta/1-beta)-approximation algorithm is designed. This ratio tends to 1 with beta tending to 1/2, and it improves the previous known bound of 3/2 holding for graphs satisfying the triangle inequality, as soon as beta < 5/7. Furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of G by means of a set of edges of minimum cost is considered. This problem is known to admit a 2-approximation algorithm. Here we show that whenever the input graph satisfies the sharpened beta-triangle inequality with beta < 2/3, then this ratio can be improved to beta/1-beta. (C) 2004 Elsevier B.V. All rights reserved.
We present a 0.7499-approximation algorithm for Max Set Splitting in this paper. The previously best known result for this problem is a 0.7240-approximation by Andersson and Engebretsen (Inform. Process. Lett. 65 (199...
详细信息
We present a 0.7499-approximation algorithm for Max Set Splitting in this paper. The previously best known result for this problem is a 0.7240-approximation by Andersson and Engebretsen (Inform. Process. Lett. 65 (1998) 305), which is based on a semidefinite programming (SDP) relaxation. Our improvement is resulted from a strengthened SDP relaxation, an improved rounding method, and a tighter analysis compared with that in Andersson and Engebretsen (1998). (C) 2004 Elsevier B.V. All rights reserved.
A radio labeling of a graph G is an assignment of pairwise distinct, positive integer labels to the vertices of G such that labels of adjacent vertices differ by at least 2. The radio labeling problem (RL) consists in...
详细信息
A radio labeling of a graph G is an assignment of pairwise distinct, positive integer labels to the vertices of G such that labels of adjacent vertices differ by at least 2. The radio labeling problem (RL) consists in determining a radio labeling that minimizes the maximum label that is used (the so-called span of the labeling). RL is a well-studied problem, mainly motivated by frequency assignment problems in which transmitters are not allowed to operate on the same frequency channel. We consider the special case where some of the transmitters have preassigned operating frequency channels. This leads to the natural variants p-RL(l) and p-RL(*) of RL with l preassigned labels and an arbitrary number of preassigned labels, respectively. We establish a number of combinatorial, algorithmical, and complexity-theoretical results for these variants of radio labeling. In particular, we investigate a simple upper bound on the minimum span, yielding a linear time approximation algorithm with a constant additive error bound for p-RL(*) restricted to graphs with girth greater than or equal to 5. We consider the complexity of p-RL( l) and p-RL(*) for several cases in which RL is known to be polynomially solvable. On the negative side, we prove that p-RL(*) is NP-hard for cographs and for k-colorable graphs where a k-coloring is given (k greater than or equal to 3). On the positive side, we derive polynomial time algorithms solving p-RL(*) and p-RL(l) for graphs with bounded maximum degree, and for solving p-RL(l) for k-colorable graphs where a k-coloring is given.
The paper presents a general method of designing constant-factor approximation algorithms for some discrete optimization problems with assignment-type constraints. The core of the method is a simple deterministic proc...
详细信息
The paper presents a general method of designing constant-factor approximation algorithms for some discrete optimization problems with assignment-type constraints. The core of the method is a simple deterministic procedure of rounding of linear relaxations ( referred to as pipage rounding). With the help of the method we design approximation algorithms with better performance guarantees for some well-known problems including MAXIMUM COVERAGE, MAX CUT with given sizes of parts and some of their generalizations.
The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is...
详细信息
The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +infinity, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.
Let P be a set of n points in the plane. The geometric minimum-diameter spanning tree (MDST) of P is a tree that spans P and minimizes the Euclidean length of the longest path. It is known that there is always a mono-...
详细信息
Let P be a set of n points in the plane. The geometric minimum-diameter spanning tree (MDST) of P is a tree that spans P and minimizes the Euclidean length of the longest path. It is known that there is always a mono- or a dipolar MDST, i.e., a MDST with one or two nodes of degree greater 1, respectively. The more difficult dipolar case can so far only be solved in slightly subcubic time. This paper has two aims. First, we present a solution to a new data structure for facility location, the minimum-sum dipolar spanning tree (MSST), that mediates between the minimum-diameter dipolar spanning tree and the discrete two-center problem (2CP) in the following sense: find two centers p and q in P that minimize the sum of their distance plus the distance of any other point (client) to the closer center. This is of interest if the two centers do not only serve their customers (as in the case of the 2CP), but frequently have to exchange goods or personnel between themselves. We show that this problem can be solved in 0(n 2 log n) time and that it yields a factor-4/3 approximation of the MDST.
The minimum alpha-small partition problem is the problem of partitioning a given simple polygon into subpolygons, each with diameter at most alpha, for a given alpha > 0. This paper considers the version of this pr...
详细信息
The minimum alpha-small partition problem is the problem of partitioning a given simple polygon into subpolygons, each with diameter at most alpha, for a given alpha > 0. This paper considers the version of this problem that disallows Steiner points. This problem is motivated by applications in mesh generation and collision detection. The main result in the paper is a polynomial-time algorithm that solves this problem, and either returns an optimal partition or reports the nonexistence of such a partition. This result contrasts with the recent NP-completeness result for the minimum a-small partition problem for polygons with holes (C. Worman, 15th Canadian Conference on Computational Geometry, 2003). Even though the running time of our algorithm is a polynomial in the input size, it is prohibitive for most real applications and we seek faster algorithms that approximate an optimal solution. We first present a faster 2-approximation algorithm for the problem for simple polygons and then a near linear-time algorithm for convex polygons that produces, for any epsilon > 0. an (alpha + epsilon)-small partition with no more polygons than in an optimal alpha-small partition. We also present an exact polynomial-time algorithm for the minimum alpha-small partition problem with the additional constraint that each piece in the partition be convex.
We show that, if NP not equal ZPP, for any epsilon > 0, the toughness of a graph with n vertices is not approximable in polynomial time within a factor of (1)/(2) (n/2)(1-epsilon). We give a 4-approximation for gra...
详细信息
We show that, if NP not equal ZPP, for any epsilon > 0, the toughness of a graph with n vertices is not approximable in polynomial time within a factor of (1)/(2) (n/2)(1-epsilon). We give a 4-approximation for graphs with toughness bounded by (1)/(3) and we show that this result cannot be generalized to graphs with a bounded toughness. More exactly we prove that there is no constant approximation for graphs with bounded toughness, unless P = NP. (C) 2003 Elsevier B.V. All rights reserved.
The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems [8], and it...
详细信息
ISBN:
(纸本)3540228233
The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems [8], and its approximability is largely open. We prove a lower approximation bound of 8root5 - 15 approximate to 2.88854, improving the previous bound of 10root5 - 21 approximate to 1.36067 by Dinur and Safra [5]. For highly restricted instances with exactly 4 occurrences of every variable we provide a lower bound of 3/2. Both inapproximability results apply to instances with no mixed Clauses (the literals in every clause are both either negated, or unnegated). We further prove that any k-approximation algorithm for MINIMUM 2SAT-DELETION polynomially reduces to a (2 - 2/k+1)-approximation algorithm for the MINIMUM VERTEX COVER problem. One ingredient of these improvements is our proof that for the MINIMUM VERTEX COVER problem restricted to graphs with a perfect matching its threshold on polynomial time approximability is the same as for the general MINIMUM VERTEX COVER problem. This improves also on results of Chen and Kanj [3].
暂无评论