Capacitated facility location with outliers and uniform facility costs

• 成果类型: Article; Early Access
• 署名作者: Gupta, Neelima; Dabas, Rajni; Garg, Naveen
• 署名单位: University of Delhi; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02243-y
• 发表日期: 2025
• 关键词: approximation algorithms

摘要

We consider the capacitated facility location problem with outliers when facility costs are uniform. Our main result is the first constant factor approximation for this problem. We give a local search algorithm that requires only 2 operations and is a 6.373 +& varepsilon;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document} approximation. In developing this result we also improve the approximation guarantee of the capacitated facility location problem with uniform facility costs. Our local search algorithm is extremely simple to analyze and is a 3.733+& varepsilon;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}- approximation thus improving on the 4-approximation of Kao [2].