Local search heuristic for k-median and facility location problems
From MaRDI portal
Publication:5175949
DOI10.1145/380752.380755zbMath1323.90031OpenAlexW2010410498MaRDI QIDQ5175949
Rohit Khandekar, Kamesh Munagala, Naveen Garg, Adam Meyerson, Vinayaka Pandit, Vijay Arya
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/380752.380755
Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems, New approximation algorithms for the unsplittable capacitated facility location problem, Serving Online Requests with Mobile Servers, Approximation algorithms for facility location problems with a special class of subadditive cost functions, An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee, A local search approximation algorithm for \(k\)-means clustering, LP-based approximation for uniform capacitated facility location problem, Improved results on geometric hitting set problems, Incremental facility location problem and its competitive algorithms, Polyhedral properties of the \(K\)-median problem on a tree, Universal Algorithms for Clustering Problems, Better bounds for incremental medians, Unnamed Item, A primal-dual algorithm for online non-uniform facility location, A Streaming Algorithm for k-Means with Approximate Coreset, Local Search Yields a PTAS for $k$-Means in Doubling Metrics, An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem, On the competitive ratio for online facility location, On the Facility Location Problem in Online and Dynamic Models., Approximation algorithms for the robust/soft-capacitated 2-level facility location problems, Approximate solution of the \(p\)-median minimization problem, Approximating soft-capacitated facility location problem with uncertainty, A fast swap-based local search procedure for location problems, Incremental medians via online bidding, A new approximation algorithm for the multilevel facility location problem, Deterministic sampling algorithms for network design, A simple tabu search for warehouse location, An approximation algorithm for a facility location problem with stochastic demands and inventories, Performance guarantees for hierarchical clustering, Asymmetry in \(k\)-center variants, Better Bounds for Incremental Medians, The facility location problem with general cost functions, Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems, The Priority k-Median Problem, An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties, Approximation algorithms for hierarchical location problems, Near-optimal clustering in the \(k\)-machine model, Joint object placement and node dimensioning for internet content distribution, An improved approximation algorithm for uncapacitated facility location problem with penalties, Center-based clustering under perturbation stability, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties, The reverse greedy algorithm for the metric k-median problem, Unnamed Item, Locating repair shops in a stochastic environment, Improved approximation algorithms for multilevel facility location problems, A constant-factor approximation algorithm for the \(k\)-median problem
Cites Work
