An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
From MaRDI portal
Publication:4962654
DOI10.1145/2981561zbMath1454.90069OpenAlexW3162678658MaRDI QIDQ4962654
Khoa Trinh, Jaroslaw Byrka, Aravind Srinivasan, Bartosz Rybicki, Thomas W. Pensyl
Publication date: 5 November 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2981561
combinatorial optimizationapproximation algorithms\(k\)-medianfacility location problemsdependent rounding
Related Items (40)
An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Improved parameterized approximation for balanced \(k\)-median ⋮ Unnamed Item ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ Approximation algorithms for clustering with dynamic points ⋮ On clustering with discounts ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Discrete facility location in machine learning ⋮ Effective Heuristic Techniques for Combined Robust Clustering Problem ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ Approximation algorithms for diversity-bounded center problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem ⋮ Approximation algorithms for spherical \(k\)-means problem using local search scheme ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ On the cost of essentially fair clusterings ⋮ Proportional Approval Voting, Harmonic k-median, and Negative Association ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Faster balanced clusterings in high dimension ⋮ Unnamed Item ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations ⋮ Lossy kernelization of same-size clustering ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Approximation algorithms for the lower-bounded knapsack median problem ⋮ The ordered \(k\)-median problem: surrogate models and approximation algorithms ⋮ On perturbation resilience of non-uniform \(k\)-center ⋮ The traveling \(k\)-median problem: approximating optimal network coverage ⋮ Lossy kernelization of same-size clustering ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem ⋮ On parameterized approximation algorithms for balanced clustering
This page was built for publication: An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
