Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
From MaRDI portal
Publication:2085735
DOI10.1007/978-3-030-92702-8_4OpenAlexW4285543569MaRDI QIDQ2085735
Jan Marcinkowski, Szymon Dudycz, Pasin Manurangsi
Publication date: 19 October 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-92702-8_4
Cites Work
- Unnamed Item
- Unnamed Item
- Approximating edge dominating set in dense graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Tight approximation ratio for Minimum Maximal Matching
- Approximation hardness of edge dominating set problems
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Graph expansion and the unique games conjecture
- Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
- On the power of unique 2-prover 1-round games
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Edge Dominating Sets in Graphs
- Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
- Bicovering: Covering edges with two small subsets of vertices
- New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set
- Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
- Optimal Long Code Test with One Free Bit
- Towards a proof of the 2-to-1 games conjecture?
- On non-optimally expanding sets in Grassmann graphs
- A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
