Seminář G²OAT: Approximation Algorithms for Orthogonal Line Centers

Abstrakt

The problem of $k$ orthogonal line center is about computing a set of $k$ axis-parallel lines for a given set of points in ${\mathrm{\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 are presented for the problem. Both of them are deterministic approximation algorithms using combinatorial techniques and having sub-quadratic running times.

Další události