Metraipolis › archive › dc_e9733e76742f

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts — arXiv:2609.07204

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.07204
License (as archived)
CC0-1.0
Archived
2026-10-08T14:37:30.474Z
SHA-256 of the archived text
57b9d994a6be583851d48aecb036ca5621ee310aa3ccd9a433076fac792f8ce2
Stable URL of this page
https://metraipolis.com/documento/dc_e9733e76742f

How to cite

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts — arXiv:2609.07204 — arXiv (en), https://arxiv.org/abs/2609.07204 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e9733e76742f (Metraipolis archive dc_e9733e76742f, sha256 57b9d994a6be583851d48aecb036ca5621ee310aa3ccd9a433076fac792f8ce2)
BibTeX
@misc{dce9733e76742f,
  title = {Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts — arXiv:2609.07204},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.07204},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e9733e76742f; sha256 57b9d994a6be583851d48aecb036ca5621ee310aa3ccd9a433076fac792f8ce2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07204. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-23 in cs.DC).
Categorie arXiv: Artificial Intelligence (cs.AI) ; Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.07204 — 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-10-08T13:47:35.211Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).