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

DOI10.1080/02331934.2013.793326zbMath1311.90080OpenAlexW2076657481MaRDI QIDQ4981876

Dongxiao Gao, Chen-Chen Wu, Da-Chuan Xu

Publication date: 20 March 2015

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331934.2013.793326

zbMATH Keywords

approximation algorithmsubmodular functionstochastic facility location

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

A per-scenario bound for the two-stage stochastic facility location problem with linear penalty ⋮ Approximation algorithm for stochastic set cover problem

Cites Work

• Approximation algorithms for soft-capacitated facility location in capacitated network design
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A new approximation algorithm for the \(k\)-facility location problem
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Approximating the two-level facility location problem via a quasi-greedy approach
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
• Stochastic Transportation-Inventory Network Design Problem
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem

This page was built for publication: A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties