Analysis of a Local Search Heuristic for Facility Location Problems
From MaRDI portal
Publication:4512576
DOI10.1006/jagm.2000.1100zbMath0962.68044OpenAlexW2608158342MaRDI QIDQ4512576
Madhukar R. Korupolu, Rajmohan Rajaraman, C. Greg Plaxton
Publication date: 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.2000.1100
Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties, A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems, Approximation algorithms for hard capacitated \(k\)-facility location problems, A new approximation algorithm for the \(k\)-facility location problem, A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties, Optimal Physician assignment and patient demand allocation in an outpatient care network, Approximation algorithms for facility location problems with a special class of subadditive cost functions, Bifactor approximation for location routing with vehicle and facility capacities, LP-based approximation for uniform capacitated facility location problem, A note on LP-based approximation algorithms for capacitated facility location problem, A 3-approximation algorithm for the facility location problem with uniform capacities, Solving Facility Location Problem Based on Duality Approach, On the mass COVID-19 vaccination scheduling problem, Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date, An approximation algorithm for the dynamic facility location problem with outliers, Approximation algorithm for squared metric facility location problem with nonuniform capacities, Centrality of trees for capacitated \(k\)-center, Improved bounds for metric capacitated covering problems, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, Robust facility location in reverse logistics, Approximation algorithm for squared metric two-stage stochastic facility location problem, Improved approximation algorithm for universal facility location problem with linear penalties, Unnamed Item, \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space, Unnamed Item, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Maximum gradient embeddings and monotone clustering, A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem, LP-Based Algorithms for Capacitated Facility Location, Respecting lower bounds in uniform lower and upper bounded facility location problem, Unnamed Item, A Local-Search Algorithm for Steiner Forest, Capacitated Domination Problem, LP-based approximation algorithms for capacitated facility location, From stars to comets: improved local search for universal facility location, Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics, Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties, Easy capacitated facility location problems, with connections to lot-sizing, Observations on some heuristic methods for the capacitated facility location problem, Local search algorithm for universal facility location problem with linear penalties, A distributed O(1)-approximation algorithm for the uniform facility location problem, Local search algorithms for the red-blue median problem, Capacitated domination problem, Incremental medians via online bidding, A new approximation algorithm for the multilevel facility location problem, Improved approximation algorithms for capacitated facility location problems, An approximation algorithm for a facility location problem with stochastic demands and inventories, Incremental algorithms for facility location and \(k\)-median, Approximation algorithms for the transportation problem with market choice and related models, Heuristics for the dynamic facility location problem with modular capacities, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, Approximating $k$-Median via Pseudo-Approximation, Unnamed Item, An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties, Constant-Factor FPT Approximation for Capacitated k-Median, Constant factor approximation algorithm for uniform hard capacitated knapsack median problem, The ordered \(k\)-median problem: surrogate models and approximation algorithms, An approximation algorithm for the uniform capacitated \(k\)-means problem, Solving large-scale uncapacitated facility location problems with evolutionary simulated annealing, Locating repair shops in a stochastic environment, The capacitated facility location problem with random input data, A constant-factor approximation algorithm for the \(k\)-median problem, To close is easier than to open: dual parameterization to \(k\)-median
