Metraipolis › archive › dc_fc231da6ea6e
Smoothed analysis of stability radii for the assignment problem — arXiv:2611.01584
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01584
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:31:45.227Z
- SHA-256 of the archived text
e02d83064cd324c3961c6b0d4f7917b53740d467afbbdb1a857d12560958d40a- Stable URL of this page
https://metraipolis.com/documento/dc_fc231da6ea6e
How to cite
Smoothed analysis of stability radii for the assignment problem — arXiv:2611.01584 — arXiv (en), https://arxiv.org/abs/2611.01584 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fc231da6ea6e (Metraipolis archive dc_fc231da6ea6e, sha256 e02d83064cd324c3961c6b0d4f7917b53740d467afbbdb1a857d12560958d40a)
BibTeX
@misc{dcfc231da6ea6e,
title = {Smoothed analysis of stability radii for the assignment problem — arXiv:2611.01584},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01584},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fc231da6ea6e; sha256 e02d83064cd324c3961c6b0d4f7917b53740d467afbbdb1a857d12560958d40a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01584. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Every linear program can tolerate small changes to its costs and still yield a solution of the original problem. The size of this tolerance measures how robust an optimal decision is to noise or numerical error, and how much regularization the problem can support. Classical sensitivity analysis can determine this tolerance only from an optimal solution. This paper provides a priori lower bounds on two measures of this tolerance -- the optimality gap and the $\infty$-norm stability radius -- for the $n$-by-$n$ linear assignment problem over the Birkhoff polytope. The bounds derive from a smoothed analysis, which adds Gaussian noise with standard deviation of at least $\sigma$ in every direction to an arbitrary base cost. At every fixed confidence level, uniformly over the base cost, both quantities are at least of order $\sigma/(n\sqrt{\log n})$. The radius bound is asymptotically sharp. Under isotropic noise, the worst case occurs when every assignment has equal cost, and in this case, a scaled stability radius converges in distribution to a standard exponential variable.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Data Structures and Algorithms (cs.DS); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2611.01584 — 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-03T11:04:22.237Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).