Abstract
Faster exact solutions for some NP-hard problems
Theoretical Computer Science, Vol.287(2), pp.473-499
7th Annual European Symposium on Algorithms, 7th (Czech Republic, Prague, 16/Jul/1999 - 18/Jul/1999)
Sep/2002
Abstract
This paper considers a number of NP-complete problems, and provides faster algorithms for solving them. The solutions are based on a recursive partitioning of the problem domain, and careful elimination of some of the branches along the search without actually checking them. The time complexity of the proposed algorithms is of the form O(2(epsilonn)) for constant 0 <epsilon <1, where n is the output size of the problem. In particular, such algorithms are presented for the Exact SA T and Exact Hitting Set problems (with epsilon = 0.3212), and for the Exact 3SAT problem (with epsilon = 0.2072). Both algorithms improve on previous ones proposed in the literature. (C) 2002 Elsevier Science B.V. All rights reserved.
Details
- Title
- Faster exact solutions for some NP-hard problems
- Creators
- L Drori (null)David Peleg (null) - 972WIS_INST___83
- Resource Type
- Abstract
- Publication Details
- Theoretical Computer Science, Vol.287(2), pp.473-499; Sep/2002
- Number of pages
- 27
- Language
- English
- DOI
- https://doi.org/10.1016/S0304-3975(01)00257-2
- Conference
- 7th Annual European Symposium on Algorithms, 7th (Czech Republic, Prague, 16/Jul/1999 - 18/Jul/1999)
- Record Identifier
- 993265083803596
Metrics
3 Record Views