A primal-dual approximation algorithm for the facility location problem with submodular penalties
From MaRDI portal
Publication:2429335
DOI10.1007/s00453-011-9526-1zbMath1236.90066OpenAlexW1964276725MaRDI QIDQ2429335
Ruixing Lu, Dong-lei Du, Da-Chuan Xu
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9526-1
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)
Related Items
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 ⋮ The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem ⋮ On stochastic \(k\)-facility location ⋮ A cross-monotonic cost-sharing scheme for the concave facility location game ⋮ Fractional 0-1 programming and submodularity ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Approximation Algorithms for the Robust Facility Location Problem with Penalties ⋮ An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ A cost-sharing method for the multi-level economic lot-sizing game ⋮ An approximation algorithm for the dynamic facility location problem with outliers ⋮ An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ Approximation algorithms for the fault-tolerant facility location problem with submodular penalties ⋮ The facility location problem with maximum distance constraint ⋮ Approximation algorithms for the priority facility location problem with penalties ⋮ An approximation algorithm for soft capacitated \(k\)-facility location problem ⋮ A primal-dual approximation algorithm for stochastic facility location problem with service installation costs ⋮ An approximation algorithm for the \(k\)-median warehouse-retailer network design problem ⋮ Unnamed Item ⋮ Approximation algorithms for the dynamic \(k\)-level facility location problems ⋮ Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties ⋮ A per-scenario bound for the two-stage stochastic facility location problem with linear penalty ⋮ A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties ⋮ Approximation algorithms for the multiprocessor scheduling with submodular penalties ⋮ Improved approximation algorithms for the facility location problems with linear/submodular penalties ⋮ A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
Cites Work
- 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
- An improved approximation algorithm for uncapacitated facility location problem with penalties
- An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
- The \(k\)-level facility location game
- Approximating the two-level facility location problem via a quasi-greedy approach
- 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
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
- 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: A primal-dual approximation algorithm for the facility location problem with submodular penalties
