CS Paper Radar

Smoothed analysis of stability radii for the assignment problem

Michael P. Friedlander

cs.DS math.OCmath.PR ·submitted 2026-11-01 05:10 UTC · v1

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.

Comment
17 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Fairness--Stability Trade-offs in Many-to-One Matching

cs.GT ·2026-08-18 ·Genjie Qin
similarity 0.58
Abstract

We study the trade-off between firm-side fairness and coalition stability in many-to-one matching markets with transferable payments. For a fixed matching $X$, we characterize the largest supportable core factor by a bottleneck financing problem: $α(X)=1/Φ(X)$, where $Φ(X)=\min_{z\ge0}\max_i R_i(X,z)$. This yields a polynomial-time linear program and local sensitivity formulas for one-worker reallocations. We then develop a maximum-edge round algorithm and a broader class of mutual-top safe choices. Every safe execution is EF1 and, with $t=δ(A)$ denoting the minimum positive-edge quality, guarantees $α(X)\ge\max\{t,1/[m-(m-1)t]\}$ and $SW(X)/OPT\geq t+(1-t)/m$. These bounds give finite-firm lower and upper bounds for the EF1--core minimax frontier, with exact results for two firms and for three firms when $δ\le1/2$; as the number of firms grows, the tight scale-free stability rate is $δ$. We also extend the financing formulation to stronger $EFX^+$ fairness and capacity-constrained markets.

0.16

A $(3+ε)$-Approximation for Fair $k$-Means and a Matching Lower Bound

cs.CG cs.LG ·2026-09-07 ·Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding
theory similarity 0.58
Abstract

Fair clustering aims to prevent algorithmic bias against protected groups. We study Euclidean fair $k$-means, in which the proportion of each protected group in every cluster lies between prescribed lower and upper bounds. Because these constraints violate the nearest-center assignment property, center selection is coupled with point assignment. We introduce the drift-regularized relaxation, a new convex relaxation solved by a modified Frank-Wolfe method with linear-programming iterations, whose optimality condition controls the cost of converting its solution into $k$ fair clusters. Combined with any $ρ$-approximation algorithm for weighted $k$-means, the relaxation yields an exactly fair fractional solution of cost at most $2ρ+1+ε$ times the fractional optimum, improving the previous ratio $1+4ρ+ε$. In fixed dimension, this improves the best known ratio from $5+O(ε)$ to $3+O(ε)$. The fractional solution can be rounded to an integral one without changing the centers or increasing the cost, at a bounded additive violation of the fairness bounds. We also show that a $(3-δ)$-approximation is NP-hard for every fixed $δ>0$, even on the line with fractional assignments, so $3$ is the exact approximation threshold for fractional fair $k$-means in fixed dimension. The same guarantees hold for $k$-sparse Wasserstein barycenters, a special case of fractional fair $k$-means. More generally, they hold whenever every cluster must satisfy given homogeneous linear inequalities in the fractions of its points, such as a bound on the ratio between two groups or on the average of a numerical attribute in every cluster.

0.09

A Constant-Factor Approximation for Capacitated Facility Location with Outliers

cs.DS ·2026-11-03 ·Rajni Dabas
similarity 0.58
Abstract

We give a deterministic polynomial-time $(60/11+\eps)$-approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities. The algorithm respects both capacities and the outlier budget. Its guarantee, approximately $5.455$, is close to the best known factor $5+\eps$ for capacitated facility location without outliers. The main ingredient is a local-search comparison for a common rejection penalty that retains the signed difference between the algorithm's and the comparator's rejection counts. Ordinary approximation guarantees for the penalty objective do not provide this comparison. We extend the exchange-forest accounting of Bansal, Garg, and Gupta \cite{BGG18} so that a nonnegative assignment remainder pays for rejection and cancels in the final bound. We then merge two penalty assignments whose served counts bracket the outlier quota. Grouping alternating paths by their terminal facility preserves capacities and shares opening costs. These ingredients give a $(20/3+\eps)$-approximation; starting each penalty run from the preceding solution improves the guarantee to $60/11+\eps$.

0.06

Consistent Submodular Maximization with Full Foresight

cs.DS cs.LG ·2026-11-04 ·Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard +2 more
theory similarity 0.57
Abstract

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$, we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

0.44

Exact Sum-of-Radii Clustering under Any Constant Stability

cs.DS ·2026-11-02 ·Shyam Ravichandran, Lev Reyzin
similarity 0.56
Abstract · 27 pages

We establish a separation between the stability thresholds of Minimum Sum-of-Radii (MSR) clustering and two closely related objectives. Known hardness results show that, on general metrics, exact recovery for Minimum Sum-of-Diameters and symmetric $k$-center is hard for every fixed $1<γ<2$, unless NP=RP. We show that MSR admits deterministic polynomial-time exact recovery for every fixed $γ>1$, extending Gao and Reyzin's result for $γ\ge2$. All three results use the same Bilu--Linial stability model: the optimal partition remains uniquely optimal when each pairwise distance is multiplied by any factor in $[1,γ]$, without requiring the perturbed distances to satisfy the triangle inequality. The number of clusters is part of the input. For $1<γ<2$, our algorithm runs in $n^{O((γ-1)^{-5})}$ time. The main structural insight is that a cheap merge in one part of the instance would allow a profitable split elsewhere under a suitable perturbation, contradicting stability. The resulting exchange inequality controls local cluster density, which gives linear growth and hence bounded treewidth in local interaction graphs. We use random partitions to obtain these regions, solve them by dynamic programming, and then derandomize the construction. For rational input and fixed rational $γ>1$, recognizing stability in this model is coNP-complete. Verifying that a supplied partition remains uniquely optimal under all allowed perturbations is coNP-complete for both arbitrary symmetric and metric perturbations.

0.30

On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation

cs.CC math.OC ·2026-08-12 ·Jonah Bondar, Stephen Vavasis
theory similarity 0.56
Abstract

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\barχ_A^*$. Their work builds on Vavasis and Ye's (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\barχ_A$. Monteiro-Tsuchiya (2003) defined the optimal condition number $\barχ_A^*$ as the maximum $\barχ_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) introduced the optimal circuit imbalance measure $κ_W^*$, which serves as a lower bound for $\barχ^*_A$. Instances with artificially large optimal circuit imbalance measures $κ_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $κ_W^*$ grows exponentially in the number of approximation steps. Since $κ_W^*$ lower bounds $\barχ_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.

0.04

Recoverable robust representatives selection problem under interval continuous budgeted uncertainty

cs.DS ·2026-08-16 ·Marcel Jackiewicz, Adam Kasperski, Pawel Zielinski
similarity 0.55
Abstract

In this paper, the recoverable robust representative selection problem is considered, where uncertain second-stage costs are modeled using interval uncertainty with a continuous budget. While the variant under a discrete uncertainty budget is known to be NP-hard, we show that transitioning to a continuous budget fundamentally alters the computational complexity landscape. Specifically, by exploiting the structural properties of the problem under the continuous budget model, we design a strongly polynomial-time algorithm for the general case. Furthermore, we propose an even more efficient strongly polynomial-time algorithm for an important special case.

0.04

The Price of Distributional Robustness in Linear Quadratic Control

eess.SY ·2026-09-15 ·Andrea Martin, Giuseppe Belgioioso
similarity 0.55
Abstract

Distributionally robust (DR) optimization seeks decisions that perform best under the most adverse law within a given ambiguity set, enabling the design of data-driven controllers with strong out-of-sample guarantees in the face of uncertainty. In this paper, we study the conservatism introduced by safeguarding against distributional ambiguity. Specifically, we consider the data-driven Wasserstein DR linear quadratic control problem, and we analyze the suboptimality of the corresponding solution relative to the oracle controller computed with foreknowledge of the underlying unknown uncertainty distribution. We present a sample complexity bound that characterizes the number of samples required to ensure that the true cost of the DR solution exceeds that of the oracle controller by at most a user-defined tolerance factor. Our analysis reveals that the suboptimality of the DR solution increases at most linearly with the Wasserstein radius for sufficiently small distributional ambiguity, and at most quadratically away from this local regime. Numerical simulations validate our bounds on the price of distributional robustness.

0.13