Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach

DOI10.1016/j.tcs.2014.09.045zbMath1303.68158OpenAlexW1991566967MaRDI QIDQ476861

Chen-Chen Wu, Da-Chuan Xu, Dong-lei Du

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.09.045

zbMATH Keywords

approximation algorithmfacility location problemprimal-dual algorithm

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (3)

An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ Approximation algorithms for \(k\)-level stochastic facility location problems ⋮ Approximation algorithms for the robust/soft-capacitated 2-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 stochastic facility location problem
• A new approximation algorithm for the multilevel facility location problem
• Approximation algorithms for soft-capacitated facility location in capacitated network design
• Geometric algorithms and combinatorial optimization
• A note on maximizing a submodular set function subject to a knapsack constraint
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• A note on the maximization version of the multi-level facility location problem
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A new approximation algorithm for the \(k\)-facility location problem
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Approximating the two-level facility location problem via a quasi-greedy approach
• Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location
• 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
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
• Improved Combinatorial Algorithms for Facility Location Problems
• Stochastic Transportation-Inventory Network Design 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: Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach