Optimum turn-restricted paths,nested compatibility,and optimum convex polygons |
| |
Authors: | Maurice Queyranne Laurence A Wolsey |
| |
Institution: | 1.UBC Sauder School of Business,University of British Columbia,Vancouver,Canada;2.Center for Operations Research and Econometrics (CORE),Université catholique de Louvain,Louvain-la-Neuve,Belgium |
| |
Abstract: | We consider two apparently unrelated classes of combinatorial and geometric optimization problems. First, we give compact extended formulations, i.e., polynomial-size linear programming formulations with integer optima, for optimum path problems with turn restrictions satisfying a nested compatibility condition in acyclic digraphs. We then apply these results to optimum convex polygon problems in the plane, by interpreting certain dynamic programming algorithms as sequences of optimum turn-restricted path problems with nested compatibility in acyclic digraphs. As a result, we derive compact extended formulations for these geometric problems as well. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|