Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
type: Item
instance of: scholarly article
title: Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
zbMATH Open document ID: 1426.68101
DOI: 10.1007/978-3-662-44465-8_35
published in: Mathematical Foundations of Computer Science 2014
publication date: 2014-10-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1406.3247
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6355332
MaRDI profile type: Publication
OpenAlex ID: W2172212024
arXiv ID: 1406.3247
cites work: Twice-Ramanujan Sparsifiers
cites work: The complexity of soft constraint satisfaction
cites work: On generating all solutions of generalized satisfiability problems
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: On the algebraic structure of combinatorial problems
cites work: Closure properties of constraints
cites work: Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
cites work: The approximability of constraint satisfaction problems
cites work: Weak bases of Boolean co-clones
cites work: Function Algebras on Finite Sets
cites work: Q4904144
cites work: The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
cites work: On the Limits of Sparsification
cites work: The complexity of satisfiability problems
cites work: Partial Polymorphisms and Constraint Satisfaction Problems
cites work: Q4414647
Recommended article: The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
Recommended article: Towards the Actual Relationship Between NP and Exponential Time
Recommended article: Relativizations comparing NP and exponential time
Recommended article: On Parameterized Exponential Time Complexity
Recommended article: On parameterized exponential time complexity
Recommended article: Q4606306
Recommended article: ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
Recommended article: New tools and connections for exponential-time approximation
Recommended article: Q3109949
Recommended article: Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
author: Peter Jonsson
author: Victor Lagerkvist
author: Johannes Schmidt
author: Hannes Uppman
description: scientific article; zbMATH DE number 6355332