The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem

DOI10.1007/978-3-319-18263-6_7zbMATH Open1457.68306OpenAlexW632518231MaRDI QIDQ3453284FDOQ3453284

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

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

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)

Cites Work

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Title not available (Why is that?)
• An optimal bifactor approximation algorithm for the metric 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
• Submodular Function Minimization under Covering Constraints
• The submodular joint replenishment problem
• Network design for information networks
• Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization
• Title not available (Why is that?)
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Facility location with hierarchical facility costs

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)