Search for: All records

The metric\(k\)-median problem is a classical and widely studied objective for data clustering, with applications in data analysis, computer vision, genomics, and facility location. The current best approximation algorithms for\(k\)-median rely on first obtaining a structured fractional solution known as abi-point solution, and then rounding it to an integer solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasingly-discretized partitioning schemes for the facilities, along with corresponding sets of randomized algorithms and factor-revealing non-linear programs. We show this hierarchy improves upon the current best factor of\(1.3371\), proving that the third layer of this hierarchy achieves a rounding factor of\(1.3064\), while no layer can achieve a factor smaller than\(1.2943\)in expectation. Combined with the current best algorithm for bi-point solution generation, we get a\(2.6081\)approximation factor for\(k\)-median. On the negative side, we give a family of bi-point solutions with integrality gap approaching the square root of the golden ratio, approximately\(1.272\), even when allowed to open\(k+o(k)\)facilities. Altogether, our results substantially narrow the approximation gap for bi-point solutions. 

Abstract We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We prove such a concentration inequality for the lower tail when the random variables satisfy negative association or negative regression, partially resolving an open problem raised in ([1]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([2, 3]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read-kfamilies [4] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [4].