Paired approximation problems and incompatible inapproximabilities

MaRDI QIDQ5417691zbMATH OpenFDO

Authors David Eppstein

Publication date 22 May 2014

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
• scientific article; zbMATH DE number 1839451
• Primal-dual approximation algorithms for a packing-covering pair of problems
• On the complexity of approximating the independent set problem
• Complexity of approximating bounded variants of optimization problems

Cited in

(4)

• Inapproximability of maximal strip recovery
• Improved approximations for hard optimization problems via problem instance classification
• On the approximability of graph visibility problems
• Structural properties of hard metric TSP inputs (extended abstract)

This page was built for publication: Paired approximation problems and incompatible inapproximabilities

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