Paper Info
Title
Errata for: A subexponential lower bound for the Random Facet algorithm for Parity Games.
Abstract
In Friedmann, Hansen, and Zwick (2011) we claimed that the expected number of pivoting steps performed by the Random-Facet algorithm of Kalai and of Matousek, Sharir, and Welzl is equal to the expected number of pivoting steps performed by Random-Facet^*, a variant of Random-Facet that bases its random decisions on one random permutation. We then obtained a lower bound on the expected number of pivoting steps performed by Random-Facet^* and claimed that the same lower bound holds also for Random-Facet. Unfortunately, the claim that the expected numbers of steps performed by Random-Facet and Random-Facet^* are the same is false. We provide here simple examples that show that the expected numbers of steps performed by the two algorithms are not the same.
Year
Venue
Field
2014
CoRR
Discrete mathematics,Combinatorics,Upper and lower bounds,Algorithm,Random permutation,Expected value,Facet (geometry),Parity (mathematics),Mathematics
DocType
Volume
Citations 
Journal
abs/1410.7871
2
PageRank 
References 
Authors
0.36
8
3
Name
Order
Citations
PageRank
Oliver Friedmann119814.29
Thomas Dueholm Hansen216113.77
Uri Zwick33586257.02