A natural family of optimization problems with arbitrarily small approximation thresholds

DOI10.1016/S0020-0190(98)00169-0zbMath1339.68118OpenAlexW2052188732MaRDI QIDQ293457

C. Pandu Rangan, Venkatesan Guruswami

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001690?np=y

zbMATH Keywords

computational complexityapproximation algorithmNP-hardnesshardness of approximationPTASapproximation thresholdedge dominationindependent set problemtotal graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

On the complexity of variations of mixed domination on graphs^†

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Minimum Edge Dominating Sets
• Proof verification and the hardness of approximation problems
• Edge Dominating Sets in Graphs

This page was built for publication: A natural family of optimization problems with arbitrarily small approximation thresholds