Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis
From MaRDI portal
(Redirected from Publication:5111410)
Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
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
Cited in
(18)- Partitioning subclasses of chordal graphs with few deletions
- Minimizing the union: tight approximations for small set bipartite vertex expansion
- Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Approximations and hardness of covering and packing partially ordered items
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- Partitioning subclasses of chordal graphs with few deletions
- The strongish planted clique hypothesis and its consequences
- Parameterized inapproximability for Steiner orientation by gap amplification
- Hardness of bipartite expansion
- 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
- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- LP relaxation and tree packing for minimum k-cut
- Fast and deterministic approximations for \(k\)-cut
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)
