Metraipolis › archive › dc_ff656c15b01f
Exact penalties for maximum-edge bicliques in bipartite graphs — arXiv:2611.07239
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.07239
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:52:06.730Z
- SHA-256 of the archived text
aec3b0b3ff39597bd3c09ce112989513fdc762f0532a5e90e6db78eed35d735a- Stable URL of this page
https://metraipolis.com/documento/dc_ff656c15b01f
How to cite
Exact penalties for maximum-edge bicliques in bipartite graphs — arXiv:2611.07239 — arXiv (en), https://arxiv.org/abs/2611.07239 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ff656c15b01f (Metraipolis archive dc_ff656c15b01f, sha256 aec3b0b3ff39597bd3c09ce112989513fdc762f0532a5e90e6db78eed35d735a)
BibTeX
@misc{dcff656c15b01f,
title = {Exact penalties for maximum-edge bicliques in bipartite graphs — arXiv:2611.07239},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.07239},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ff656c15b01f; sha256 aec3b0b3ff39597bd3c09ce112989513fdc762f0532a5e90e6db78eed35d735a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07239. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Given a bipartite graph $G$, we denote by $g(G)$ the largest product $|A||B|$ over pairs of vertex sets $A$ and $B$, one on each side, with no edge between them. These pairs are the bicliques of the bipartite complement of $G$; hence, computing $g(G)$ is the maximum-edge biclique problem, which is NP-hard, as shown by Peeters in 2003. Gillis and Glineur characterized it by a continuous quadratic program, in which a large enough penalty on the edges of $G$ makes the global maximizers correspond to the maximum pairs and the local maximizers to the maximal ones. We propose a new threshold for the penalty, which depends only on $g(G)$. For any penalty at or above it, the global maximizers correspond exactly to the maximum pairs, and every local maximizer with positive value corresponds to a maximal pair. This threshold is never larger than theirs and is sharp up to an additive $1/2$. Spectral and semidefinite bounds give computable penalties; in experiments, a simple local ascent succeeds far more often with the semidefinite one than with the earlier thresholds, although on our graphs that bound already reveals $g(G)$. The penalty formulation, whose optimal value is $\sqrt{g(G)}/2$, is also a copositive formulation of $g(G)$. Strengthening a semidefinite bound of Laurent, Polak and Vargas with the completely positive cone gives exactly $\sqrt{g(G)}/2$, while the doubly nonnegative strengthening is already inexact on six vertices. Finally, Pólya's linear programming approximations of the copositive cone become finite at an explicit level and converge to $\sqrt{g(G)}/2$ without ever being exact.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.07239 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:23:27.655Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).