3 papers
cs.DM2017
Exponential lower bounds for history-based simplex pivot rules on abstract cubes
Antonis Thomas
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 impo…
cs.DM2016
The Niceness of Unique Sink Orientations
Bernd Gärtner, Antonis Thomas
Random Edge is the most natural randomized pivot rule for the simplex algorithm. Considerable progress has been made recently towards fully understanding its behavior. Back in 2001…
cs.CC2016
Approximation and Hardness for Token Swapping
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto +3
Given a graph with , we place on every vertex a token . A swap is an exchange of tokens on adjacent vertices. We consider the algorithmi…