Short simplex paths in lattice polytopes

DOI10.1007/S00454-020-00268-YMaRDI QIDQ2117352zbMATH OpenOpenAlexFDO

Authors Alberto Del Pia, Carla Michini

Publication date 21 March 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.05712

zbMATH Keywords

lattice polytopesdiametersimplex algorithmstrongly polynomial time

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces `short' simplex paths from any given vertex to an optimal one. We consider a lattice polytope $P$ contained in $[0,k{]}^n$ and defined via $m$ linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of $P$ of length in $O(n^{4}klog(nk)$. The length of this path is independent from $m$ and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst-case diameter, which roughly grows as a linear function in $n$ and $k$. Motivated by the fact that most known lattice polytopes are defined via $0,pm1$ constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value $alpha$ of the entries in the constraint matrix. We show that the length of the simplex path generated by the iterative algorithm is in $O(n^{2}klog(nkalpha))$. In particular, if $alpha$ is bounded by a polynomial in $n,k$, then the length of the simplex path is in $O(n^{2}klog(nk))$. For both algorithms, the number of arithmetic operations needed to compute the next vertex in the path is polynomial in $n$, $m$ and $logk$. If $k$ is polynomially bounded by $n$ and $m$, the algorithm runs in strongly polynomial time.

Recommendations

• Finding short paths on polytopes by the shadow vertex algorithm
• On the length of monotone paths in polyhedra
• scientific article; zbMATH DE number 2196286
• On the shadow simplex method for curved polyhedra
• Linear programming, the simplex algorithm and simple polytopes

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 66675 (Why is no real title available?)
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• 0/1-Integer programming: Optimization and Augmentation are equivalent
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A bound for the number of different basic solutions generated by the simplex method
• An application of simultaneous diophantine approximation in combinatorial optimization
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Factoring polynomials with rational coefficients
• Improved bounds on the diameter of lattice polytopes
• Integer Programming
• Network flows. Theory, algorithms, and applications.
• On the diameter of convex polytopes
• On the diameter of lattice polytopes
• On the length of monotone paths in polyhedra
• On the maximal number of edges of convex digital polygons included into an m m-grid
• On the number of solutions generated by the dual simplex method
• Primitive zonotopes
• Restarting algorithms: sometimes there is free lunch
• Scaling algorithms for network problems
• Solving MIPs via scaling-based augmentation
• The Hirsch conjecture is true for (0,1)-polytopes
• The diameter of lattice zonotopes
• The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(9)

• The complexity of geometric scaling
• On the shadow simplex method for curved polyhedra
• A generalized simplex method for integer problems given by verification oracles
• On the shadow simplex method for curved polyhedra
• On the length of monotone paths in polyhedra
• Pivot rules for circuit-augmentation algorithms in linear optimization
• Lemke Paths on Simple Polytopes
• Finding short paths on polytopes by the shadow vertex algorithm
• Inapproximability of shortest paths on perfect matching polytopes

This page was built for publication: Short simplex paths in lattice polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117352)