Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
From MaRDI portal
Publication:3020016
DOI10.1137/080729256zbMath1223.68043MaRDI 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
graph theory; NP-hardness; hardness of approximation; sparsest cut problem; maximum edge biclique problem; minimum linear arrangement problem
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Bi-Covering: Covering Edges with Two Small Subsets of Vertices, Maximum Edge Bicliques in Tree Convex Bipartite Graphs, Unnamed Item, Mining Compressing Sequential Patterns, Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges, The Bipartite QUBO, Unnamed Item, Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking, Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem, A note on a maximum \(k\)-subset intersection problem, Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms, Single machine precedence constrained scheduling is a Vertex cover problem, Markov chain methods for the bipartite Boolean quadratic programming problem, Hardness of approximation for crossing number, On an ordering problem in weighted hypergraphs, Minimum fill-in: inapproximability and almost tight lower bounds, Adversarial topology discovery in network virtualization environments: a threat for ISPs?, The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases, \(d\)-dimensional arrangement revisited, 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, The Complexity Status of Problems Related to Sparsest Cuts, Vertex Cover in Graphs with Locally Few Colors
