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
Exact algorithms via monotone local search
Fomin F., Gaspers S., Lokshtanov D., Saurabh S.  Journal of the ACM 66 (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?
Other reviews under "Search Process": Date
Query intent mining with multiple dimensions of web search data
Jiang D., Leung K., Ng W.  World Wide Web 19(3): 475-497, 2016. Type: Article
Nov 11 2016
Personalized concept-based search on the linked open data
Sah M., Wade V.  Journal of Web Semantics 3632-57, 2016. Type: Article
Jun 9 2016
The Mannheim Search Join Engine
Lehmberg O., Ritze D., Ristoski P., Meusel R., Paulheim H., Bizer C.  Journal of Web Semantics 35, Part 3, 159-166, 2015. Type: Article
Mar 14 2016

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy