The celebrated semidefinite programming algorithm for MAX CUT introduced by Goemans and Williamson was known to have a performance ratio of at least [GRAPHICS] (0: 87856 < < 0: 87857);the exact performance ratio...
详细信息
The celebrated semidefinite programming algorithm for MAX CUT introduced by Goemans and Williamson was known to have a performance ratio of at least [GRAPHICS] (0: 87856 < < 0: 87857);the exact performance ratio was unknown. We prove that the performance ratio of their algorithm is exactly. Furthermore, we show that it is impossible to add valid linear constraints to improve the performance ratio.
In this paper, we consider the problem of scheduling independent parallel tasks with individual deadlines so as to maximize the total work performed by the tasks which complete their executions before deadlines. We pr...
详细信息
In this paper, we consider the problem of scheduling independent parallel tasks with individual deadlines so as to maximize the total work performed by the tasks which complete their executions before deadlines. We propose two polynomial-time approximation algorithms for non-malleable parallel tasks and malleable tasks with linear speedup. For non-malleable tasks, the first algorithm guarantees an approximation factor of 5 + epsilon for any positive constant epsilon, while, for malleable tasks with linear speedup, the second algorithm guarantees an approximation factor of 4.5. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
We consider the problem of fitting an n x n distance matrix D by a tree metric T. Let epsilon be the distance to the closest tree metric under the L-infinity norm;that is, epsilon = min(T) {parallel to T ? D parallel ...
详细信息
We consider the problem of fitting an n x n distance matrix D by a tree metric T. Let epsilon be the distance to the closest tree metric under the L-infinity norm;that is, epsilon = min(T) {parallel to T ? D parallel to infinity}. First we present an O(n(2)) algorithm for finding a tree metric T such that parallel to T ? D parallel to infinity less than or equal to 3 epsilon. Second we show that it is NP-hard to find a tree metric T such that parallel to T ? D parallel to infinity < 9/8 epsilon. This paper presents the first algorithm for this problem with a performance guarantee.
In recent years, approximation algorithms based on randomized rounding of fractional optimal solutions have been applied to several classes of discrete optimization problems. In this paper, we describe a class of roun...
详细信息
In recent years, approximation algorithms based on randomized rounding of fractional optimal solutions have been applied to several classes of discrete optimization problems. In this paper, we describe a class of rounding methods that exploits the structure and geometry of the underlying problem to round fractional solution to 0-1 solution. This is achieved by introducing dependencies in the rounding process. We show that this technique can be used to establish the integrality of several classical polyhedra (min cut, uncapacitated lot-sizing, Boolean optimization, k-median on cycle) and produces an improved approximation bound for the min-k-sat problem. (C) 1999 Elsevier Science B.V. All rights reserved.
We consider the problem of scheduling n jobs that are released over time on a single machine in order to minimize the total flow time. This problem is well known to be NP-complete, and the best polynomial-time approxi...
详细信息
We consider the problem of scheduling n jobs that are released over time on a single machine in order to minimize the total flow time. This problem is well known to be NP-complete, and the best polynomial-time approximation algorithms constructed so far had (more or less trivial) worst-case performance guarantees of O(n). In this paper, we present one positive and one negative result on polynomial-time approximations for the minimum total flow time problem: The positive result is the first approximation algorithm with a sublinear worst-case performance guarantee of O(root n). This algorithm is based on resolving the preemptions of the corresponding optimum preemptive schedule. The performance guarantee of our approximation algorithm is not far from best possible, as our second, negative result demonstrates: Unless P = NP, no polynomial-time approximation algorithm for minimum total flow time can have a worst-case performance guarantee of O(n(1/2?epsilon)) for any epsilon > 0.
We consider the problem of finding deterministically a large independent set of guaranteed size in a hypergraph on n vertices and with m edges. With respect to the Turan bound, the quality of our solutions is better f...
详细信息
We consider the problem of finding deterministically a large independent set of guaranteed size in a hypergraph on n vertices and with m edges. With respect to the Turan bound, the quality of our solutions is better for hypergraphs with not too many small cycles by a logarithmic factor in the input size. The algorithms are fast;they often have a running time of O(m) + o(n(3)). Indeed, the denser the hypergraphs are the closer the running times are to the linear times. For the first time, this gives for some combinatorial problems algorithmic solutions with state-of-the-art quality, solutions of which only the existence was known to date. In some cases, the corresponding upper bounds match the lower bounds up to constant factors. The involved concepts are uncrowded hypergraphs.
We deal with the variable-sized bin covering problem: Given a list L of items in (0, 1] and a finite collection B of feasible bin sizes, the goal is to select a set of bins with sizes in B and to cover them with the i...
详细信息
We deal with the variable-sized bin covering problem: Given a list L of items in (0, 1] and a finite collection B of feasible bin sizes, the goal is to select a set of bins with sizes in B and to cover them with the items in L such that the total size of the covered bins is maximized. In the on-line version of this problem, the items must be assigned to bins one by one without previewing future items. This note presents a complete solution to the on-line problem: For every collection B of bin sizes, we give an on-line approximation algorithm with a worst-case ratio r(B), and we prove that no on-line algorithm can perform better in the worst case. The value r(B) mainly depends on the largest gap between consecutive bin sizes. (C) 1999 Elsevier Science B.V. All rights reserved.
This paper considers the problem of sequencing n jobs in a two-machine re-entrant shop with the objective of minimizing the maximum completion time. The shop consists of two machines, M-1 and M-2 , and each job has th...
详细信息
This paper considers the problem of sequencing n jobs in a two-machine re-entrant shop with the objective of minimizing the maximum completion time. The shop consists of two machines, M-1 and M-2 , and each job has the processing route (M-1 , M-2 , M-1 ). An O(n log n) time heuristic is presented which generates a schedule with length at most 4/3 times that of an optimal schedule, thereby improving the best previously available worst-case performance ratio of 3/2.
作者：
Ye, YYUniv Iowa
Dept Management Sci Iowa City IA 52242 USA
We consider the problem of approximating the global maximum of a quadratic program (QP) subject to bound and (simple) quadratic constraints. Based on several early results, we show that a 4/7-approximate solution can ...
详细信息
We consider the problem of approximating the global maximum of a quadratic program (QP) subject to bound and (simple) quadratic constraints. Based on several early results, we show that a 4/7-approximate solution can be obtained in polynomial time.
Given a bounded integer program with n variables and m constraints each with 2 variables we present an O(mU) time and O(m) space feasibility algorithm for such integer programs (where U is the maximal variable range s...
详细信息
ISBN:
(纸本)3540662510
Given a bounded integer program with n variables and m constraints each with 2 variables we present an O(mU) time and O(m) space feasibility algorithm for such integer programs (where U is the maximal variable range size). We show that with the same complexity we can find an optimal solution for the positively weighted minimization problem for monotone systems. Using the local-ratio technique we develop an O(nmU) time and O(m) space 2-approximation algorithm for the positively weighted minimization problem for the general case. We further generalize all results to non linear constraints (called an's-convex constraints) and to non linear (but monotone) weight functions. Our algorithms are not only better in complexity than other known algorithms, but they are also considerably simpler, and Contribute to the understanding of these very fundamental problems.
暂无评论