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.
In this paper we consider the following natural generalization of two fundamental problems: the Set-Cover problem and the Min-Knapsack problem. We are given an hypergraph, each vertex has a nonnegative weight and each...
详细信息
ISBN:
(纸本)0898714346
In this paper we consider the following natural generalization of two fundamental problems: the Set-Cover problem and the Min-Knapsack problem. We are given an hypergraph, each vertex has a nonnegative weight and each edge has a nonnegative length. For a given threshold (l) over cap, our objective is to find a subset of the vertices with minimum total cost, such that at least a length of (l) over cap of the edges are covered. This problem is called the partial set cover problem. We present an O(\V\(2) + \H\) time, Delta(E)-approximation algorithm for this problem, where Delta(E) greater than or equal to 2 is an upper bound on the edge cardinality of the hypergraph, and \H\ is the size of the hypergraph (i.e. the sum of all its edges cardinalities). We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.
In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow...
详细信息
In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides irs practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n log n) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
暂无评论