A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center (Q1405006)

Given a set \(S\) of \(n\) points in \(\mathbb R^2\), the two-line center problem consists of finding two strips covering \(S\) such that the maximum width of the strips is minimized. Known algorithms giving the exact solution require run times that grow almost like \(n^2\). In the paper under review, an approximation algorithm is presented that gives a nearly optimal solution with strip width \((1+\varepsilon)w^*\) instead of \(w^*\). The run time of this algorithm is only \(O(n (\log n + \varepsilon^{-2} \log \varepsilon^{-1}) + \varepsilon^{-7/2} \log\varepsilon^{-1})\).