Algorithms for Some Clustering Problems

Abstract

The first part of this work gives new insight into two well-known approximation algorithms for the uncapacitated facility location problem: the primal-dual algorithm of Jain & Vazirani, and an algorithm of Mettu & Plaxton. The main result answers positively a question posed by Jain and Vazirani of whether their algorithm can be modified to attain a desired "continuity" property. This yields an upper bound of 3 on the integrality gap of the natural LP relaxation of the k-median problem, but our approach does not yield a polynomial time algorithm with this guarantee. We also give a new simple proof of the performance guarantee of the Mettu-Plaxton algorithm using LP duality, which suggests a minor modification of the algorithm that makes it Lagrangian multiplier-preserving.

The second part of this work deals with a problem we call the maximum average ratio cut problem. The motivation for this problem is a desire to expose structure in populations based on genetic information. Specifically, solving this problem allows us to evaluate unusually low heterozygosity in subpopulations. We reduce this problem to the maximum cut problem with given cardinality, and implement a branch and bound procedure to find exact solutions.