The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem

DOI10.1007/978-3-319-18263-6_7zbMath1457.68306OpenAlexW632518231MaRDI QIDQ3453284

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) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The submodular joint replenishment problem
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Submodular Function Minimization under Covering Constraints
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Facility location with hierarchical facility costs

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