This pager gives a new randomized algorithm which solves 3-SAT in time O(1.32113(n)). The previous best bound is O(1.32216(n)) due to Rolf (J. SAT, 2006). The new algorithm uses the same approach as Iwama and Tamaki (...
详细信息
ISBN:
(纸本)9783642175169
This pager gives a new randomized algorithm which solves 3-SAT in time O(1.32113(n)). The previous best bound is O(1.32216(n)) due to Rolf (J. SAT, 2006). The new algorithm uses the same approach as Iwama and Tamaki (SODA 2004), but exploits the non-uniform initial assignment clue to Hofmeister et al. (STACS 2002) against the Schoning's local search (FOCS 1999).
The SET COVER problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions...
详细信息
The SET COVER problem belongs to a group of hard problems which are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. In recent years, many researchers design exact exponential-time algorithms for problems of that kind. The goal is getting the time complexity still of order O(c(n)), but with the constant c as small as possible. In this work we extend this line of research and we investigate whether the constant c can be made even smaller when one allows constant factor approximation. In fact, we describe a kind of approximation schemes-trade-offs between approximation factor and the time complexity. We use general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate r, one can transform any O*(c(n))-time(1) algorithm for SET COVER into a (1 + lnr)-approximation algorithm running in time O*(C-n/r). We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems. (C) 2009 Elsevier B.V. All rights reserved.
Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a g...
详细信息
Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O* (2(n-z)), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O*(2(n/2)). Another implication is an algorithm for general graphs whose running time is O(1.7088(n)). (C) 2008 Elsevier B.V. All rights reserved.
We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561(n)) and O(1.6737(n)) time, respectively, where n is the number of variable...
详细信息
We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561(n)) and O(1.6737(n)) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting nonweighted models for 2SAT and 3SAT, which run in O(1.3247(n)) and O(1.6894(n)) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices. (c) 2004 Elsevier B.V. All rights reserved.
暂无评论