Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis

DOI10.4230/LIPICS.ICALP.2017.79zbMATH Open1441.68191OpenAlexW2741464441MaRDI QIDQ5111410FDOQ5111410

Pasin Manurangsi

Publication date: 27 May 2020

Full work available at URL: https://doi.org/10.4230%2FLIPIcs.ICALP.2017.79

zbMATH Keywords

hardness of approximationsmall set expansion hypothesis

Mathematics Subject Classification ID

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)