In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-) optimal solution of the linear programming ( LP) relaxation, lead...
详细信息
In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-) optimal solution of the linear programming ( LP) relaxation, leading to a partial integer solution and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. For d-dimensional vector packing, we obtain a polynomial-time randomized algorithm with asymptotic approximation guarantee arbitrarily close to ln d + 1. For d = 2, this value is 1.693...;i.e., we break the natural 2 "barrier" for this case. Moreover, for small values of d this is a notable improvement over the previously known O(ln d) guarantee by Chekuri and Khanna [SIAM J. Comput., 33 ( 2004), pp. 837-851]. For two-dimensional bin packing with and without rotations, we obtain polynomial-time randomized algorithms with asymptotic approximation guarantee 1.525..., improving upon previous algorithms with asymptotic performance guarantees arbitrarily close to 2 by Jansen and van Stee [ On strip packing with rotations, in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pp. 755-761] for the problem with rotations and 1.691... by Caprara [ Math. Oper. Res., 33 ( 2008), pp. 203-215] for the problem without rotations. The previously unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker [Combinatorica, 1 ( 1981), pp. 349-355]. We prove that their approximation scheme is "subset oblivious," which leads to numerous applications.
This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumabl...
详细信息
This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed. (C) 2007 Elsevier Ltd. All rights reserved.
For any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [1...
详细信息
For any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + epsilon)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.
Given a multivariate quadratic polynomial system in a finite field F,, the problem MAX-MQ is to find a solution satisfying the maximal number of equations. We prove that the probability of a random assignment satisfyi...
详细信息
Given a multivariate quadratic polynomial system in a finite field F,, the problem MAX-MQ is to find a solution satisfying the maximal number of equations. We prove that the probability of a random assignment satisfying a non-degenerate quadratic equation is at least 1/q - O(q(-n/2)), where n is the number of the variables in the equation. Consequently, the random assignment provides a polynomial-time approximation algorithm with approximation ratio q + O(q(-n/2)) for non-degenerate MAX-MQ. For large n, the ratio is close to q. According to a result by Hastad, it is NP-hard to approximate MAX-MQ with an approximation ratio of q - is an element of for a small positive number is an element of. Therefore, the minimal approximation ratio that can be achieved in polynomial time for MAX-MQ is q. (C) 2009 Elsevier B.V. All rights reserved.
We consider a problem of minimizing the number of batches of a fixed capacity processing the orders of various sizes on a finite set of items. This batch consolidation problem is motivated by the production system typ...
详细信息
We consider a problem of minimizing the number of batches of a fixed capacity processing the orders of various sizes on a finite set of items. This batch consolidation problem is motivated by the production system typical in raw material industries in which multiple items can be processed in the same batch if they share sufficiently close production parameters. if the number of items processed in a batch is restricted to being up to some fixed integer k, the problem is referred to as the k-batch consolidation problem. We will show that the k-batch consolidation problem admits an approximation whose factor is twice that of the k-set cover problem. In particular, this implies an upper bound on the approximation factor, 2H(k) - 1, where H-k = 1 + 1/2 + ... + 1/k (C) 2008 Elsevier B.V. All rights reserved.
The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time unti...
详细信息
The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented. (C) 2008 Elsevier B.V. All rights reserved.
Given a graph G=(V,E) with node weight w:V -> R (+) and a subset SaS dagger V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied i...
详细信息
Given a graph G=(V,E) with node weight w:V -> R (+) and a subset SaS dagger V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0 < a < 1 unless NPaS dagger DTIME(n (O(log n))), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5 rho-approximation where rho is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+epsilon)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+epsilon)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.
We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. This algorithm provides a 2-ap...
详细信息
We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. This algorithm provides a 2-approximation to the minimum edge dominating set and minimum maximal matching problems. We refine its analysis and give an expression of the approximation ratio that is strictly less than 2 in the cases where the input graph has it vertices and at least epsilon (n 2) edges, for epsilon > 1/2. This ratio is shown to be asymptotically tight for epsilon > 1/2. (C) 2009 Elsevier B.V. All rights reserved.
Given a set of leaf-labeled trees with identical leaf sets, the well-known Maximum Agreement SubTree (MAST) problem consists in finding a subtree homeomorphically included in all input trees and with the largest numbe...
详细信息
Given a set of leaf-labeled trees with identical leaf sets, the well-known Maximum Agreement SubTree (MAST) problem consists in finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its variant called Maximum Compatible Tree (MCT) are of particular interest in computational biology. This article presents a linear-time approximation algorithm to solve the complement version of MAST, namely identifying the smallest set of leaves to remove from input trees to obtain isomorphic trees. We also present an O(n(2) + kn) algorithm to solve the complement version of MCT. For both problems, we thus achieve significantly lower running times than previously known algorithms. Fast running times are especially important in phylogenetics where large collections of trees are routinely produced by resampling procedures, such as the nonparametric bootstrap or Bayesian MCMC methods.
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 p...
详细信息
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.
暂无评论