research-article

On sub-determinants and the diameter of polyhedra

Authors:

Nicolas Bonifas,

Marco Di Summa,

Friedrich Eisenbrand,

Nicolai Hähnle,

Martin NiemeierAuthors Info & Claims

SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

Pages 357 - 362

https://doi.org/10.1145/2261250.2261304

Published: 17 June 2012 Publication History

Abstract

We derive a new upper bound on the diameter of the graph of a polyhedron P = {x ∈ Rⁿ : Ax ≤ b}, where A ∈ Z^m×n. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O(Δ² n⁴ log nΔ). If P is bounded, then we show that the diameter of P is at most O(Δ² n^3.5 log nΔ).

For the special case in which A is a totally unimodular matrix, the bounds are O(n⁴ log n) and O(n^3.5 log n) respectively. This improves over the previous best bound of O(m¹⁶n³(log mn)³) due to Dyer and Frieze [MR1274170].

References

[1]

M. L. Balinski. The Hirsch conjecture for dual transportation polyhedra. Math. Oper. Res., 9(4):629--633, 1984.

Digital Library

[2]

D. Barnette. An upper bound for the diameter of a polytope. Discrete Math., 10:9--13, 1974.

Digital Library

[3]

G. Brightwell, J. van den Heuvel, and L. Stougie. A linear bound on the diameter of the transportation polytope. Combinatorica, 26(2):133--139, 2006.

Digital Library

[4]

J. A. De Loera, E. D. Kim, S. Onn, and F. Santos. Graphs of transportation polytopes. J. Combin. Theory Ser. A, 116(8):1306--1325, 2009.

Digital Library

[5]

M. Dyer and A. Frieze. Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program., 64(1, Ser. A):1--16, 1994.

Digital Library

[6]

F. Eisenbrand, N. Hahnle, A. Razborov, and T. Rothvoß. Diameter of polyhedra: Limits of abstraction. Math. Oper. Res., 35(4):786--794, 2010.

Digital Library

[7]

H. Federer. Geometric Measure Theory. Springer, 1969.

[8]

T. Figiel, J. Lindenstrauss, and V. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1):53--94, 1977.

[9]

V. Kaibel. On the expansion of graphs of 0/1-polytopes. In The sharpest cut, MPS/SIAM Ser. Optim., pages 199--216. SIAM, Philadelphia, PA, 2004.

[10]

G. Kalai. The diameter of graphs of convex polytopes and $f$-vector theory. In Applied geometry and discrete mathematics, volume 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 387--411. Amer. Math. Soc., Providence, RI, 1991.

[11]

G. Kalai and D. J. Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Amer. Math. Soc. (N.S.), 26(2):315--316, 1992.

[12]

E. D. Kim and F. Santos. An update on the Hirsch conjecture. Jahresber. Dtsch. Math.-Ver., 112(2):73--98, 2010.

[13]

V. Klee and D. W. Walkup. The d-step conjecture for polyhedra of dimension d<6. Acta Math., 133:53--78, 1967.

[14]

D. G. Larman. Paths of polytopes. Proc. London Math. Soc. (3), 20:161--178, 1970.

[15]

L. Lovász and M. Simonovits. Random walks in a convex body and an improved volume algorithm. Rand. Struct. Algor., 4(4):359--412, 1993.

[16]

M. Merkle. Logarithmic convexity and inequalities for the gamma function. J. Math. Anal. Appl., 203(2):369--380, 1996.

[17]

D. Naddef. The Hirsch conjecture is true for (0,1)-polytopes. Math. Program., 45:109--110, 1989.

Digital Library

[18]

J. B. Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Math. Program., 78(2, Ser. B):109--129, 1997.

Digital Library

[19]

F. Santos. A counterexample to the Hirsch conjecture. 2010. arXiv:1006.2814v1 {math.CO}. To appear in Ann. Math.

[20]

R. Vershynin. Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM J. Comput., 39(2):646--678, 2009.

Digital Library

Cited By

Eisenbrand FVempala S(2017)Geometric random edgeMathematical Programming: Series A and B10.1007/s10107-016-1089-0164:1-2(325-339)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10107-016-1089-0
Bonifas NDi Summa MEisenbrand FHähnle NNiemeier M(2014)On Sub-determinants and the Diameter of PolyhedraDiscrete & Computational Geometry10.1007/s00454-014-9601-x52:1(102-115)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1007/s00454-014-9601-x

Index Terms

On sub-determinants and the diameter of polyhedra
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics

Recommendations

On Sub-determinants and the Diameter of Polyhedra

We derive a new upper bound on the diameter of a polyhedron $$P = \{x {\in } {\mathbb {R}}^n :Ax\le b\}$$ P = { x R n : A x ≤ b } , where $$A \in {\mathbb {Z}}^{m\times n}$$ A Z m n . The bound is polynomial in $$n$$ n and the largest absolute value of a sub-determinant of $$A$$ A , denoted by $$\Delta $$ Δ . More precisely, we show that the diameter of $$P$$ P is bounded by $$O(\Delta ^2 n^4\log n\Delta )$$ O ( Δ 2 n 4 log n Δ ) . If $$P$$ P is bounded, then we ...
On the Shadow Simplex Method for Curved Polyhedra

We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds, which enforce that the boundary always meets vertices at sharp angles. Motivated by linear programs with totally unimodular constraint matrices, recent ...
On the total/sub k/-diameter of connection networks
ISTCS '97: Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97)

We study connection networks in which certain pairs of nodes have to be connected by k edge-disjoint paths, and study bounds for the minimal sum of lengths of such k paths. We define the related notions of total/sub k/-distance for a pair of nodes and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '12: Proceedings of the twenty-eighth annual symposium on Computational geometry

June 2012

436 pages

ISBN:9781450312998

DOI:10.1145/2261250

Program Chairs:
Tamal Dey
The Ohio State University, USA
,
Sue Whitesides
University of Victoria, Canada

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '12

Sponsor:

SoCG '12: Symposium on Computational Geometry 2012

June 17 - 20, 2012

North Carolina, Chapel Hill, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
100
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Eisenbrand FVempala S(2017)Geometric random edgeMathematical Programming: Series A and B10.1007/s10107-016-1089-0164:1-2(325-339)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10107-016-1089-0
Bonifas NDi Summa MEisenbrand FHähnle NNiemeier M(2014)On Sub-determinants and the Diameter of PolyhedraDiscrete & Computational Geometry10.1007/s00454-014-9601-x52:1(102-115)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1007/s00454-014-9601-x

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten