Bi-Covering: Covering Edges with Two Small Subsets of Vertices
From MaRDI portal
Publication:4596825
DOI10.1137/16M1082421zbMath1380.90230OpenAlexW2768402024MaRDI QIDQ4596825
Rohit Khandekar, Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Guy Kortsarz
Publication date: 11 December 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1082421
Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (3)
Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ UG-hardness to NP-hardness by losing half ⋮ Tight approximation bounds for maximum multi-coverage
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Derandomized graph products
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Conditional hardness of precedence constrained scheduling on identical machines
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- Subexponential Algorithms for Unique Games and Related Problems
- A Separator Theorem for Chordal Graphs
- Conditional Hardness for Approximate Coloring
- Relations between average case complexity and approximation complexity
- On the power of unique 2-prover 1-round games
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Optimal Long Code Test with One Free Bit
- A deterministic reduction for the gap minimum distance problem
- A characterization of strong approximation resistance
- Approximation algorithms for channel allocation problems in broadcast networks
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
This page was built for publication: Bi-Covering: Covering Edges with Two Small Subsets of Vertices
