Inapproximability of hypergraph vertex cover and applications to scheduling problems
From MaRDI portal
Publication:3587384
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)
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\)
Cited in
(34)- On scheduling coflows
- 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
- Vertex cover meets scheduling
- Hardness of vertex deletion and project scheduling
- Inapproximability of \(H\)-transversal/packing
- 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
- scientific article; zbMATH DE number 7566049 (Why is no real title available?)
- Approximability and exact resolution of the multidimensional binary vector assignment problem
- Complexity and lowers bounds for power edge set problem
- Gaussian bounds for noise correlation of resilient functions
- Complexity of approximating CSP with balance/hard constraints
- Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
- 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
- Tight approximation bounds for dominating set on graphs of bounded arboricity
- Matroid coflow scheduling
- 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
- Approximating vertex cover in dense hypergraphs
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
- Vertex cover in graphs with locally few colors
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)
