License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.345
URN: urn:nbn:de:0030-drops-51142
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5114/
Go to the corresponding LIPIcs Volume Portal

Dadush, Daniel ; Hähnle, Nicolai

On the Shadow Simplex Method for Curved Polyhedra

pdf-format:
31.pdf (0.5 MB)

Abstract

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 results of Bonifas et al. (SOCG 2012), Brunsch and Röglin (ICALP 2013), and Eisenbrand and Vempala (2014) have improved our understanding of such polyhedra.

We develop a new type of dual analysis of the shadow simplex method which provides a clean and powerful tool for improving all previously mentioned results. Our methods are inspired by the recent work of Bonifas and the first named author, who analyzed a remarkably similar process as part of an algorithm for the Closest Vector Problem with Preprocessing.

For our first result, we obtain a constructive diameter bound of O((n^2 / delta) ln (n / delta)) for n-dimensional polyhedra with curvature parameter delta in (0, 1]. For the class of polyhedra arising from totally unimodular constraint matrices, this implies a bound of O(n^3 ln n). For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected O((n^3 / delta) ln (n / delta)) simplex pivots, each requiring O(mn) time to compute. An initial feasible solution can be found using O((mn^3 / delta) ln (n / delta)) pivot steps.

BibTeX - Entry

@InProceedings{dadush_et_al:LIPIcs:2015:5114,
  author =	{Daniel Dadush and Nicolai H{\"a}hnle},
  title =	{{On the Shadow Simplex Method for Curved Polyhedra}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{345--359},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5114},
  URN =		{urn:nbn:de:0030-drops-51142},
  doi =		{10.4230/LIPIcs.SOCG.2015.345},
  annote =	{Keywords: Optimization, Linear Programming, Simplex Method, Diameter of Polyhedra}
}

Keywords: Optimization, Linear Programming, Simplex Method, Diameter of Polyhedra
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI