Optimization Online


On the diameter of lattice polytopes

Alberto Del Pia(delpia***at***wisc.edu )
Carla Michini(michini***at***wisc.edu)

Abstract: In this paper we show that the diameter of a d-dimensional lattice polytope in [0,k]^n is at most (k - 1/2) d. This result implies that the diameter of a d-dimensional half-integral polytope is at most 3/2 d. We also show that for half-integral polytopes the latter bound is tight for any d.

Keywords: diameter, lattice polytope

Category 1: Combinatorial Optimization (Polyhedra )

Citation: University of Wisconsin-Madison, December 2015

Download: [PDF]

Entry Submitted: 12/24/2015
Entry Accepted: 12/24/2015
Entry Last Modified: 12/24/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society