Inapproximability of Maximum Weighted Edge Biclique and Its Applications

DOI10.1007/978-3-540-79228-4_25zbMath1139.68395arXiv0704.0468OpenAlexW1794289031MaRDI QIDQ3502654

Jinsong Tan

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0704.0468

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

The biclique k-clustering problem in bipartite graphs and its application in bioinformatics ⋮ 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 ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Unnamed Item ⋮ Parameterized Algorithms for Maximum Edge Biclique and Related Problems ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ Solving the maximum edge biclique packing problem on unbalanced bipartite graphs ⋮ Markov chain methods for the bipartite Boolean quadratic programming problem ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Maximal-sum submatrix search using a hybrid constraint programming/linear programming approach ⋮ The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

Cites Work

• Unnamed Item
• Correlation clustering
• The maximum edge biclique problem is NP-complete
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Algorithmic and complexity issues of three clustering methods in microarray data analysis
• On Bipartite and Multipartite Clique Problems
• Managing Broader Product Lines through Delayed Differentiation Using Vanilla Boxes
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Relations between average case complexity and approximation complexity
• Learning Theory and Kernel Machines

This page was built for publication: Inapproximability of Maximum Weighted Edge Biclique and Its Applications