Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, 3/2 is the best known approximation ratio achievable in polynomial time for ...
详细信息
Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, 3/2 is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known 3/2 to 33/23 + epsilon > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149-182, 1999b), this yields the same approximation guarantee for n! - O((n - 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result.
Refined Harmonic(RH)is one of the best on-line bin packing *** algorithm was first proposed by Lee&Leen in 1985 and the upper bouund of the worst-case performance ratio has been proved to be 1.63596....In this pap...
详细信息
Refined Harmonic(RH)is one of the best on-line bin packing *** algorithm was first proposed by Lee&Leen in 1985 and the upper bouund of the worst-case performance ratio has been proved to be 1.63596....In this paper,it is proved that 1.63596... is also the lower *** average performance of RH is also studied for the first *** is shown that the average-case performance ratio of RH is 1.28243... under the uniform distribution.
We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently a...
详细信息
We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently active job whenever a new job arrives that has higher ratio of weight to processing time. We prove that the competitive ratio of this simple on-line algorithm is precisely 2. We also show that list scheduling in order of random alpha-points drawn from the same schedule results in an on-line algorithm with competitive ratio (4)/(3). Since its analysis relies on a well-known integer programming relaxation of the scheduling problem, the relaxation has performance guarantee A as well. On the other hand, we show that it is at best an (8)/(7)-relaxation. Copyright (C) 2002 John Wiley Sons, Ltd.
We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0, 1] into a small numb...
详细信息
We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0, 1] into a small number of bins of size b greater than or equal to 1. Its performance is measured by comparing the produced packing against: the optimal offline packing of the list L into bins of size I. We present a complete solution to this problem: For every bin size, b greater than or equal to 1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound rho (b). Moreover, we prove that no online bounded space algorithm can perform better than rho(b) in the worst case. (C) 2002 Elsevier Science (USA). All rights reserved.
This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completi...
详细信息
This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completion time are studied. For the first objective, we present the optimal algorithms for m = 2,3, 4 machine cases. For m greater than or equal to 5, we propose an algorithm with competitive ratio 2 - 1/(m - 1) while the lower bound is 5/3. For the second objective, the optimal algorithm is also given. Furthermore, for a special case, in algorithm with significantly improved competitive ratio is given. (C) 2002 Elsevier Science Ltd. All rights reserved.
A k-partite graph is a graph G = (V-1,...,V-k, E), where V-1,..., V-k are k non-empty disjoint independent sets of vertices. Such a graph is called complete k-partite if E = U-inot equalj V-i x V-j. We discuss three v...
详细信息
A k-partite graph is a graph G = (V-1,...,V-k, E), where V-1,..., V-k are k non-empty disjoint independent sets of vertices. Such a graph is called complete k-partite if E = U-inot equalj V-i x V-j. We discuss three variants of the following optimization problem: given a graph and a non-negative weight function on the vertices and edges, find a minimum weight set of vertices and incident edges whose removal from the graph leaves a complete k-partite graph. All the problems we consider are at least as hard to approximate as the weighted vertex cover problem. We use the local-ratio technique to develop 2-approximation algorithms for the first two variants of the problem. In particular, we present the first (linear time) 2-approximation algorithm for the edge clique complement problem. For other previously studied special cases our 2-approximation algorithms are better in terms of time complexity than the existing 2-approximation algorithms. We use approximation preserving reductions in order to (4 - 4/k)-approximate the third variant of the problem. (C) 2002 Elsevier Science.
We study the variant of the well-known stable roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability is possible. Here w...
详细信息
We study the variant of the well-known stable roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability is possible. Here we consider two of these stability criteria, so-called super-stability and weak stability. We present a linear-time algorithm for finding a super-stable matching if one exists, given a stable roommates instance with ties. This contrasts with the known NP-hardness of the analogous problem under weak stability. We also extend our algorithm to cope with preference lists that are incomplete and/or partially ordered. On the other hand, for a given stable roommates instance with ties and incomplete lists, we show that the weakly stable matchings may be of different sizes and the problem of finding a maximum cardinality weakly stable matching is NP-hard, though approximable within a factor of 2. (C) 2002 Elsevier Science (USA).
Consider two sets B and G of strings of length L with characters from an unbounded alphabet Sigma, i.e., the size of Sigma is not bounded by a constant and has to be taken into consideration as a parameter for input s...
详细信息
Consider two sets B and G of strings of length L with characters from an unbounded alphabet Sigma, i.e., the size of Sigma is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of B is a string that minimizes the maximum of Hamming(1) distance(s, s*) over all string s : s is an element of B. In contrast, a farthest string t* from G maximizes the minimum of Hamming distance(t*,t) over all elements t: t is an element of G. A distinguisher of B from G is a string that is close to every string in B and far away from any string in G. We obtain polynomial time approximation schemes to settle the above problems.
This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M-1, M-2, and M-3. A job is first proces...
详细信息
This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M-1, M-2, and M-3. A job is first processed on M-1 and then is assigned either the route (M-2, M-3) or the route (M-3, M-2). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(n log n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.
This paper considers the semi-on-line versions of scheduling problem P2 \\ C-max. We study the semi-on-line problems with combination of two types of information. Five basic types of partial information are considered...
详细信息
This paper considers the semi-on-line versions of scheduling problem P2 \\ C-max. We study the semi-on-line problems with combination of two types of information. Five basic types of partial information are considered. For two kinds of pairwise combination, we present their respective optimal semi-on-line algorithms which show that combination can admit to construct better algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论