Top

Journal of Combinatorial Optimization

Published in:

05-04-2018

Optimum turn-restricted paths, nested compatibility, and optimum convex polygons

Authors: Maurice Queyranne, Laurence A. Wolsey

Published in: Journal of Combinatorial Optimization | Issue 1/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article An upper bound on the double Roman domination number

next article 2-Distance vertex-distinguishing index of subcubic graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

If needed, we could add an origin 0 and a destination n connected to all 0p nodes, and from all \(\overline{qn}\) nodes, respectively, with zero-revenue arcs, so we seek a maximum value (0, n)-path in the resulting expanded network. This is, however, unnecessary for our purposes.

Recall that both nodes 0 and \(n_t\) represent the point \(x^t\).

Balas E (1998) Disjunctive programming: properties of the convex hull of feasible points. GSIA Management Science Research Report MSRR 348, Carnegie Mellon University (1974), published as invited paper. Discrete Appl Math 89(1):3–44

Bast H, Delling D, Goldberg A, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck RF (2015) Route planning in transportation networks. arXiv:1504.05140

Bautista-Santiago C, Díaz-Báñez JM, Lara D, Pérez-Lantero P, Urrutia J, Ventura I (2011) Computing optimal islands. Oper Res Lett 39(4):246–251MathSciNetCrossRefMATH

Borgwardt S, Brieden A, Gritzmann P (2014) Geometric clustering for the consolidation of farmland and woodland. Math Intell 36(2):37–44MathSciNetCrossRefMATH

Bucarey V, Ordóñez F, Bassaletti E (2015) Shape and balance in police districting. In: Applications of location analysis. Springer, Berlin, pp 329–347

Caldwell T (1961) On finding minimum routes in a network with turn penalties. Commun ACM 4(2):107–108MathSciNetCrossRefMATH

Conforti M, Cornuéjols G, Zambelli G (2010) Extended formulations in combinatorial optimization. 4OR 8(1):1–48MathSciNetCrossRefMATH

Delling D, Goldberg AV, Pajor T, Werneck RF (2011) Customizable route planning. In: Experimental algorithms. Springer, Berlin, pp 376–387

Doignon JP, Ducamp A, Falmagne JC (1984) On realizable biorders and the biorder dimension of a relation. J Math Psychol 28(1):73–109MathSciNetCrossRefMATH

Eppstein D, Overmars M, Rote G, Woeginger G (1992) Finding minimum areak-gons. Discrete Comput Geom 7(1):45–58MathSciNetCrossRefMATH

Geisberger R, Vetter C (2011) Efficient routing in road networks with turn costs. In: Experimental algorithms. Springer, Berlin, pp 100–111

Gutiérrez E, Medaglia AL (2008) Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks. Ann Oper Res 157(1):169–182MathSciNetCrossRefMATH

King D, Jacobson S, Sewell E (2017) The geo-graph in practice: creating united states congressional districts from census blocks. Comput Optim Appl 69:1–25MathSciNetMATH

Korte B, Lovász L (1989) Polyhedral results for antimatroids. Ann N Y Acad Sci 555(1):283–295MathSciNetCrossRefMATH

Korte B, Lovász L, Schrader R (1991) Greedoids, vol 4. Springer, BerlinMATH

Llorente IDP, Hoganson HM, Carson MT, Windmuller-Campione M (2017) Recognizing spatial considerations in forest management planning. Curr For Rep 3(4):308–316

Vanegas P, Cattrysse D, Van Orshoven J (2010) Compactness in spatial decision support: a literature review. Comput Sci Appl ICCSA 2010:414–429

Wilfong GT (1990) Motion planning for an autonomous vehicle. In: Autonomous robot vehicles. Springer, Berlin, pp 391–395

Title: Optimum turn-restricted paths, nested compatibility, and optimum convex polygons
Authors: Maurice Queyranne
Laurence A. Wolsey
Publication date: 05-04-2018
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2018
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0281-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2018

Approximation algorithms for the bus evacuation problem

Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan

Minimum 2-distance coloring of planar graphs and channel assignment

An upper bound on the double Roman domination number

Distributed algorithms for barrier coverage via sensor rotation in wireless sensor networks

A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network

Premium Partner