← 研踪 PaperTrailarXiv:2611.04094 · v1
A Constant-Factor Approximation for Capacitated Facility Location with Outliers
首次提交 2026-11-03 08:08
版本更新 2026-11-03 08:08
雷达观测 2026-11-04 23:40
摘要
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$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 08:08 · 最新观测版本
A Constant-Factor Approximation for Capacitated Facility Location with Outliers
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$.
查看此版本解读 →查看此版本原文 ↗