Back to search

Springer

Algorithms for Some Clustering Problems

Abstract

dc:description.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.

Degree

thesis:*
Grantor dc:publisher
Springer
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rajagopalan, Ranjithkumar

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
6475809
Dc Identifier Citation
Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science 2832 Springer 2003

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Rajagopalan, Ranjithkumar. Algorithms for Some Clustering Problems. Springer, 2005. https://hdl.handle.net/1813/2102