Approximation properties of NP minimization classes

DOI10.1006/jcss.1995.1031zbMath0837.68028OpenAlexW1976960787MaRDI QIDQ1894448

Phokion G. Kolaitis, Madhukar N. Thakur

Publication date: 29 April 1996

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1031

zbMATH Keywords

descriptive complexity theoryNP optimization problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Safe Approximation and Its Relation to Kernelization ⋮ On fixed-parameter tractability and approximability of NP optimization problems ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Max NP-completeness made easy ⋮ A survey on the structure of approximation classes ⋮ Local approximations for maximum partial subgraph problem. ⋮ atalog: A logic language for expressing search and optimization problems ⋮ Structure of polynomial-time approximation ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Integer programming as a framework for optimization and approximability ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap