文章基本信息

标题：Random-Edge Is Slower Than Random-Facet on Abstract Cubes
本地全文：下载
作者：Thomas Dueholm Hansen ; Uri Zwick
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：51:1-51:14
DOI：10.4230/LIPIcs.ICALP.2016.51
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Random-Edge and Random-Facet are two very natural randomized pivoting rules for the simplex algorithm. The behavior of Random-Facet is fairly well understood. It performs an expected sub-exponential number of pivoting steps on any linear program, or more generally, on any Acyclic Unique Sink Orientation (AUSO) of an arbitrary polytope, making it the fastest known pivoting rule for the simplex algorithm. The behavior of Random-Edge is much less understood. We show that in the AUSO setting, Random-Edge is slower than Random-Facet. To do that, we construct AUSOs of the n-dimensional hypercube on which Random-Edge performs an expected number of 2^{Omega(sqrt(n*log(n)))} steps. This improves on a 2^{Omega(sqrt^3(n))} lower bound of MatouSek and Szabó. As Random-Facet performs an expected number of 2^{O(sqrt(n)} steps on any n-dimensional AUSO, this established our result. Improving our 2^{Omega(sqrt(n*log(n)))} lower bound seems to require radically new techniques.
关键词：Linear programming; the Simplex Algorithm; Pivoting rules; Acyclic Unique Sink Orientations