# Approximation algorithms for k-line center

Published

Conference Paper

© Springer-Verlag Berlin Heidelberg 2002. Given a set P of n points in Rd and an integer k ≥ 1, let w* denote the minimum value so that P can be covered by k cylinders of radius at most (1 + ε )w*. We describe an algorithm that, given P and an ε> 0, computes k cylinders of radius at most (1 + ε)w* that cover P. The running time of the algorithm is O(n log n), with the constant of proportionality depending on k, d, and e. We first show that there exists a small "certificate" Q #x2286; P, whose size does not depend on n, such that for any k-cylinders that cover Q, an expansion of these cylinders by afactorof(1 + ε)covers P. We then use a well-known scheme based on sampling and iterated re-weighting for computing the cylinders.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Procopiuc, CM; Varadarajan, KR

### Published Date

- January 1, 2002

### Published In

### Volume / Issue

- 2461 /

### Start / End Page

- 54 - 63

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### International Standard Book Number 10 (ISBN-10)

- 3540441808

### International Standard Book Number 13 (ISBN-13)

- 9783540441809

### Digital Object Identifier (DOI)

- 10.1007/3-540-45749-6_9

### Citation Source

- Scopus