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