Greedy Strikes Back: Improved Facility Location Algorithms
From MaRDI portal
Publication:4240134
DOI10.1006/jagm.1998.0993zbMath0928.68137OpenAlexW4243637616WikidataQ57568237 ScholiaQ57568237MaRDI QIDQ4240134
Publication date: 9 January 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1998.0993
Related Items
Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems, Improved Approximation Algorithm for Fault-Tolerant Facility Placement, The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem, Unnamed Item, Robust network function virtualization, Problem-driven scenario clustering in stochastic optimization, The facility location problem with maximum distance constraint, Unnamed Item, Unnamed Item, Approximation schemes for \(k\)-facility location, Approximation Algorithms for Stochastic and Risk-Averse Optimization, Unnamed Item, A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Integrated Supply Chain Management via Randomized Rounding, Unnamed Item, Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics, On the cost of essentially fair clusterings, Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties, Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension, A unified framework of FPT approximation algorithms for clustering problems, FPT Approximation for Constrained Metric k-Median/Means, Unnamed Item, A General k-Level Uncapacitated Facility Location Problem, Unnamed Item, On Min-Max r-Gatherings, A local search approximation algorithm for a squared metric \(k\)-facility location problem, Mixed fault tolerance in server assignment: combining reinforcement and backup, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics, Approximation algorithms for hierarchical location problems, A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties, Efficient Black-Box Reductions for Separable Cost Sharing, Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem, Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks, Unnamed Item, On Hop-Constrained Steiner Trees in Tree-Like Metrics, 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, Complexity of single-swap heuristics for metric facility location and related problems, A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Integrality gaps for strengthened linear relaxations of capacitated facility location, A DISTRIBUTED APPROXIMATION ALGORITHM FOR FAULT-TOLERANT METRIC FACILITY LOCATION, A new approximation algorithm for the \(k\)-facility location problem, On the bounded-hop MST problem on random Euclidean instances, An improved approximation algorithm for squared metric \(k\)-facility location, Improved parameterized approximation for balanced \(k\)-median, On stochastic \(k\)-facility location, A hybrid multistart heuristic for the uncapacitated facility location problem, Approximation algorithms for facility location problems with a special class of subadditive cost functions, Clustering through continuous facility location problems, LP-based approximation for uniform capacitated facility location problem, Incremental facility location problem and its competitive algorithms, 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 risk-adjusted two-stage stochastic facility location problem with penalties, An approximation algorithm for the \(k\)-level stochastic facility location problem, Better guarantees for \(k\)-median with service installation costs, An approximation algorithm for the \(k\)-level capacitated facility location problem, Perturbation resilience for the facility location problem, An approximation algorithm for the dynamic facility location problem with submodular penalties, An approximation algorithm for the dynamic facility location problem with outliers, 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, Centrality of trees for capacitated \(k\)-center, Approximation algorithm for squared metric two-stage stochastic facility location problem, On min-max \(r\)-gatherings, \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space, 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, An approximation algorithm for soft capacitated \(k\)-facility location problem, LP-Based Algorithms for Capacitated Facility Location, 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, Dynamic Sum-Radii Clustering, Approximation algorithm for facility location with service installation costs, Data stability in clustering: a closer look, Approximation algorithms for the dynamic \(k\)-level facility location problems, Iterative partial rounding for vertex cover with hard capacities, Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach, A \(k\)-product uncapacitated facility location problem, Polynomial time approximation schemes for clustering in low highway dimension graphs, An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem, Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem, Easy capacitated facility location problems, with connections to lot-sizing, Approximation Algorithms for Single and Multi-Commodity Connected Facility Location, The approximation gap for the metric facility location problem is not yet closed, Local search algorithm for universal facility location problem with linear penalties, 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, Fault-tolerant concave facility location problem with uniform requirements, Approximating \(k\)-hop minimum spanning trees in Euclidean metrics, Non-cooperative facility location and covering games, A new approximation algorithm for the multilevel facility location problem, Kinetic facility location, Approximating \(k\)-hop minimum-spanning trees, Randomized priority algorithms, Improved approximation algorithms for capacitated facility location problems, Soft-capacitated facility location game, Hedging uncertainty: approximation algorithms for stochastic optimization problems, 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, Local search approximation algorithms for the sum of squares facility location problems, Approximating the \(\tau\)-relaxed soft capacitated facility location problem, Incremental algorithms for facility location and \(k\)-median, Integrating facility location and production planning decisions, Approximation algorithms for the transportation problem with market choice and related models, 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, Approximation algorithms for soft-capacitated facility location in capacitated network design, On the power of static assignment policies for robust facility location problems, An improved approximation algorithm for uncapacitated facility location problem with penalties, Interactive Clustering of Linear Classes and Cryptographic Lower Bounds, A 6.55 factor primal-dual approximation algorithm for the connected facility location problem, The traveling \(k\)-median problem: approximating optimal network coverage, A cross-monotonic cost sharing method for the facility location game with service installation costs, Bounding quality of pure Nash equilibria in dual-role facility location games, The General Steiner Tree-Star problem., Improved approximation algorithms for constrained fault-tolerant resource allocation, Improved approximation algorithms for solving the squared metric \(k\)-facility location problem, On parameterized approximation algorithms for balanced clustering, Improved approximation algorithms for multilevel facility location problems, A constant-factor approximation algorithm for the \(k\)-median problem, The minimum \(k\)-storage problem on directed graphs, Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties), To close is easier than to open: dual parameterization to \(k\)-median, Concave connection cost facility location and the star inventory routing problem
