Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

DOI10.1051/ita:2005041zbMath1085.68056arXivcs/0110025MaRDI QIDQ3374757

Jörg Rothe, Edith Hemaspaandra, Holger Spakowski

Publication date: 22 February 2006

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0110025

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• It is hard to know when greedy is good for finding independent sets
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• The strong exponential hierarchy collapses
• The complexity of Kemeny elections
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• The complexity of optimization problems
• More complicated questions about maxima and minima, and some closures of NP
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Exact complexity of the winner problem for Young elections
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• A threshold of ln n for approximating set cover
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• A Greedy Heuristic for the Set-Covering Problem
• Exact analysis of Dodgson elections
• On the hardness of approximating minimization problems
• The Minimization Problem for Boolean Formulas