A primal-dual approximation algorithm for the facility location problem with submodular penalties

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

zbMATH Keywords

approximation algorithmsubmodular functionfacility location problem

Mathematics Subject Classification ID

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