Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

DOI10.1007/978-3-662-44465-8_35zbMath1426.68101arXiv1406.3247OpenAlexW2172212024MaRDI QIDQ2922627

No author found.

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.3247

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the algebraic structure of combinatorial problems
• Which problems have strongly exponential complexity?
• Weak bases of Boolean co-clones
• The complexity of soft constraint satisfaction
• The Approximability of Constraint Satisfaction Problems
• On the Limits of Sparsification
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Closure properties of constraints
• On generating all solutions of generalized satisfiability problems
• Twice-Ramanujan Sparsifiers
• Function Algebras on Finite Sets
• The complexity of satisfiability problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• On the complexity of \(k\)-SAT

This page was built for publication: Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis