Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
From MaRDI portal
Publication:4441898
DOI10.1137/S0097539703405754zbMath1044.90056OpenAlexW1978117135WikidataQ56519779 ScholiaQ56519779MaRDI QIDQ4441898
David B. Shmoys, Fabián A. Chudak
Publication date: 8 January 2004
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539703405754
Continuous location (90B85) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)
Related Items
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties, Combinatorial approximation algorithms for the robust facility location problem with penalties, Beyond Moulin mechanisms, An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution, Improved Approximation Algorithm for Fault-Tolerant Facility Placement, The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem, Approximation algorithms for facility location problems with a special class of subadditive cost functions, Approximation algorithm for uniform bounded facility location problem, LP-based approximation for uniform capacitated facility location problem, Approximation algorithms for \(k\)-level stochastic facility location problems, Approximation Algorithms for the Robust Facility Location Problem with Penalties, Solving Facility Location Problem Based on Duality Approach, An approximation algorithm for the \(k\)-level stochastic facility location problem, Agile optimization for a real‐time facility location problem in Internet of Vehicles networks, An approximation algorithm for the dynamic facility location problem with outliers, Min Sum Edge Coloring in Multigraphs Via Configuration LP, An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities, Approximation algorithms for the fault-tolerant facility location problem with penalties, Approximation algorithm for squared metric facility location problem with nonuniform capacities, Approximation algorithms for the fault-tolerant facility location problem with submodular penalties, The facility location problem with maximum distance constraint, Recovery guarantees for exemplar-based clustering, An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions, Approximation algorithm for squared metric two-stage stochastic facility location problem, A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties, Approximation Algorithms for Stochastic and Risk-Averse Optimization, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Approximation algorithms for the fault-tolerant facility placement problem, A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem, Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms, LP-Based Algorithms for Capacitated Facility Location, On the Location and p-Median Polytopes, Graph clustering, An efficient heuristic approach for a multi-period logistics network redesign problem, Integrated Supply Chain Management via Randomized Rounding, 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 \(k\)-product uncapacitated facility location problem, LP-rounding algorithms for the fault-tolerant facility placement problem, Approximation Algorithm for the Uniform Bounded Facility Problem, Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties, Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties, A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem, Approximation algorithms for the robust facility leasing problem, Robust fault tolerant uncapacitated facility location, A distributed O(1)-approximation algorithm for the uniform facility location problem, 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, Improved approximation algorithms for capacitated facility location problems, Soft-capacitated facility location game, Approximating the two-level facility location problem via a quasi-greedy approach, An approximation algorithm for a facility location problem with stochastic demands and inventories, An improved per-scenario bound for the two-stage stochastic facility location problem, Near-optimal solutions to large-scale facility location problems, Approximating the \(\tau\)-relaxed soft capacitated facility location problem, A General k-Level Uncapacitated Facility Location Problem, Integrating facility location and production planning decisions, On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem, A local search approximation algorithm for a squared metric \(k\)-facility location problem, Approximation algorithms for the transportation problem with market choice and related models, Heuristics for the dynamic facility location problem with modular capacities, Mixed fault tolerance in server assignment: combining reinforcement and backup, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, 2-level station location for bike sharing, Approximating $k$-Median via Pseudo-Approximation, LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem, An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties, 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 systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems, A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties, A 6.55 factor primal-dual approximation algorithm for the connected facility location problem, An LP rounding algorithm for approximating uncapacitated facility location problem with 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, Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem, Unnamed Item, Improved approximation algorithms for constrained fault-tolerant resource allocation, Improved approximation algorithms for solving the squared metric \(k\)-facility location problem, Improved approximation algorithms for multilevel facility location problems, Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties), Concave connection cost facility location and the star inventory routing problem
