Abstract
The problem of orthogonal line center is about computing a set of axis-parallel lines for a given set of points in such that the maximum among the distances between each point to its nearest line is minimized. A -factor approximation algorithm and a bi-criteria approximation algorithm are presented for the problem. Both of them are deterministic approximation algorithms using combinatorial techniques and having sub-quadratic running times.