Article (Scientific journals)
On the length of monotone paths in polyhedra
Blanchard, Moise; De Loera, Jesus; Louveaux, Quentin
2021In SIAM Journal on Discrete Mathematics
Peer Reviewed verified by ORBi
 

Files


Full Text
BlanchardDeLoeraLouveaux.pdf
Author postprint (527.82 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Simplex method; diameter; polyhedra
Abstract :
[en] Motivated by the problem of bounding the number of iterations of the Simplex algorithm we investigate the possible lengths of monotone paths followed inside the oriented graphs of polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the TSP, among others. We begin by showing that combinatorial cubes have monotone diameter and Bland simplex height upper bounded by their dimension and that in fact all monotone paths of zonotopes are no larger than the number of edge directions of the zonotope. We later use this to show that several polytopes have polynomial-size monotone diameter. In contrast, we show that for many well-known combinatorial polytopes, the height is at least exponential. Surprisingly, for some famous pivot rules, e.g., greatest improvement and steepest edge, these same polytopes have polynomial-size simplex paths.
Disciplines :
Mathematics
Computer science
Author, co-author :
Blanchard, Moise ;  Massachusetts Institute of Technology - MIT
De Loera, Jesus ;  University of California, Davis - UC Davis > Department of Mathematics
Louveaux, Quentin  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète
 These authors have contributed equally to this work.
Language :
English
Title :
On the length of monotone paths in polyhedra
Publication date :
2021
Journal title :
SIAM Journal on Discrete Mathematics
ISSN :
0895-4801
eISSN :
1095-7146
Publisher :
Society for Industrial and Applied Mathematics, United States
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 28 April 2021

Statistics


Number of views
56 (15 by ULiège)
Number of downloads
99 (9 by ULiège)

Scopus citations®
 
2
Scopus citations®
without self-citations
2
OpenCitations
 
1

Bibliography


Similar publications



Contact ORBi