Smoothed analysis of stability radii for the assignment problem
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01584
curl -X POST /api/v1/records/arxiv/2611.01584/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01584/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'