{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/2102"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/2102","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"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.","abstract_html":"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 &amp; Vazirani, and an algorithm of Mettu &amp; Plaxton. The main result answers positively a question posed by Jain and Vazirani of whether their algorithm can be modified to attain a desired &quot;continuity&quot; 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.","abstract_has_math":false,"creators":["Rajagopalan, Ranjithkumar"],"institution":"Springer","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2005,"date_issued":"2005-07-21T20:29:03Z","date_published":"2005-07-21T20:29:03Z","updated_at":"2026-11-19T03:14:48Z","subjects":["Facility Location","Population Genetics","Approximation Algorithms","Branch and Bound"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475809"],"render_values":[{"text":"6475809","href":null,"code":true}]},{"key":"dc:identifier.citation","label":"Dc Identifier Citation","values":["Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science 2832 Springer 2003"],"render_values":[{"text":"Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science 2832 Springer 2003","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/2102","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/2102","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F2102","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Rajagopalan, Ranjithkumar"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-07-21T20:29:03Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-07-21T20:29:03Z"]},{"key":"dc:date.issued","label":"Date","values":["2005-07-21T20:29:03Z"]},{"key":"dc:publisher","label":"Institution","values":["Springer"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Facility Location","Population Genetics","Approximation Algorithms","Branch and Bound"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475809"]},{"key":"dc:identifier.citation","label":"Dc Identifier Citation","values":["Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science 2832 Springer 2003"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/2102"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"a37e943e-241a-44bb-81aa-d776a864326f\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Algorithms for Some Clustering Problems</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2005-07-21T20:29:03Z</PublicationDate> <Authors> <Author> <DisplayName>Rajagopalan, Ranjithkumar</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <DisplayName>Springer</DisplayName> <OrgUnit /> </Publisher> </Publishers> <Keyword>Facility Location</Keyword> <Keyword>Population Genetics</Keyword> <Keyword>Approximation Algorithms</Keyword> <Keyword>Branch and Bound</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Rajagopalan, Ranjithkumar"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description","label":"Description","values":["Committee Members: David Shmoys, Shane Henderson, Jon Kleinberg"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:description.sponsorship","label":"Dc Description Sponsorship","values":["National Science Foundation"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["402465 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithms for Some Clustering Problems"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"a37e943e-241a-44bb-81aa-d776a864326f\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Algorithms for Some Clustering Problems</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2005-07-21T20:29:03Z</PublicationDate> <Authors> <Author> <DisplayName>Rajagopalan, Ranjithkumar</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <DisplayName>Springer</DisplayName> <OrgUnit /> </Publisher> </Publishers> <Keyword>Facility Location</Keyword> <Keyword>Population Genetics</Keyword> <Keyword>Approximation Algorithms</Keyword> <Keyword>Branch and Bound</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Rajagopalan, Ranjithkumar"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Rajagopalan, Ranjithkumar"],"dc:date.accessioned":["2005-07-21T20:29:03Z"],"dc:date.available":["2005-07-21T20:29:03Z"],"dc:date.issued":["2005-07-21T20:29:03Z"],"dc:description":["Committee Members: David Shmoys, Shane Henderson, Jon Kleinberg"],"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."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:description.sponsorship":["National Science Foundation"],"dc:format.extent":["402465 bytes"],"dc:format.mimetype":["application/pdf"],"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"],"dc:identifier.uri":["https://hdl.handle.net/1813/2102"],"dc:language.iso":["en_US"],"dc:publisher":["Springer"],"dc:subject":["Facility Location","Population Genetics","Approximation Algorithms","Branch and Bound"],"dc:title":["Algorithms for Some Clustering Problems"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:14:48Z"}