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 \(\Re^2\) such that the maximum among the distances between each point to its nearest line is minimized. A \(2\)-factor approximation algorithm and a \((\frac{5}{3}, \frac{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.