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 | |