.png){kind=icon}
.png){kind=icon}
Return
An Lp-rounding Based Algorithm for Soft Capacitated Facility Location Problem with Submodular Penalties
.png){kind=icon}
PRE
AI
DOI：10.1007/s00224-026-10271-0.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The soft capacitated facility location problem (SCFLP) is a fundamental model in logistics, supply chain management, and network design, capturing the trade-off between facility opening costs and service flexibility under capacity constraints. This paper studies a variant, the soft capacitated facility location problem with submodular penalties (SCFLPSP), where unserved clients incur submodular penalty costs and where each client's demand is integer-splittable across multiple facilities. We develop an LP-rounding-based algorithm that achieves a (lambda R+4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\lambda R + 4)$$\end{document}-approximation, where R=maxi is an element of Ffimini is an element of Ffi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R = \frac{\max _{i \in \mathcal {F}} f_i}{\min _{i \in \mathcal {F}} f_i}$$\end{document}, lambda=R+R2+8R2R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda = \frac{R + \sqrt{R<^>2 + 8R}}{2R}$$\end{document}, and fi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_i$$\end{document} is the opening cost of facility i. When R=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R=1$$\end{document}, that is, when the opening costs are uniform, the approximation ratio simplifies to 6. Extensive experiments on publicly available datasets demonstrate that the proposed algorithm significantly improves computational efficiency compared with optimal solutions while maintaining high solution quality. Moreover, it exhibits more stable performance than greedy and ant colony optimization approaches and provides an explicit approximation guarantee, confirming both its effectiveness and reliability.
Keywords:
Soft capacitated facility location problem
Approximation algorithm
Submodular penalties
LP-rounding