Metraipolis › archive › dc_7dbd5519c88d
A Tardos-Type Algorithm for Separable Convex Quadratic Programming — arXiv:2610.07465
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.07465
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:40:31.067Z
- SHA-256 of the archived text
52e4fdb0660559b7a41469d064ea5ae1351eca1d6b176eae33b5284979364454- Stable URL of this page
https://metraipolis.com/documento/dc_7dbd5519c88d
How to cite
A Tardos-Type Algorithm for Separable Convex Quadratic Programming — arXiv:2610.07465 — arXiv (en), https://arxiv.org/abs/2610.07465 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7dbd5519c88d (Metraipolis archive dc_7dbd5519c88d, sha256 52e4fdb0660559b7a41469d064ea5ae1351eca1d6b176eae33b5284979364454)
BibTeX
@misc{dc7dbd5519c88d,
title = {A Tardos-Type Algorithm for Separable Convex Quadratic Programming — arXiv:2610.07465},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.07465},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7dbd5519c88d; sha256 52e4fdb0660559b7a41469d064ea5ae1351eca1d6b176eae33b5284979364454},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07465. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give an exact algorithm for continuous separable convex quadratic programming with an integer equality matrix and nonnegative variables. The number of rational arithmetic operations and comparisons is polynomial in the dimensions and the encoding length of the constraint matrix, independently of the right-hand side, linear costs, and all nonnegative quadratic weights. Intermediate rational encodings are polynomial in the complete input. This yields a strongly polynomial algorithm for every integer matrix class with polynomially bounded entry encodings, including arbitrary matrices with entries in $\{0,\pm1\}$. The local solver compresses a quadratic objective on an integer box and solves only the compressed continuous problem. Two-sided proximity on boxes with rational bounds transfers its solution to a nearby original optimum; integer optima are used only in the proof. A single linear program supplies an error bound and a dual potential, while tight-coordinate revelation and fixed feasible anchors ensure termination and control encoding lengths. An explicit lifting extends the result to convex piecewise quadratic functions of signed integer affine features, with operation counts independent of breakpoints and objective coefficients. Applications include continuous multicommodity flow with shared capacities and piecewise quadratic costs of aggregate congestion.
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/2610.07465 — 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-07T13:13:03.910Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).