Exact Algorithms for NP-Hard Problems: A Survey

By G. Woeginger. Combinatorial Optimization, 2001

766 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Theory and Applications of Models of Computation: 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019, Proceedings (2019, methodology): “provide several approximation algorithms for several simple diffusion models [24,26] as well as a more general decreasing cascade model, where a behaviour spreads in a cascading fashion according to a probabilistic rule [25].”
A new algorithm for optimal 2-constraint satisfaction and its implications (2005, methodology): “[21,1,8,29]) explicitly proposed a (2 − ) algorithm for MAX-2-SAT (and/or MAX-CUT) as a benchmark open problem in exact algorithms.”
Combinatorial Optimization on Graphs of Bounded Treewidth (2008, methodology): “As the running time of such algorithms is dominated by the exponential term, the polynomial in n is typically ignored in this branch of algorithm theory and the O* notation is used (see Woeginger [51] for a survey).”
Entrusting Private Computation and Data to Untrusted Networks (2013, unknown): “clusters [5], [31], [35], [45].”
The Algorithm Design Manual (2020, background): “[Woe03] G. Woeginger.”
Set Partitioning via Inclusion-Exclusion (2009, background): “2), and the possibility of ever arriving within a polynomial factor of time 2, for example for Chromatic Number, has been a well-known open problem [48].”