Local Search Heuristics for k-Median and Facility Location Problems
From MaRDI portal
Publication:4651480
DOI10.1137/S0097539702416402zbMath1105.68118OpenAlexW2003207175MaRDI QIDQ4651480
Rohit Khandekar, Vinayaka Pandit, Naveen Garg, Vijay Arya, Adam Meyerson, Kamesh Munagala
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539702416402
Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (only showing first 100 items - show all)
Experimental evaluation of a local search approximation algorithm for the multiway cut problem ⋮ Complexity of single-swap heuristics for metric facility location and related problems ⋮ Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median ⋮ An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ Clustering with or without the approximation ⋮ A new approximation algorithm for the \(k\)-facility location problem ⋮ Improved algorithms for joint optimization of facility locations and network connections ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Improved parameterized approximation for balanced \(k\)-median ⋮ An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation ⋮ Analysis of a local search algorithm for the k-facility location problem ⋮ Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties ⋮ A lower bound for metric 1-median selection ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ An exact algorithm for stable instances of the \(k\)-means problem with penalties in fixed-dimensional Euclidean space ⋮ On a facility location problem with applications to tele-diagnostic ⋮ Approximation algorithms for clustering with dynamic points ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ A 3-approximation algorithm for the facility location problem with uniform capacities ⋮ On generalizations of network design problems with degree bounds ⋮ A Lagrangian search method for the \(P\)-median problem ⋮ Solving Facility Location Problem Based on Duality Approach ⋮ The distance-constrained matroid median problem ⋮ On clustering with discounts ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ The median routing problem for simultaneous planning of emergency response and non-emergency jobs ⋮ Perturbation resilience for the facility location problem ⋮ Discrete facility location in machine learning ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities ⋮ Approximation algorithm for squared metric facility location problem with nonuniform capacities ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Recovery guarantees for exemplar-based clustering ⋮ An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions ⋮ On min-max \(r\)-gatherings ⋮ Better bounds for incremental medians ⋮ A Branch Decomposition Algorithm for the p-Median Problem ⋮ Unnamed Item ⋮ Approximation algorithms for the fault-tolerant facility placement problem ⋮ Maximum gradient embeddings and monotone clustering ⋮ 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 ⋮ Approximate the lower-bounded connected facility location problem ⋮ Local Search Based Approximation Algorithms for Two-Stage Stochastic Location Problems ⋮ Data stability in clustering: a closer look ⋮ Approximation algorithms for the dynamic \(k\)-level facility location problems ⋮ Approximation algorithms for spherical \(k\)-means problem using local search scheme ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Complexity of local search for the \(p\)-median problem ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ Metric \(k\)-median clustering in insertion-only streams ⋮ LP-rounding algorithms for the fault-tolerant facility placement problem ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ One-dimensional \(k\)-center on uncertain data ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Graph summarization with quality guarantees ⋮ Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties ⋮ Approximation algorithms for the robust facility leasing problem ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ 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 ⋮ Faster balanced clusterings in high dimension ⋮ Unnamed Item ⋮ An approximation ratio for biclustering ⋮ Sublinear-time Algorithms ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations ⋮ 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 ⋮ Heuristics for the dynamic facility location problem with modular capacities ⋮ An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme ⋮ Approximation algorithms for the lower-bounded knapsack median problem ⋮ Approximating $k$-Median via Pseudo-Approximation ⋮ Improved approximation for prize-collecting red-blue median ⋮ Unnamed Item ⋮ An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties ⋮ Constant-Factor FPT Approximation for Capacitated k-Median ⋮ An approximation algorithm for the \(k\)-level facility location problem with outliers ⋮ Unnamed Item ⋮ Approximation Algorithms for Distributed Multi-robot Coverage in Non-convex Environments ⋮ Near-optimal large-scale k-medoids clustering ⋮ Metric 1-Median Selection: Query Complexity vs. Approximation Ratio ⋮ Locating Depots for Capacitated Vehicle Routing ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ GravCPA: controller placement algorithm based on traffic gravitation in SDN ⋮ Approximate Range Queries for Clustering ⋮ A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem ⋮ Improved local search for universal facility location ⋮ A tight analysis of geometric local search ⋮ To close is easier than to open: dual parameterization to \(k\)-median ⋮ Problem-based optimal scenario generation and reduction in stochastic programming ⋮ Scenario reduction revisited: fundamental limits and guarantees
This page was built for publication: Local Search Heuristics for k-Median and Facility Location Problems
