Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Best of 2016 Recommended by Editor Recommended by Reviewer Recommended by Reader
Search
Exact algorithms via monotone local search
Fomin F., Gaspers S., Lokshtanov D., Saurabh S. Journal of the ACM66 (2):1-23,2019.Type:Article
Date Reviewed: Apr 26 2021

Many important problems are NP-complete; this means that, unless P = NP, we cannot have a polynomial-time (feasible) algorithm for solving all instances of this problem. For each such problem, there is an exhaustive search algorithm that requires exponential time.

How can we solve these problems faster? There are two main approaches to answering this question. The parameterized algorithm approach tries to find subclasses for which a feasible algorithm is possible--usually by introducing an integer-valued parameter such that for each value of this parameter, a feasible algorithm is possible for all the instances for which this parameter does not exceed this value. An alternative idea is to find an exponential algorithm--applicable to all the instances--that is faster than exhaustive search.

The authors show, rather unexpectedly, that these two seemingly unrelated approaches are actually strongly related: namely, in many cases, a successful parameterized algorithm can lead to a faster-than-exhaustive-search exponential algorithm. Specifically, the authors consider subset problems, that is, the problems of checking whether in a given n-element set there is a subset satisfying a given property. For example, we are given: a CNF formula with clauses of size at most d, weights assigned to all n variables, and the overall weight W; we want to check the existence of a satisfying vector for which the total weight of all true variables does not exceed W. For such problems, exhaustive search of all 2n subsets takes time ≧2n.

The corresponding parameterized problem is: given a set X and an integer k, can we add at most k elements to X and get a set with the desired property? It turns out that if this “extension” problem can be solved in time O(cknC) (for some constant C), then the original problem can be solved faster than in 2n steps: namely, in time O((2-1/c)n). The authors first prove the existence of a randomized algorithm with this computation time, and then use an innovative pseudo-random generator to design a deterministic algorithm with practically the same complexity: O((2-1/c)n+o(n)).

The results are spectacular. For many problems for which no faster-than-exhaustive-search algorithm was previously known, such algorithms are produced. For many other problems, new exponential algorithms are generated that are faster than all previously known ones.

Reviewer:  V. Kreinovich Review #: CR147250 (2108-0216)
Bookmark and Share
  Editor Recommended
Featured Reviewer
 
 
Search Process (H.3.3 ... )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Search Process": Date
Search improvement via automatic query reformulation
Gauch S., Smith J. ACM Transactions on Information Systems 9(3): 249-280, 1991. Type: Article
Jul 1 1993
Criteria for the selection of search strategies in best-match document-retrieval systems
McCall F., Willett P. International Journal of Man-Machine Studies 25(3): 317-326, 1986. Type: Article
Oct 1 1987
The use of adaptive mechanisms for selection of search strategies in document retrieval systems
Croft W. (ed), Thompson R.  Research and development in information retrieval (, King’s College, Cambridge,1101984. Type: Proceedings
Aug 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy