An introduction to exponential time exact algorithms for solving NP-hard problems

MaRDI QIDQ3109949zbMATH OpenFDO

Authors Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Publication date 26 January 2012

zbMATH Keywords

branch and reducedynamic programming methodexhaustive searchinclusion-exclusion method

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Exact exponential algorithms.
• scientific article; zbMATH DE number 1953201
• scientific article; zbMATH DE number 1405801
• Faster exact solutions for some NP-hard problems.
• Open problems around exact algorithms

Cited in

(12)

• Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
• Moderate exponential-time algorithms for scheduling problems
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• scientific article; zbMATH DE number 6520244 (Why is no real title available?)
• scientific article; zbMATH DE number 3915621 (Why is no real title available?)
• scientific article; zbMATH DE number 1206043 (Why is no real title available?)
• Towards the Actual Relationship Between NP and Exponential Time
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1405801 (Why is no real title available?)
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• New Computational Paradigms
• Exact exponential algorithms.

This page was built for publication: An introduction to exponential time exact algorithms for solving NP-hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3109949)