Math @ Duke

Publications [#235453] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Procopiuc, CM; Varadarajan, KR, A (1+ε)approximation algorithm for 2linecenter,
Computational Geometry, vol. 26 no. 2
(2003),
pp. 119128, ISSN 09257721 [doi]
(last updated on 2018/03/17)
Abstract: We consider the following instance of projective clustering, known as the 2linecenter problem: Given a set S of n points in ℝ2, cover S by two congruent strips of minimum width. Algorithms that find the optimal solution for this problem have nearquadratic running time. In this paper we present an algorithm that, for any ε > 0, computes in time O(n(logn+ε 2log(1/ε))+ε 7/2log(1/ε)) a cover of S by two strips of width at most (1+ε)w(*). © 2003 Elsevier B.V. All rights reserved.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

