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 (13)

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

This page was built for publication: Approximation properties of NP minimization classes