We study in this note approximation algorithms for the problem of coloring the vertices of a graph with as few colors as possible, with moderately exponential running times (and using either polynomial or exponential ...
详细信息
We study in this note approximation algorithms for the problem of coloring the vertices of a graph with as few colors as possible, with moderately exponential running times (and using either polynomial or exponential space), better than those of exact computation. Study of approximation is performed with respect to optimality measures, the minimum number of used colors and the maximum number of unused colors. (C) 2009 Elsevier B.V. All rights reserved.
We study approximation of some well-known network design problems such as the TRAVELING SALESMAN PROBLEM (for both minimization and maximization versions) and the MIN STEINER TREE problem by moderately exponential alg...
详细信息
We study approximation of some well-known network design problems such as the TRAVELING SALESMAN PROBLEM (for both minimization and maximization versions) and the MIN STEINER TREE problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled. (C) 2013 Elsevier B.V. All rights reserved.
We first devise a branching algorithm that computes a minimum independent dominating set with running time O*(1.3351(n)) = O*(2(0.417n)) and polynomial space. This improves upon the best state of the art algorithms fo...
详细信息
We first devise a branching algorithm that computes a minimum independent dominating set with running time O*(1.3351(n)) = O*(2(0.417n)) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1 + epsilon, for any epsilon > 0, in a time smaller than the one of exact computation and exponentially decreasing with epsilon. We also propose approximation algorithms with better running times for ratios greater than 3 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se. (C) 2012 Elsevier B.V. All rights reserved.
In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding an embedding of a given graph into a...
详细信息
In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding an embedding of a given graph into a line that minimizes distortion (the DISTORTION problem). For both problems we develop algorithms that work in O(9.363(n)) time and polynomial space. For BANDWIDTH, this improves O*(10(n)) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(c(n)) time we are aware of. As a byproduct, we enhance the O(5(n+o(n)))-time and O*(2(n))-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383(n))-time and space. (c) 2011 Elsevier B.V. All rights reserved.
We present a simple randomized algorithm that approximates the number of satisfying assignments of Boolean formulas in conjunctive normal form. To the best of our knowledge this is the first algorithm which approximat...
详细信息
ISBN:
(纸本)9783939897354
We present a simple randomized algorithm that approximates the number of satisfying assignments of Boolean formulas in conjunctive normal form. To the best of our knowledge this is the first algorithm which approximates #k-SAT for any k >= 3 within a running time that is not only non-trivial, but also significantly better than that of the currently fastest exact algorithms for the problem. More precisely, our algorithm is a randomized approximation scheme whose running time depends polynomially on the error tolerance and is mildly exponential in the number n of variables of the input formula. For example, even stipulating sub-exponentially small error tolerance, the number of solutions to 3-CNF input formulas can be approximated in time O(1.5366(n)). For 4-CNF input the bound increases to O(1.6155(n)). We further show how to obtain upper and lower bounds on the number of solutions to a CNF formula in a controllable way. Relaxing the requirements on the quality of the approximation, on k-CNF input we obtain significantly reduced running times in comparison to the above bounds.
In this paper we consider the CAPACITATED DOMINATING SET problem a generalisation of the DOMINATING SET problem where each vertex v is additionally equipped with a number c(v), which is the number of other vertices th...
详细信息
In this paper we consider the CAPACITATED DOMINATING SET problem a generalisation of the DOMINATING SET problem where each vertex v is additionally equipped with a number c(v), which is the number of other vertices this vertex has the capacity to dominate. We provide an algorithm that solves CAPACITATED DOMINATING SET exactly in O(1.89(n)) time and polynomial space. Despite the fact that the CAPACITATED DOMINATING SET problem is quite similar to the DOMINATING SET problem, we are not aware of any published algorithms solving this problem faster than the straightforward O*(2(n)) solution prior to this paper. This was stated as an open problem at Dagstuhl seminar 08431 in 2008 and IWPEC 2008. We also provide an exponential approximation scheme for CAPACITATED DOMINATING SET which is a trade-off between the time complexity and the approximation ratio of the algorithm. (C) 2011 Elsevier B.V. All rights reserved.
暂无评论