For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut pr...
详细信息
For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 - 3/k for an odd k and 2 - (3k - 4)/(k(2) - k) for an even k. The running time is O(kmn(3) log(n(2)/m)) where n and m are the numbers of vertices and edges respectively.
We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a numb...
详细信息
We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst-case ratio 3/2 is given for the version where the processing times of large jabs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst-case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. (C) 2001 John Wiley & Sons, Inc. Naval Research Logistics 48. 226-240, 2001.
In this paper, we present a projected gradient algorithm for solving the semidefinite programming (SDP) relaxation of the maximum cut (maxcut) problem. Coupled with a randomized method, this gives a very efficient app...
详细信息
In this paper, we present a projected gradient algorithm for solving the semidefinite programming (SDP) relaxation of the maximum cut (maxcut) problem. Coupled with a randomized method, this gives a very efficient approximation algorithm for the maxcut problem. We report computational results comparing our method with two earlier successful methods on problems with dimension up to 7,000.
We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P-max/12 greater than the optimal ...
详细信息
We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P-max/12 greater than the optimal schedule length, where P-max is the length of the longest job.
It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P not equal NP....
详细信息
It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P not equal NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m greater than or equal to 2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4. (C) 2001 Elsevier Science B.V. All rights reserved.
作者：
Makino, KUno, YIbaraki, TUniv Osaka Prefecture
Coll Integrated Arts & Sci Dept Math & Informat Sci Sakai Osaka 5918531 Japan Osaka Univ
Grad Sch Engn Sci Div Syst Sci Toyonaka Osaka 5608531 Japan Kyoto Univ
Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan
In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST);i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a giv...
详细信息
In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST);i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio min {(Delta* - 1) log n/Delta*, Delta* - 1}/log(Delta* + 1) - 1, where n is the number of vertices in G and Delta* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees. (C) 2001 Academic Press.
We present a Lagrangian decomposition algorithm which uses logarithmic potential reduction to compute an epsilon -approximate solution of the general max-min resource sharing problem with M nonnegative concave constra...
详细信息
We present a Lagrangian decomposition algorithm which uses logarithmic potential reduction to compute an epsilon -approximate solution of the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. We show that this algorithm runs in O(M (epsilon (-2) + In M)) iterations, a data independent bound which is optimal up to polylogarithmic factors for any fixed relative accuracy epsilon is an element of (0,1). In the block-angular case, B is the product of K convex sets ( blocks) and each constraint function is block separable. For such models, an iteration of our method requires a Theta (epsilon) approximate solution of K independent block maximization problems which can be computed in parallel.
For a finite set X, let c be a mapping which assigns to every two-element subset {u, v} of X a nonnegative real number c(u, v), the cost of {u, v}. For tau is an element of R, tau greater than or equal to 1, we say th...
详细信息
For a finite set X, let c be a mapping which assigns to every two-element subset {u, v} of X a nonnegative real number c(u, v), the cost of {u, v}. For tau is an element of R, tau greater than or equal to 1, we say that the pair (X, c) satisfies the tau -inequality ("relaxed triangle inequality") if c(u, v) less than or equal to tau (c(u, w) + c(w, v)) for each three-element subset {u, v, w} of X. For fixed tau greater than or equal to 1, we denote by Delta tauTSP the Traveling Salesman Problem (TSP) restricted to inputs (X, c) satisfying the tau -inequality. In a paper of the present author and H.-J. Bandelt [SIAM J Discr Math 8 (1995), 1-16], a heuristic, called the T-3-algorithm, was proposed for the TSP and it was shown that this heuristic is an approximation algorithm for Delta tauTSP with performance guarantee c(approx) less than or equal to (3/2 tau (2) + 1/2 tau )c(min). In the present paper, by means of appropriately refining the T-3-algorithm, an improved performance guarantee of factor tau (2) + tau (instead of 3/2 tau (2) + 1/2 tau) is established (which is best possible for certain refined versions of the T-3-algorithm). This settles a conjecture of Andreae and Bandelt. Also, related results are derived and examples are given which shed light on the original (unrefined) T-3-algorithm and the improved version presented here. (C) 2001 John Wiley & Sons, Inc.
Inferring evolutionary trees has long been a challenging problem for both biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. ...
详细信息
Inferring evolutionary trees has long been a challenging problem for both biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quartet topologies) and then recombining these inferred quartet topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.
We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V,E) where node nu is an element of V can be upgraded at a cost of c(nu). This upgrade reduces the delay of each lin...
详细信息
ISBN:
(纸本)3540651950
We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V,E) where node nu is an element of V can be upgraded at a cost of c(nu). This upgrade reduces the delay of each link emanating from nu. The goal is to find a minimum cost set of nodes to be upgraded so that the resulting network has a good performance. The performance is measured by the bottleneck weight of a constrained forest defined by a proper function (Goemans and Williamson, SIAM J. Comput. 24 (1995) 296-317). These problems are a generalization of the node weighted constrained forest problems studied by Klein and Ravi (J. algorithms 19 (1995) 104-115). The main result of the paper is a polynomial-time approximation algorithm for this problem with performance guarantee of 2 ln(roote/2.\K\), where K:={nu: f({v}) = 1} is the set of terminals given by the proper function f. We also prove that the performance bound is tight up to small constant factors by providing a lower bound of In \K\. Our results are obtained by extending the elegant solution based decomposition technique of (Klein and Ravi, J. algorithms 19 (1995) 104-115) for approximating node weighted constrained forest problems. These results obtained extend those in (Klein and Ravi, J. algorithms 19 (1995) 104-115, Krumke et al., Lecture Notes in Comput. Sci., Vol. 1197, 1996, pp. 293-307). (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论