Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty

DOI10.1007/978-3-642-38768-5_27zbMath1381.90053OpenAlexW93178413MaRDI QIDQ4925246

Yu Li, Dong-lei Du, Da-Chuan Xu, Nai-Hua Xiu

Publication date: 11 June 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38768-5_27

zbMATH Keywords

approximation algorithmsubmodular functionfacility location problemLP rounding

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (10)

Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Approximation Algorithms for the Robust Facility Location Problem with Penalties ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ Improved approximation algorithms for the facility location problems with linear/submodular penalties ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties ⋮ Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties) ⋮ Concave connection cost facility location and the star inventory routing problem

This page was built for publication: Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty