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

DOI10.1007/S10107-006-0704-XMaRDI QIDQ2494518zbMATH OpenOpenAlexFDO

Authors Jiawei 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

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

Recommendations

• Approximating the two-level facility location problem via a quasi-greedy approach
• Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach
• Approximation Algorithms for Metric Facility Location Problems
• scientific article; zbMATH DE number 1947060
• Improved Combinatorial Algorithms for Facility Location Problems

Cites work

• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• 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
• A dual-based optimization procedure for the two-echelon uncapacitated facility location problem
• A greedy approximation algorithm for the group Steiner problem
• A new greedy approach for facility location problems
• A note on the maximization version of the multi-level facility location problem
• A Plant and Warehouse Location Problem
• A threshold of ln n for approximating set cover
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• An approximation algorithm for the maximization version of the two level uncapacitated facility location problem
• Approximation Algorithms for Directed Steiner Problems
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Cost-Distance: Two Metric Network Design
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Greedy Strikes Back: Improved Facility Location Algorithms
• Heuristics for the fixed cost median problem
• scientific article; zbMATH DE number 1670526 (Why is no real title available?)
• scientific article; zbMATH DE number 1253065 (Why is no real title available?)
• scientific article; zbMATH DE number 1947060 (Why is no real title available?)
• scientific article; zbMATH DE number 2038706 (Why is no real title available?)
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 1833402 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• Improved approximation algorithms for multilevel facility location problems
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Combinatorial Algorithms for Facility Location Problems
• On a combinatorial game
• On the Two-Level Uncapacitated Facility Location Problem
• Uncapacitated facility location: General solution procedure and computational experience

Cited in

(47)

• A cost-sharing method for an economic lot-sizing game
• A cross-monotonic cost sharing method for the facility location game with service installation costs
• A new mixed integer linear programming model for the multi level uncapacitated facility location problem
• An improved approximation algorithm for the k-level facility location problem with soft capacities
• Multi-level facility location problems
• Integer linear programming models for grid-based light post location problem
• An improved per-scenario bound for the two-stage stochastic facility location problem
• An approximation algorithm for the k-level facility location problem with outliers
• An approximation algorithm for stochastic multi-level facility location problem with soft capacities
• Soft-capacitated facility location game
• LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem
• Approximation algorithms for \(k\)-level stochastic facility location problems
• Approximation algorithms for the fault-tolerant facility location problem with penalties
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties)
• Combinatorial approximation algorithms for the robust facility location problem with penalties
• Approximation algorithms for the stochastic priority facility location problem
• An approximation algorithm for the two-stage distributionally robust facility location problem
• Approximation Algorithms for the Robust Facility Location Problem with Penalties
• Multi-level facility location as the maximization of a submodular set function
• A General k-Level Uncapacitated Facility Location Problem
• An approximation algorithm for the dynamic facility location problem with submodular penalties
• An approximation algorithm for the k-level concentrator location problem
• Improved approximation algorithms for the robust fault-tolerant facility location problem
• 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
• A primal-dual 3-approximation algorithm for the stochastic facility location problem with submodular penalties
• Bilevel optimization: theory, algorithms, applications and a bibliography
• Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
• A per-scenario bound for the two-stage stochastic facility location problem with linear penalty
• Non-metric Multicommodity and Multilevel Facility Location
• The vendor location problem
• Approximating the two-level facility location problem via a quasi-greedy approach
• Inapproximability of the multi-level uncapacitated facility location problem
• Robust network function virtualization
• An approximation algorithm for the k-level stochastic facility location problem
• An approximation algorithm for the k-level capacitated facility location problem
• A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
• Approximation algorithms for the robust/soft-capacitated 2-level facility location problems
• A polynomial-time exact algorithm for the connected k-facility location problem on trees
• Fault-tolerant concave facility location problem with uniform requirements
• 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 the multi-level economic lot-sizing game
• Approximation algorithms for the priority facility location problem with penalties
• Approximation algorithm for facility location with service installation costs
• A new approximation algorithm for the multilevel facility location problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494518)