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

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

Jörg Rothe, Holger Spakowski, Edith Hemaspaandra

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

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ The complexity of computing minimal unidirectional covering sets ⋮ Stability, vertex stability, and unfrozenness for special graph classes

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

This page was built for publication: Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP