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.ESA.2017.69
URN: urn:nbn:de:0030-drops-78505
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7850/
Go to the corresponding LIPIcs Volume Portal

Thomas, Antonis

Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes

pdf-format:
LIPIcs-ESA-2017-69.pdf (0.7 MB)

Abstract

The behavior of the simplex algorithm is a widely studied subject. Specifically, the question of the existence of a polynomial pivot rule for the simplex algorithm is of major importance. Here, we give exponential lower bounds for three history-based pivot rules. Those rules decide their next step based on memory of the past steps. In particular, we study Zadeh's least entered rule, Johnson's least-recently basic rule and Cunningham's least-recently considered (or round-robin) rule. We give exponential lower bounds on Acyclic Unique Sink Orientations of the abstract cube, for all of these pivot rules. For Johnson's rule our bound is the first superpolynomial one in any context; for Zadeh's it is the first one for AUSO. Those two are our main results.

BibTeX - Entry

@InProceedings{thomas:LIPIcs:2017:7850,
  author =	{Antonis Thomas},
  title =	{{Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7850},
  URN =		{urn:nbn:de:0030-drops-78505},
  doi =		{10.4230/LIPIcs.ESA.2017.69},
  annote =	{Keywords: pivot rule, lower bound, exponential, unique sink orientation, zadeh}
}

Keywords: pivot rule, lower bound, exponential, unique sink orientation, zadeh
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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