Approximation algorithms for orthogonal line centers.

The problem of k orthogonal line center is about computing a set of k axis-parallel lines for a given set of points in ℜ 2 such that the maximum among the distances between each point to its nearest line is minimized. A 2-factor approximation algorithm and a (5 3 , 3 2) bi-criteria approximation algorithm is presented for the problem. Both of them are deterministic approximation algorithms using combinatorial techniques and having sub-quadratic running times. [ABSTRACT FROM AUTHOR]