Optimal Cuts and Bisections on the Real Line in Polynomial Time

2012/07/04 by Marek Karpinski, Karpinski, Marek, Andrzej Lingas +3
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.1207.0933

arxiv created 2012/07/04 · arxiv updated 2012/07/05

Abstract

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.

Related

• Optimal Cuts and Partitions in Tree Metrics in Polynomial Time
• The Cutting Plane Method is Polynomial for Perfect Matchings
• Split cuts in the plane
• Geometry on Optimal Problem
• Iterated Chvatal-Gomory Cuts and the Geometry of Numbers