Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems

DOI10.1007/978-3-642-14165-2_22zbMath1287.90018OpenAlexW1859357731MaRDI QIDQ3587384

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_22

Mathematics Subject Classification ID

Hypergraphs (05C65) Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (27)

Verified Approximation Algorithms ⋮ Approximability and exact resolution of the multidimensional binary vector assignment problem ⋮ Complexity of approximating CSP with balance/hard constraints ⋮ Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints ⋮ Minimum hitting set of interval bundles problem: computational complexity and approximability ⋮ Tight approximation bounds for dominating set on graphs of bounded arboricity ⋮ Minimizing the sum of weighted completion times in a concurrent open shop ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Flexible coloring ⋮ Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension ⋮ Complexity and lowers bounds for power edge set problem ⋮ On scheduling coflows ⋮ Approximating vertex cover in dense hypergraphs ⋮ Nearly tight approximation bounds for vertex cover on dense $k$-uniform $ k$-partite hypergraphs ⋮ Restricted parameter range promise set cover problems are easy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ Select and permute: an improved online framework for scheduling to minimize weighted completion time ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs ⋮ UG-hardness to NP-hardness by losing half ⋮ Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems

This page was built for publication: Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems