Improved approximation for prize-collecting red-blue median

DOI10.1016/J.TCS.2021.05.029OpenAlexW3165631835MaRDI QIDQ2043014

Yutian Guo, Zhen Zhang, Jianxin Wang, Feng Shi, Junyu Huang

Publication date: 22 July 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.05.029

zbMATH Keywords

clusteringapproximationlocal search

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Improved approximation algorithms for solving the squared metric \(k\)-facility location problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search algorithms for the red-blue median problem
• An improved approximation algorithm for the \(k\)-means problem with penalties
• Local search approximation algorithms for the \(k\)-means problem with penalties
• A Dependent LP-Rounding Approach for the k-Median Problem
• Assignment problem in content distribution networks
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Budgeted Red-Blue Median and Its Generalizations
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Local Search Heuristics for k-Median and Facility Location Problems
• Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• Constant approximation for k-median and k-means with outliers via iterative rounding

This page was built for publication: Improved approximation for prize-collecting red-blue median