Inapproximability of hypergraph vertex cover and applications to scheduling problems

DOI10.1007/978-3-642-14165-2_22zbMATH Open1287.90018OpenAlexW1859357731MaRDI QIDQ3587384FDOQ3587384

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

Recommendations

scientific article; zbMATH DE number 2086690
Vertex cover might be hard to approximate to within $2 - \varepsilon $
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
No small linear program approximates vertex cover within a factor $2 -\varepsilon$

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

Cited In (34)

Nearly optimal NP-hardness of vertex cover on $k$-uniform $k$-partite hypergraphs
Minimizing the sum of weighted completion times in a concurrent open shop
Flexible coloring
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
Inapproximability of $H$-transversal/packing
Hardness of vertex deletion and project scheduling
Vertex cover meets scheduling
Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
Approximability and exact resolution of the multidimensional binary vector assignment problem
Verified Approximation Algorithms
Rainbow coloring hardness via low sensitivity polymorphisms
Title not available (Why is that?)
Approximability and exact resolution of the multidimensional binary vector assignment problem
Complexity and lowers bounds for power edge set problem
Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
Gaussian bounds for noise correlation of resilient functions
Complexity of approximating CSP with balance/hard constraints
Restricted parameter range promise set cover problems are easy
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
Minimum hitting set of interval bundles problem: computational complexity and approximability
Inapproximability of truthful mechanisms via generalizations of the Vapnik-Chervonenkis dimension
Matroid coflow scheduling
Tight approximation bounds for dominating set on graphs of bounded arboricity
Approximation algorithm for prize-collecting vertex cover with fairness constraints
Nearly tight approximation bounds for vertex cover on dense $k$-uniform $ k$-partite hypergraphs
Hardness of vertex deletion and project scheduling
The quest for strong inapproximability results with perfect completeness
Inapproximability of $b$-matching in $k$-uniform hypergraphs
UG-hardness to NP-hardness by losing half
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
Approximating vertex cover in dense hypergraphs
Vertex cover in graphs with locally few colors
On scheduling coflows

This page was built for publication: Inapproximability of hypergraph vertex cover and applications to scheduling problems

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