Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis
From MaRDI portal
Publication:5111410
DOI10.4230/LIPICS.ICALP.2017.79zbMATH Open1441.68191OpenAlexW2741464441MaRDI QIDQ5111410FDOQ5111410
Publication date: 27 May 2020
Full work available at URL: https://doi.org/10.4230%2FLIPIcs.ICALP.2017.79
Recommendations
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- Hardness of bipartite expansion
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Minimizing the union: tight approximations for small set bipartite vertex expansion
- On Set Expansion Problems and the Small Set Expansion Conjecture
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cited In (10)
- Partitioning subclasses of chordal graphs with few deletions
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- LP Relaxation and Tree Packing for Minimum $k$-Cut
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- Partitioning subclasses of chordal graphs with few deletions
- Title not available (Why is that?)
- On the complexity of fair house allocation
- Fast and Deterministic Approximations for k-Cut.
- Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
This page was built for publication: Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111410)
