We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices;the extension to directed graphs is also discussed. In this probl...
详细信息
We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices;the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.
An alternative proof for convergence of stochastic approximation algorithms is provided. The proof is completely deterministic, very elementary (involving only basic notions of convergence), and direct in that it rema...
详细信息
An alternative proof for convergence of stochastic approximation algorithms is provided. The proof is completely deterministic, very elementary (involving only basic notions of convergence), and direct in that it remains in a discrete setting. An alternative form of the Kushner-Clark condition is introduced and utilized and the results are the first to prove necessity for general gain sequences in a Hilbert space setting.
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.
暂无评论