ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated.
If you have any questions, please contact Marianne Reed at mreed@ku.edu .
Approximation Algorithms for Geometric Median Problems
dc.contributor.author | Lin, Jyh-Han | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-21T18:13:55Z | |
dc.date.available | 2011-03-21T18:13:55Z | |
dc.date.issued | 1992 | |
dc.identifier.citation | J.-H. Lin and J. S. Vitter. “Approximation Algorithms for Geometric Median Problems,” Information Processing Letters, 44, 1992, 245–249. http://dx.doi.org/10.1016/0020-0190(92)90208-D | |
dc.identifier.uri | http://hdl.handle.net/1808/7206 | |
dc.description.abstract | In this paper we present approximation algorithms for median problems in metric spaces and xed-dimensional Euclidean space. Our algorithms use a new method for transforming an optimal solution of the linear program relaxation of the s-median problem into a provably good integral solution. This transfor- mation technique is fundamentally di erent from the methods of randomized and deterministic rounding [Rag, RaT] and the methods proposed in [LiV] in the following way: Previous techniques never set variables with zero values in the fractional solution to 1. This departure from previous methods is crucial for the success of our algorithms. | |
dc.language.iso | en_US | |
dc.publisher | Elsevier | |
dc.title | Approximation Algorithms for Geometric Median Problems | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffery Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1016/0020-0190(92)90208-D | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess |