A natural family of optimization problems with arbitrarily small approximation thresholds

DOI10.1016/S0020-0190(98)00169-0zbMATH Open1339.68118OpenAlexW2052188732MaRDI QIDQ293457FDOQ293457

Authors: Venkatesan Guruswami, C. Pandu Rangan 

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

Recommendations

• scientific article; zbMATH DE number 1789921
• scientific article; zbMATH DE number 847149
• On the complexity of approximating the independent set problem
• The inapproximability of non-NP-hard optimization problems.
• Complexity of approximating bounded variants of optimization problems

zbMATH Keywords

computational complexityapproximation algorithmNP-hardnesshardness of approximationapproximation thresholdedge dominationindependent set problemPTAStotal graphs

Mathematics Subject Classification ID

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

Cites Work

• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Proof verification and the hardness of approximation problems
• Title not available (Why is that?)
• Edge Dominating Sets in Graphs
• Minimum Edge Dominating Sets
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• On the complexity of variations of mixed domination on graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293457)