Skip to main content


eCommons@Cornell >
Cornell University Graduate School >
Cornell Theses and Dissertations >

Please use this identifier to cite or link to this item:
Title: Algorithms for Some Clustering Problems
Authors: Rajagopalan, Ranjithkumar
Keywords: Facility Location
Population Genetics
Approximation Algorithms
Branch and Bound
Issue Date: 21-Jul-2005
Publisher: Springer
Citation: Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science 2832 Springer 2003
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.
Description: Committee Members: David Shmoys, Shane Henderson, Jon Kleinberg
Appears in Collections:Cornell Theses and Dissertations

Files in This Item:

File Description SizeFormat
thesis.pdf393.03 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us