Approximating the two-level facility location problem via a quasi-greedy approach

DOI10.1007/s10107-006-0704-xzbMath1142.90440OpenAlexW3136436047MaRDI QIDQ2494518

Jia-Wei Zhang

Publication date: 28 June 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0704-x

zbMATH Keywords

Approximation algorithmLinear programming relaxationQuasi-greedy approachTwo-level facility location

Mathematics Subject Classification ID

Mixed integer programming (90C11) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (44)

Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ A new mixed integer linear programming model for the multi level uncapacitated facility location problem ⋮ Multi-level facility location as the maximization of a submodular set function ⋮ Approximation algorithms for \(k\)-level stochastic facility location problems ⋮ An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem ⋮ Approximation Algorithms for the Robust Facility Location Problem with Penalties ⋮ Integer linear programming models for grid-based light post location problem ⋮ An approximation algorithm for the \(k\)-level stochastic facility location problem ⋮ An approximation algorithm for the \(k\)-level capacitated facility location problem ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ Robust network function virtualization ⋮ A cost-sharing method for the multi-level economic lot-sizing game ⋮ An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities ⋮ An approximation algorithm for the \(k\)-level concentrator location problem ⋮ Approximation algorithms for the fault-tolerant facility location problem with penalties ⋮ A primal-dual approximation algorithm for the facility location problem with submodular penalties ⋮ Approximation algorithms for the priority facility location problem with penalties ⋮ Improved approximation algorithms for the robust fault-tolerant facility location problem ⋮ A primal-dual approximation algorithm for stochastic facility location problem with service installation costs ⋮ Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location ⋮ Approximation algorithm for facility location with service installation costs ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ A cost-sharing method for an uncapacitated facility location game with penalties ⋮ Approximation algorithms for the robust/soft-capacitated 2-level facility location problems ⋮ Multi-level facility location problems ⋮ Fault-tolerant concave facility location problem with uniform requirements ⋮ A per-scenario bound for the two-stage stochastic facility location problem with linear penalty ⋮ A new approximation algorithm for the multilevel facility location problem ⋮ The vendor location problem ⋮ Soft-capacitated facility location game ⋮ An improved per-scenario bound for the two-stage stochastic facility location problem ⋮ A General k-Level Uncapacitated Facility Location Problem ⋮ LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem ⋮ An approximation algorithm for the \(k\)-level facility location problem with outliers ⋮ An approximation algorithm for the stochastic fault-tolerant facility location problem ⋮ Improved approximation algorithms for the facility location problems with linear/submodular penalties ⋮ A cost-sharing method for an economic lot-sizing game ⋮ A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ A cross-monotonic cost sharing method for the facility location game with service installation costs ⋮ Unnamed Item ⋮ Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography ⋮ Approximation algorithms for the stochastic priority facility location problem ⋮ Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints
• A branch-and-bound algorithm for the multi-level uncapacitated facility location problem
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• Uncapacitated facility location: General solution procedure and computational experience
• An approximation algorithm for the maximization version of the two level uncapacitated facility location problem
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• Improved approximation algorithms for multilevel facility location problems
• A note on the maximization version of the multi-level facility location problem
• A greedy approximation algorithm for the group Steiner problem
• A threshold of ln n for approximating set cover
• Cost-Distance: Two Metric Network Design
• A new greedy approach for facility location problems
• Heuristics for the fixed cost median problem
• A dual-based optimization procedure for the two-echelon uncapacitated facility location problem
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• A Plant and Warehouse Location Problem
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Approximation Algorithms for Directed Steiner Problems
• Improved Combinatorial Algorithms for Facility Location Problems
• On the Two-Level Uncapacitated Facility Location Problem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• On a combinatorial game

This page was built for publication: Approximating the two-level facility location problem via a quasi-greedy approach