The complexity of polynomial-time approximation

DOI10.1007/s00224-007-1346-yzbMath1202.68481OpenAlexW2092838574WikidataQ57359962 ScholiaQ57359962MaRDI QIDQ2464331

Michael R. Fellows, David W. Juedes, Frances A. Rosamond, Li-Ming Cai

Publication date: 19 December 2007

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-1346-y

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (max. 100)

Safe Approximation and Its Relation to Kernelization ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ A Basic Parameterized Complexity Primer ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Confronting intractability via parameters ⋮ Succinct certification of monotone circuits ⋮ Structure of polynomial-time approximation ⋮ Succinct monotone circuit certification: planarity and parameterized complexity ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

This page was built for publication: The complexity of polynomial-time approximation