Approximation Algorithms for Metric Facility Location Problems

DOI10.1137/S0097539703435716zbMATH Open1151.90590OpenAlexW1973529814MaRDI QIDQ3434992FDOQ3434992

Authors: Mohammad Mahdian, Yinyu Ye, Jiawei Zhang 

Publication date: 3 May 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703435716

Recommendations

• scientific article; zbMATH DE number 1947060
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• scientific article; zbMATH DE number 2086926
• scientific article; zbMATH DE number 1559542
• scientific article; zbMATH DE number 1187151

zbMATH Keywords

linear programmingapproximation algorithmsfacility location problemgreedy method

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Cited In (87)

• Approximation algorithms for the stochastic priority facility location problem
• Fast bounding procedures for large instances of the simple plant location problem
• Approximation of the competitive facility location problem with MIPs
• Title not available (Why is that?)
• An approximation algorithm for the dynamic facility location problem with submodular penalties
• Title not available (Why is that?)
• Approximation algorithms for the fault-tolerant facility placement problem
• Capacitated domination problem
• Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks
• An approximation algorithm for the \(k\)-level capacitated facility location problem
• Fault-tolerant concave facility location problem with uniform requirements
• Cost-effective designs of fault-tolerant access networks in communication systems
• Deterministic sampling algorithms for network design
• Black-box reductions for cost-sharing mechanism design
• Approximation algorithm for facility location with service installation costs
• A cost-sharing method for an economic lot-sizing game
• Title not available (Why is that?)
• Approximating \(k\)-median via pseudo-approximation
• A new approximation algorithm for the multilevel facility location problem
• Improved approximation algorithms for the robust fault-tolerant facility location problem
• Title not available (Why is that?)
• LP-based approximation algorithms for capacitated facility location
• A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties
• Beyond Moulin mechanisms
• An improved per-scenario bound for the two-stage stochastic facility location problem
• Approximation algorithms for soft-capacitated facility location in capacitated network design
• A cross-monotonic cost sharing method for the facility location game with service installation costs
• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• Integrality gaps for strengthened linear relaxations of capacitated facility location
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Improved approximation algorithms for multilevel facility location problems
• An approximation algorithm for the dynamic facility location problem with outliers
• Title not available (Why is that?)
• Approximation algorithms for the metric labeling problem via a new linear programming formulation
• Soft-capacitated facility location game
• Title not available (Why is that?)
• An approximation algorithm for the maximization version of the two level uncapacitated facility location problem
• The online prize-collecting facility location problem
• An approximation algorithm for the stochastic fault-tolerant facility location problem
• Automata, Languages and Programming
• 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
• An approximation algorithm for the \(k\)-level stochastic facility location problem
• Approximation algorithm for uniform bounded facility location problem
• A cost-sharing method for an uncapacitated facility location game with penalties
• 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 metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
• A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation
• Capacitated Domination Problem
• An exact cooperative method for the uncapacitated facility location problem
• A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Integrating facility location and production planning decisions
• A mixed integer programming formulation and solution for traffic analysis zone delineation considering zone amount decision
• An approximation algorithm for soft capacitated \(k\)-facility location problem
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Robust fault tolerant uncapacitated facility location
• Approximation algorithms for the transportation problem with market choice and related models
• Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties
• Title not available (Why is that?)
• A cost-sharing method for the multi-level economic lot-sizing game
• An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties
• A distributed O(1)-approximation algorithm for the uniform facility location problem
• Recovery guarantees for exemplar-based clustering
• Title not available (Why is that?)
• Metric location problems with nonshortest service routes
• An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties
• Improved approximation algorithms for constrained fault-tolerant resource allocation
• A per-scenario bound for the two-stage stochastic facility location problem with linear penalty
• Approximating the \(\tau\)-relaxed soft capacitated facility location problem
• Approximation Algorithms for Stochastic and Risk-Averse Optimization
• Improved lower bound for differentially private facility location
• Approximating soft-capacitated facility location problem with uncertainty
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
• Approximation algorithm for the uniform bounded facility problem
• LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem
• Mixed fault tolerance in server assignment: combining reinforcement and backup
• The approximation gap for the metric facility location problem is not yet closed
• Dynamic Sum-Radii Clustering
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties
• Approximation algorithms for the fault-tolerant facility location problem with submodular penalties
• The facility location problem with maximum distance constraint
• Entrepreneurship facility-activation games

This page was built for publication: Approximation Algorithms for Metric Facility Location Problems

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