Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut

DOI10.1137/080729256zbMath1223.68043OpenAlexW1995472412MaRDI QIDQ3020016

Monaldo Mastrolilli, Ola Svensson, Christoph Ambühl

Publication date: 29 July 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/72e02db1c04aacd1821bc54ad599d6ebe2da39f3

zbMATH Keywords

graph theoryNP-hardnesshardness of approximationsparsest cut problemmaximum edge biclique problemminimum linear arrangement problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (24)

Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges ⋮ The Bipartite QUBO ⋮ Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs ⋮ Scale reduction techniques for computing maximum induced bicliques ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Unnamed Item ⋮ Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem ⋮ Unnamed Item ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Hardness of approximation for crossing number ⋮ A note on a maximum \(k\)-subset intersection problem ⋮ \(d\)-dimensional arrangement revisited ⋮ Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Markov chain methods for the bipartite Boolean quadratic programming problem ⋮ Mining Compressing Sequential Patterns ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Adversarial topology discovery in network virtualization environments: a threat for ISPs? ⋮ On an ordering problem in weighted hypergraphs ⋮ The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

This page was built for publication: Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut