arXiv preprint ·
Smoothed analysis of stability radii for the assignment problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\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 $σ$ 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\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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
An $\mathsf{FPRAS}$ for Mixed Volumes
Fine-Grained Complexity Across the Computational Phase Transition
Sharper Bounds for Graphical Two-Choice Allocation
On a Class of Non-Local Elliptic-Transport Systems in Score-Guided Probability Flow on $SE(3)$: Score-Singularity Resolution, Space-Time ADN Shift, and Markov Mean-Field Games
Online Algorithms Cannot Find Isolated Perceptron Solutions
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.