Improved parameterized approximation for balanced \(k\)-median

DOI10.1007/978-3-030-92681-6_49OpenAlexW4206498635MaRDI QIDQ2150584

Qilong Feng, Zhen Zhang

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_49

zbMATH Keywords

approximation algorithm\(k\)-medianparameterized algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An LP-based \(k\)-means algorithm for balancing weighted point sets
• Distributed balanced partitioning via linear embedding
• Faster balanced clusterings in high dimension
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• A constant factor approximation for lower-bounded \(k\)-median
• Approximating $k$-Median via Pseudo-Approximation
• A Dependent LP-Rounding Approach for the k-Median Problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximating capacitated k-median with (1 + ∊)k open facilities
• Local Search Heuristics for k-Median and Facility Location Problems
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
• On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
• Constant-Factor FPT Approximation for Capacitated k-Median

This page was built for publication: Improved parameterized approximation for balanced \(k\)-median