A (1+ε)-approximation algorithm for 2-line-center

Journal Article

We consider the following instance of projective clustering, known as the 2-line-center 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 near-quadratic 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.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • October 1, 2003

Published In

Volume / Issue

  • 26 / 2

Start / End Page

  • 119 - 128

International Standard Serial Number (ISSN)

  • 0925-7721

Digital Object Identifier (DOI)

  • 10.1016/S0925-7721(03)00017-8

Citation Source

  • Scopus