Metraipolis › archive › dc_2b6b33c8d862
Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee — arXiv:2611.06008
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06008
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:36.540Z
- SHA-256 of the archived text
f4e0b0dd6b0fdef26d786892ce09226eed3449f6bc675090348ad8c0651583dc- Stable URL of this page
https://metraipolis.com/documento/dc_2b6b33c8d862
How to cite
Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee — arXiv:2611.06008 — arXiv (en), https://arxiv.org/abs/2611.06008 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2b6b33c8d862 (Metraipolis archive dc_2b6b33c8d862, sha256 f4e0b0dd6b0fdef26d786892ce09226eed3449f6bc675090348ad8c0651583dc)
BibTeX
@misc{dc2b6b33c8d862,
title = {Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee — arXiv:2611.06008},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06008},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2b6b33c8d862; sha256 f4e0b0dd6b0fdef26d786892ce09226eed3449f6bc675090348ad8c0651583dc},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06008. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Partitioning the vertex set of a graph $G=(V,E)$ into clusters is a classical problem in computer science. As vertices within clusters should be well connected and cuts between clusters sparse, Oveis Gharan and Trevisan (SODA 2014, [OGT14]) proposed to measure the partition quality using inner and outer conductance, i.e., the bi-criteria guarantee. Specifically, when partitioning $V$ into vertex-disjoint subsets $P_1,\ldots, P_k$, every subgraph induced by $P_i$ should have high conductance, while the conductance of $P_i$ in $G$ should be low. They studied the existence of such a partition and designed a polynomial-time algorithm achieving this guarantee. For more than a decade, their algorithm remained the only one achieving this guarantee on its output clusters. In this paper, we study faster cluster decomposition algorithms under the same setup as [OGT14] and prove three results: 1. We make their existential result algorithmic: Our algorithms run in nearly-linear time, and achieve the same bi-criteria guarantee as the one in [OGT14] up to constant factors, including the asymptotically tight dependence on $k$. 2. We prove that their existential result holds algorithmically under a much weaker condition on the initial disjoint subsets. To achieve this, we develop a general algorithm framework that boosts the approximation guarantee of a solution: given an $\alpha$-approximate solution to the $k$-way conductance problem, if $\rho_G(k+1)/\rho_G(k)=\Omega\left(\alpha/\varepsilon\right)$, then a $(1+\varepsilon)$-approximate solution can be obtained using only $O(k(1+\log\alpha))$ minimum $s$-$t$ cut computations. 3. We present a nearly-linear time algorithm that finds clusters with the bi-criteria guarantee. Our algorithm has the same guarantee as the one in [OGT14], which, for any unweighted graph of $n$ vertices and $m$ edges, runs in $\widetilde{O}(knm^2)$ time.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.06008 — 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-05T18:21:04.026Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).