An approximation algorithm for the dynamic facility location problem with submodular penalties

DOI10.1007/s10255-014-0277-zzbMath1305.90253OpenAlexW2036083900MaRDI QIDQ403471

Chun-Yan Jiang, Gai-Di Li, Zhen Wang

Publication date: 29 August 2014

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10255-014-0277-z

zbMATH Keywords

approximation algorithmsubmodular functiondynamic facility location problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Discrete location and assignment (90B80) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Approximation algorithms for the dynamic \(k\)-level facility location problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for the \(k\)-level capacitated facility location problem
• Approximation algorithm for facility location with service installation costs
• A cost-sharing method for an economic lot-sizing game
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• A cross-monotonic cost sharing method for the facility location game with service installation costs
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Soft-capacitated facility location game
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• The \(k\)-level facility location game
• Approximating the two-level facility location problem via a quasi-greedy approach
• Submodular functions and optimization.
• Approximation Algorithms for Metric Facility Location Problems
• 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
• A Dual-Based Procedure for Dynamic Facility Location
• The Multiperiod Location-Allocation Problem with Relocation of Facilities
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty
• Improved Combinatorial Algorithms for Facility Location Problems
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

This page was built for publication: An approximation algorithm for the dynamic facility location problem with submodular penalties