Metraipolis › archive › dc_b15de8d2e771

A Distributed Accelerated Preconditioned ADMM for Solving Quadratically Regularized Optimal Transport on Bipartite Graphs — arXiv:2610.09512

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09512
License (as archived)
CC0-1.0
Archived
2026-10-08T11:29:01.024Z
SHA-256 of the archived text
503ad23ef7197668d2077ee5f5141bec3168ca59c1aabebaaf26f98e83604314
Stable URL of this page
https://metraipolis.com/documento/dc_b15de8d2e771

How to cite

A Distributed Accelerated Preconditioned ADMM for Solving Quadratically Regularized Optimal Transport on Bipartite Graphs — arXiv:2610.09512 — arXiv (en), https://arxiv.org/abs/2610.09512 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b15de8d2e771 (Metraipolis archive dc_b15de8d2e771, sha256 503ad23ef7197668d2077ee5f5141bec3168ca59c1aabebaaf26f98e83604314)
BibTeX
@misc{dcb15de8d2e771,
  title = {A Distributed Accelerated Preconditioned ADMM for Solving Quadratically Regularized Optimal Transport on Bipartite Graphs — arXiv:2610.09512},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09512},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b15de8d2e771; sha256 503ad23ef7197668d2077ee5f5141bec3168ca59c1aabebaaf26f98e83604314},
  year = {2026}
}

Archived text

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

Optimal transport (OT) has found broad applications in machine learning, economics, and management. Classical OT models, however, are not directly suited to allocation problems with graph-structured connectivity and unbalanced mass. Distributed OT formulations on bipartite graphs address these requirements but are typically solved by ADMM, whose slow convergence limits communication efficiency. We adapt the accelerated preconditioned ADMM (AP-ADMM) to the quadratically regularized distributed OT model and develop DAP-ADMM, a fully distributed algorithm in which each node communicates only with its graph neighbors. For fixed local penalty parameters, we establish global convergence and non-ergodic $O(1/k)$ bounds for both the KKT-residual norm and the primal objective gap. We derive an exact solver-free routine for the interval-constrained projections arising in the local ADMM subproblems. We propose a distributed self-adaptive penalty mechanism that updates node-specific penalties using locally computable KKT-residual components without global aggregation. Numerical experiments confirm the efficiency of the solver-free routine and the practical acceleration of DAP-ADMM over standard distributed ADMM.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.09512 — 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-08T10:29:06.601Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).