A new greedy approach for facility location problems
From MaRDI portal
Publication:3579195
DOI10.1145/509907.510012zbMath1192.90106OpenAlexW2006514056MaRDI QIDQ3579195
No author found.
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.510012
Related Items
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems ⋮ Complexity of single-swap heuristics for metric facility location and related problems ⋮ An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ New approximation algorithms for the unsplittable capacitated facility location problem ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ Improved Approximation Algorithm for Fault-Tolerant Facility Placement ⋮ A new approximation algorithm for the \(k\)-facility location problem ⋮ Improved algorithms for joint optimization of facility locations and network connections ⋮ Serving Online Requests with Mobile Servers ⋮ Unnamed Item ⋮ A hybrid multistart heuristic for the uncapacitated facility location problem ⋮ A lower bound for metric 1-median selection ⋮ An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs ⋮ Partial multicuts in trees ⋮ Clustering through continuous facility location problems ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ Anycasting in connection-oriented computer networks: Models, algorithms and results ⋮ Approximation algorithms for clustering with dynamic points ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ Incremental facility location problem and its competitive algorithms ⋮ Probably certifiably correct \(k\)-means clustering ⋮ An approximation algorithm for the \(p\)-hub median problem ⋮ The distance-constrained matroid median problem ⋮ On clustering with discounts ⋮ Agile optimization for a real‐time facility location problem in Internet of Vehicles networks ⋮ Finding geometric facilities with location privacy ⋮ Clustering with faulty centers ⋮ Selecting energy efficient inputs using graph structure ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ 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 ⋮ Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored ⋮ Unnamed Item ⋮ Integrated Supply Chain Management via Randomized Rounding ⋮ Unnamed Item ⋮ A primal-dual algorithm for online non-uniform facility location ⋮ Approximation algorithm for facility location with service installation costs ⋮ Data stability in clustering: a closer look ⋮ Capacitated Domination Problem ⋮ A \(k\)-product uncapacitated facility location problem ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ On the cost of essentially fair clusterings ⋮ An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem ⋮ The approximation gap for the metric facility location problem is not yet closed ⋮ A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem ⋮ On the competitive ratio for online facility location ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Robust fault tolerant uncapacitated facility location ⋮ Approximating soft-capacitated facility location problem with uncertainty ⋮ A distributed O(1)-approximation algorithm for the uniform facility location problem ⋮ A splitter location-allocation problem in designing fiber optic access networks ⋮ Local search algorithms for the red-blue median problem ⋮ Capacitated domination problem ⋮ Incremental medians via online bidding ⋮ Kinetic facility location ⋮ Multi-facility ordered median problems in directed networks ⋮ Randomized priority algorithms ⋮ Soft-capacitated facility location game ⋮ Approximating the two-level facility location problem via a quasi-greedy approach ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations ⋮ A General k-Level Uncapacitated Facility Location Problem ⋮ Incremental algorithms for facility location and \(k\)-median ⋮ The facility location problem with general cost functions ⋮ An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme ⋮ Mixed fault tolerance in server assignment: combining reinforcement and backup ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Approximation algorithms for the lower-bounded knapsack median problem ⋮ Approximating $k$-Median via Pseudo-Approximation ⋮ 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 ⋮ Algorithms for k-median Clustering over Distributed Streams ⋮ Approximation algorithms for hierarchical location problems ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ Center-based clustering under perturbation stability ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ Agnostic Clustering ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ A 6.55 factor primal-dual approximation algorithm for the connected facility location problem ⋮ The reverse greedy algorithm for the metric k-median problem ⋮ 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 ⋮ Facility Location with Matroid or Knapsack Constraints ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ Improved approximation algorithms for constrained fault-tolerant resource allocation ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model ⋮ Improved approximation algorithms for multilevel facility location problems ⋮ Improved approximation algorithms for a bilevel knapsack problem ⋮ A constant-factor approximation algorithm for the \(k\)-median problem
