Smoothed analysis of stability radii for the assignment problem
Abstract
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 ∞-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 σ 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 σ/(n√(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.
Related
- Real and complex stability radii for a class of transport networks
- Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
- Stability for a formally determined Lorentzian inverse problem
- The Global Asymptotic Stability Problem for Linear MPC Is Undecidable
- The stability conjecture for the Bernoulli problem in dimension four
BibTeX
@misc{friedlander2026smoothed,
title = {{Smoothed analysis of stability radii for the assignment problem}},
author = {Michael P. Friedlander},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01584},
eprint = {2611.01584},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01584},
}
RIS
TY - UNPB
TI - Smoothed analysis of stability radii for the assignment problem
AU - Michael P. Friedlander
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01584
UR - https://arxiv.org/abs/2611.01584
AB - 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 ∞-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 σ 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 σ/(n√(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.
ER -