The problem of computing a matching of maximum weight in a given edge-weighted graph is not known to be P-hard or in RNC. This paper presents two parallel approximation algorithms for this problem. The first is an RNC...
详细信息
The problem of computing a matching of maximum weight in a given edge-weighted graph is not known to be P-hard or in RNC. This paper presents two parallel approximation algorithms for this problem. The first is an RNC-approximation scheme, i.e., an RNC algorithm that computes a matching of weight at least 1 - epsilon times the maximum for any fixed constant epsilon > 0. The other is an NC approximation algorithm achieving an approximation ratio of 1/(2 + epsilon) for any fixed constant epsilon > 0. (C) 2000 Elsevier Science B.V. All rights reserved.
Interval graphs play important roles in analysis of DNA chains in Benzer [S. Benzer, On the topology of the genetic fine structure, Proceedings of the National Academy of Sciences of the United States of America 45 (1...
详细信息
Interval graphs play important roles in analysis of DNA chains in Benzer [S. Benzer, On the topology of the genetic fine structure, Proceedings of the National Academy of Sciences of the United States of America 45 (1959) 1607-1620], restriction maps of DNA in Waterman and Griggs [M.S. Waterman, J.R. Griggs, Interval graphs and maps of DNA, Bulletin of Mathematical Biology 48 (2) (1986) 189-195] and other related areas. In this paper, we study a new combinatorial optimization problem, named the minimum clique partition problem with constrained bounds, in weighted interval graphs. For a weighted interval graph G and a bound B, partition the weighted intervals of this graph G into the smallest number of cliques, such that each clique, consisting of some intervals whose intersection on a real line is not empty, has its weight not beyond B. We obtain the following results: (1) this problem is NP-hard in a strong sense, and it cannot be approximated within a factor 3/2 - epsilon in polynomial time for any epsilon > 0;(2) we design three approximation algorithms with different constant factors for this problem;(3) for the version where all intervals have the same weights, we design an optimal algorithm to solve the problem in linear time. (c) 2007 Elsevier B.V. All rights reserved.
We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem. we are given a set of rectangles...
详细信息
We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem. we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the minimum number of lines parallel to the x and y axes, We provide a 2-approximation algorithm, while the best known approximation ratio for this problem is O(log n). This algorithm is then extended to a 4-approximation algorithm for the rectilinear partitioning problem, which. given an m(x) x m(y) array of nonnegative integers and positive integers v, h, asks to find a set of v vertical and h horizontal lines such that the maximum load of a subrectangle (i.e.. the sum of the numbers in it) is minimized. The best known approximation ratio for this problem is 27. Our approximation ratio 4 is close to the best possible, as it is known to be NP-hard to approximate within any factor less than 2. The results are then extended to the d-dimensional space for d greater than or equal to 2, where a d-approximation algorithm for the stabbing problem and a d(d)-approximation algorithm for the partitioning problem are developed. (C) 2002 Elsevier Science (USA).
We present new combinatorial approximation algorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. The new algorithms further extend ...
详细信息
We present new combinatorial approximation algorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. The new algorithms further extend these approaches by utilizing the natural idea of computing large packings of elements into sets of large size. Our results improve the previously best approximation bounds for the k-set cover problem for all values of ka parts per thousand yen6. The analysis technique used could be of independent interest;the upper bound on the approximation factor is obtained by bounding the objective value of a factor-revealing linear program.
The achromatic number problem is, given a graph G = (V, E), to find the greatest number of colors, Psi(G), in a coloring of the vertices of G such that adjacent vertices get distinct colors and for every pair of color...
详细信息
The achromatic number problem is, given a graph G = (V, E), to find the greatest number of colors, Psi(G), in a coloring of the vertices of G such that adjacent vertices get distinct colors and for every pair of colors some vertex of the first color and some vertex of the second color are adjacent. This problem is NP-complete even for trees. We obtain the following new results using combinatorial approaches to the problem. (1) A polynomial time O(\V\(3/8)) -approximation algorithm for the problem on graphs with girth at least six. (2) A polynomial time 2-approximation algorithm for the problem on trees. This is an improvement over the best previous 7-approximation algorithm. (3) A linear time asymptotic 1.414-approximation algorithm for the problem when graph G is a tree with maximum degree d(\V\), where d : N --> N, such that d (\V\) = O(Psi(G)). For example, d (\V\) = Theta(1) or d (\V\) = Theta (log \V\). (4) A linear time asymptotic 1.118-approximation algorithm for binary trees. We also improve the lower bound on the achromatic number of binary trees. (C) 2006 Elsevier B.V. All rights reserved.
We present efficient fixed-parameter and approximation algorithms for the NP-hard problem of computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Multifurcating trees arise ...
详细信息
We present efficient fixed-parameter and approximation algorithms for the NP-hard problem of computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Multifurcating trees arise naturally as a result of statistical uncertainty in current tree construction methods. The size of an MAF corresponds to the subtree prune-and-regraft distance of the two trees and is intimately connected to their hybridization number. These distance measures are essential tools for understanding reticulate evolution, such as lateral gene transfer, recombination, and hybridization. Our algorithms nearly match the running times of the currently best algorithms for the binary case. This is achieved using a combination of efficient branching rules (similar to but more complex than in the binary case) and a novel edge protection scheme that further reduces the size of the search space the algorithms need to explore.
We study three different de-randomization methods that are often applied to approximate combinatorial optimization problems. We analyze the conditional probabilities method in connection with randomized rounding for r...
详细信息
We study three different de-randomization methods that are often applied to approximate combinatorial optimization problems. We analyze the conditional probabilities method in connection with randomized rounding for routing, packing and covering integer linear programming problems. We show extensions of such methods for non-independent randomized rounding for the assignment problem. The second method, the so-called random walks is exemplified with algorithms for dense instances of some NP problems. Another often used method is the bounded independence technique;we explicit this method for the sparsest cut and maximum concurrent flow problems.
Given a graph with a label set , in which each edge has a label from L, and a source together with a sink , the Minimum Label s-t Cut problem asks to pick a set of labels with minimized cardinality, such that the remo...
详细信息
Given a graph with a label set , in which each edge has a label from L, and a source together with a sink , the Minimum Label s-t Cut problem asks to pick a set of labels with minimized cardinality, such that the removal of all edges with labels in from G disconnects s and t. Let and . The previous best known approximation ratio for this problem in literature is . We present two simple and purely combinatorial approximation algorithms for the problem with ratios and , where is the optimal value of the input instance. The former result gives the first approximation ratio which is sublinear in n for the problem, and in particular applies to the instances with dense graphs (e.g., ). The latter result improves the previous ratio , as we can always assume that is a super-constant.
We study the heterogeneous weighted delivery (HWD) problem introduced in [Bartschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n-ver...
详细信息
We study the heterogeneous weighted delivery (HWD) problem introduced in [Bartschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n-vertex edge-weighted graph G, have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1, and is 4 rho-approximable where rho is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O(root logn), closing a problem left open in [Bartschi et al., ATMOS'17]. This algorithm can be turned into an O(k)-approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time (O) over tilde (log(3)n)-approximation algorithm for the general case. (c) 2022 Elsevier B.V. All rights reserved.
Finding a sequence of workpiece orientations such that the number of setups is minimized is an important optimization problem in manufacturing industry. In this paper we present some interesting notes on this optimal ...
详细信息
Finding a sequence of workpiece orientations such that the number of setups is minimized is an important optimization problem in manufacturing industry. In this paper we present some interesting notes on this optimal workpiece setup problem. These notes show that (1) The greedy algorithm proposed in Comput. Aided Des. 35 (2003), pp. 1269-1285 for the optimal workpiece setup problem has the performance ratio bounded by O(ln n - ln ln n+0.78), where n is the number of spherical polygons in the ground set;(2) In addition to greedy heuristic, linear programming can also be used as a near-optimal approximation solution;(3) The performance ratio by linear programming is shown to be tighter than that of greedy heuristic in some cases.
暂无评论