The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem

DOI10.1007/978-3-319-18263-6_7MaRDI QIDQ3453284zbMATH OpenOpenAlexFDO

Authors Sin-Shuen Cheung

Publication date 20 November 2015

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-18263-6_7

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• The submodular joint replenishment problem
• Facility location problems with submodular penalties and stochastic demands
• An approximation algorithm for the dynamic facility location problem with submodular penalties
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• An approximation algorithm for the \(k\)-level facility location problem with submodular penalties
• Multi-level facility location as the maximization of a submodular set function
• Approximation algorithms for the priority facility location problem with submodular penalties
• A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties
• On a class of subadditive duals for the uncapacitated facility location problem
• A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties

Cites work

• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 7051222 (Why is no real title available?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A constant approximation algorithm for the one-warehouse multiretailer problem
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization
• Facility location with hierarchical facility costs
• Greedy Strikes Back: Improved Facility Location Algorithms
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Network design for information networks
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Submodular Function Minimization under Covering Constraints
• The submodular joint replenishment problem

Cited in

(2)

• The submodular joint replenishment problem
• Multi-level facility location as the maximization of a submodular set function

This page was built for publication: The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453284)