Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2012 Copyright 2012 Universität Bonn, Institut für Informatik, Abt. V
85330

04.07.2012

Optimal Cuts and Bisections on the Real Line in Polynomial Time
Marek Karpinski, Andrzej Lingas and Dzmitry Sledneu
[Download PostScript] [Download PDF]

The exact complexity of geometric cuts and bisections is the longstanding open problem including even the dimension one. In this paper, we resolve this problem for dimension one (the real line) by designing an exact polynomial time algorithm. Our results depend on a new technique of dealing with metric equalities and their connection to dynamic programming. The method of our solution could be also of independent interest.

Last Change: 11/05/14 at 10:59:47
 English
Universität Bonn -> Institut für Informatik -> Abteilung V