A Linear Algorithm for Finding the Sink of
Unique Sink Orientations on Grids
arXiv:1709.08436v1 [] 25 Sep 2017

Xiaoming Sun, Jialin Zhang, Zhijie Zhang
September 26, 2017
Abstract
An orientation of a grid is called unique sink orientation (USO)
if each of its nonempty subgrids has a unique sink. Particularly, the
original grid itself has a unique global sink. In this work we investigate
the problem of how to find the global sink using minimum number of
queries to an oracle. There are two different oracle models: the vertex
query model where the orientation of all edges incident to the queried
vertex are provided, and the edge query model where the orientation
of the queried edge is provided. In the 2-dimensional case, we design
an optimal linear deterministic algorithm for the vertex query model
and an almost linear deterministic algorithm for the edge query model,
previously the best known algorithms run in O(N log N ) time for the
vertex query model and O(N 1.404 ) time for the edge query model.

1

Introduction

In this paper we consider a special type of d-dimensional grid, which is the
Cartesian product of d complete graphs. Each pair of vertices of the grid has
an edge if and only if they are distinct in exactly one coordinate. A subgrid
is the Cartesian product of cliques of the original complete graphs. Recall
that in an oriented graph a vertex with zero outdegree is called a sink. A
unique sink orientation (USO) of a grid is an orientation of its edges such
that each of its nonempty subgrids (including the original grid) has a unique
sink. Traditionally, an oriented grid with the above property is called a grid
USO.
The computational problem now is to find the unique global sink of a grid
USO. Two different oracle models were introduced in the literature [18, 7],
namely the vertex query model and the edge query model. A vertex query
1

Figure 1: (a) a 2-dimensional grid USO. (b) a 3-cube USO with an cycle.
reveals the orientation of all incident edges of the queried vertex, whereas
an edge query returns the orientation of the queried edge. We count for the
time overhead only the number of queries to the oracle.
In this paper, we restrict our main attention to the sink-finding problem
on a 2-dimensional grid USO, see Figure 1 (a) for an instance. There are two
reasons. As is well-known, a planar grid USO must be acyclic [7]. On the
contrary, a d-dimensional grid USO with d > 2 may contain cycles. Figure
1 (b) depicts a cyclic cube (a grid with each of its dimensions having size
two). The acyclicity of a planar grid USO allows us to design algorithms
that enhance the “rank” of queried vertices step by step and finally reach
the unique sink. Besides, a fast algorithm running in the lower dimensional
case may improve the upper bound in the general case, due to the inherited
grid USO introduced by Gärtner et al. [7].
However, the vertex query model seems to be unreasonable when fixing
the dimension. Since in practice it takes linear (or polynomial) time to
implement a vertex query, while the total number of vertex is polynomial.
The time for a vertex query is never negligible compared with the number of
queries. There are several reasons to justify the vertex query model. First,
the vertex query model is theoretically simpler than the edge query model
in that it is easy to formally capture all the information coming from a
single vertex query. Second, the number of vertex queries is a good measure
of complexity for a general grid USO of d dimension and luckily, due to
the inherited grid structure, algorithms running on a fixed-dimensional grid
USO may be adapted to a general d-dimensional grid USO. Third, it turns
out that our algorithm under the vertex query model serves as a black box
when addressing the more natural and practical edge query model. In a
word, though being mostly of theoretical interest for the grid USO of fixed

2

dimension, the study of the vertex query model still has potential practical
applications.
The sink-finding problem on a planar grid USO has an intuitive interpretation. Assume we have a matrix as input. Only numbers in the same
row or in the same column are allowed to be compared. Each submatrix has
exactly one minimum number. How many comparisons do we need to find
the global minimum number?
The grid USO of dimension two serves as a simple combinatorial framework to many well-studied optimization problems. The first example is the
one line and N points problem, first studied in [9]. Suppose there are N
points in general position in the plane and one vertical line to which none of
those N points belongs. There is a line segment between a pair of points if
and only if this segment intersects with the vertical line. The problem asks
to find the unique segment that has the lowest intersection with the vertical
line. This problem can be recast to the sink-finding problem of an implicit
planar grid USO in the following way [4]. Each line segment defines a grid
vertex. Two line segments are adjacent if and only if they share exactly one
endpoint. The higher one has an oriented edge to the lower one. The total
orientation turns out to be an USO. The lowest segment corresponds to the
global sink.
Another optimization problem that can be considered as a special case
of the sink-finding problem on a planar grid USO is the linear programs on
(N − 2)-polytopes with N facets. Felsner et al. [4] showed that the vertexedge graph of such a polytope, oriented by the linear objective function, is
isomorphic to a planar grid USO. The global sink, again, corresponds to the
optimal solution of this special type of linear programs. It is of interest to
take a look at how the algorithms devised for finding the sink of the planar
grid USO go on the vertex-edge graph of the above polytope. We provide
such an example in Section 3.
We have seen some relationship between the grid USO (of dimension
two) and linear programs. Indeed, one main motivation of the study of the
(general) grid USO is that it is closely related to linear programs. It is
generally known that although there are polynomial algorithms for solving
linear programs, such as the ellipsoid algorithm by Khachiyan [13] and the
interior-point algorithm by Karmarkar [12], both of them are not strongly
polynomial. It remains open whether there is such an algorithm. And also it
is unknown whether there exists a pivoting rule such that the simplex method
runs in polynomial time. Several well-known (randomized) pivoting rules,
such as Random-Edge, Random-Facet [11, 15] and Random-Bland
[2], have failed to reach such an bound [14, 16, 5, 6]. It turns out that the
unique sink orientation may help devise an outperforming algorithm to solve
3

linear programs. Holt and Klee [10] showed that an orientation of a polytope
is an acyclic unique sink orientation (AUSO) with the Holt-Klee property if
it is induced from an LP instance. The Holt-Klee property states that the
number of vertex-disjoint directed paths from the source to the sink equals to
the number of the neighbours of the source (or the sink equivalently) in every
subgrid. Furthermore, Gärtner and Schurr [8] proved that any LP instance
in d nonnegative variables defines a d-dimensional cube USO. The sink of
this cube corresponds naturally to an optimal solution to the LP. The vertex
query oracle comes down to Gaussian elimination. A polynomial sink-finding
algorithm would yield a corresponding algorithm to solve linear programs.
Besides linear programs, the underlying combinatorial structures of many
other optimization problems are actually a grid USO. An important example
is the generalized linear complementarity problem over a P-matrix (PGLCP),
first introduced by Cottle and Dantzig [3]. Gärtner et al. [7] showed that
this problem can be recast to the sink-finding problem of an implicit grid
USO.
Previous work. The sink-finding problem of a grid USO was first put
forward formally and studied by Szabó and Welzl [18], where they restricted
their attention to a d-dimensional cube. They designed the first nontrivial
deterministic and randomized algorithms which use O(cd ) vertex queries for
some constant c < 2. Later Gärtner et al. [7] extended the two oracle
models to a d-dimensional grid USO. In that paper they investigated several
properties of a grid USO and introduced randomized algorithms for both
oracle models. However, no nontrivial deterministic algorithm was found
for a d-dimensional grid USO at that time. Attempting to find such an
algorithm, Barba et al. [1] first paid their attention to the planar case.
Here we state some known results in the planar case, given a 2-dimensional
grid USO with m × n vertices. Assume that N = m + n. In the randomized
setting, Gärtner et al. [7] prove an upper bound of O(log m · log n) for
the vertex query model, against a lower bound of Ω(log m + log n) claimed
by Barba et al. [1]. It is necessary to mention the performance of the most
natural Random-Edge algorithm on the planar grid USO, which chooses the
next queried vertex randomly from the out-going neighbours of the current
one. Gärtner et al. [9] proved it runs in Θ(log2 N ) under the Holt-Klee
condition and Milatz [17] extended this result for the general planar grid
USO. In the edge query model, the unique sink of a 2-dimensional grid USO
can be obtained with Θ(N ) queries in expectation [7]. In the deterministic
setting, Barba et al. [1] exhibit an algorithm using O(N log N ) vertex queries
to find the sink and another algorithm using O(N log4 7 ) edge queries. In

4

particular, they introduced an O(N ) algorithm for the vertex query model
under the Holt-Klee condition [10].
Our contributions. The main contribution of our paper is Lemma 4,
which states that we are able to exclude certain row and certain column from
being the global sink after querying a linear number of vertices in some way.
Based on it, we prove that m + n − 1 vertex queries suffice to determine the
global sink in the worst case, which coincide exactly with the lower bound
for the vertex
query model. Using it as a black box, we are able to exhibit an
√
2 log N
) deterministic algorithm for the edge query model. We note
O(N · 2
that for a d-dimensional grid USO our algorithm yields an upper bound of
O(N̂ dd/2e ) for the vertex query model, where N̂ denotes the sum of the sizes
of every dimension.
Paper organization. In Section 2 we establish some notations for a
planar grid USO and introduce some known properties. In Section 3 we
handle the vertex query model and give an optimal algorithm. We address
the edge query model based on the algorithm for the vertex query model in
Section 4. And at last we conclude the paper in Section 5 with some open
problems.

2

Preliminaries

First we provide some definitions and notations for the planar case. Denote
by Kn the complete graph with n vertices. An (m, n)-grid is the Cartesian
product Km × Kn . Its vertex set is defined to be the Cartesian product
[m] × [n], where [n] := {1, 2, . . . , n}. Elements in [n] are called coordinates,
and there are N = m + n coordinates. Throughout this paper, we identify
[m] × [n] with Km × Kn . A subgrid is then the Cartesian product I × J,
where I ⊆ [m] and J ⊆ [n]. For the sake of convenience, we say all vertices
with the same first-coordinate form a row. A column is defined analogously.
Hence two vertices are adjacent if and only if they are in the same row or in
the same column. Denote by uij the vertex at the cross of the i-th row and
the j-th column.
Let Tv (m, n) be the number of vertex queries needed in the worst case
to find the sink of an (m, n)-grid USO deterministically and Tv (n) for short
when m = n. Similarly, Te (m, n) and Te (n) are defined for the edge query
model. Following the tradition of the previous works [18, 1], in the vertex
query model the global sink must be queried even if we have already known
its position before it is queried. Thus, for instance, Tv (1) = 1 and Tv (2) = 3,
5

instead of Tv (1) = 0 and Tv (2) = 2. Readers will find the benefit of this
tradition shortly.
Now we introduce some known properties about the (m, n)-grid USO.
Lemma 1 ([7]). Every (m, n)-grid USO is acyclic.
Suppose G is an (m, n)-grid USO. This lemma allows us to define a partial
order on the vertex set [m] × [n] of G. For arbitrary two vertices u, v ∈ G,
define u  v if and only if either u = v or there exists a directed path
from u to v. In other word we just say u is larger than v. The unique sink
corresponds to the unique minimum vertex.
Barba et al. claimed a lower bound of m + n − 1 for the vertex query
model without a proof [1]. For the completeness we give a simple adversary
argument of this lower bound.
Lemma 2. Tv (m, n) ≥ m + n − 1.
Proof. Here is the answering strategy of the adversary. Let the first queried
vertex be the sink of the first row. Make all vertices in this row point out
to their adjacent vertices in other rows. Thus this vertex query eliminates
exactly the first row and any query of the other vertices in this row gives no
more information. By induction the i-th queried vertex eliminates exactly
the i-th row and therefore m − 1 vertex queries are necessary to eliminate all
m rows but the last row. At this time, we need n vertex queries instead of
n − 1 to find the sink of the last row, recalling the definition of Tv (m, n).
Induced grid USO. Barba et al. [1] discovered a simple construction of an induced grid USO from an (m, n)-grid USO, which helped a lot
their design of algorithms for both oracle models. It’s worth describing the
construction in detail.
Assume G is an (m, n)-grid USO. Let P = {P1 , . . . , Pk } be a partition of
[m] and Q = {Q1 , . . . , Ql } be a partition of [n]. Each Pi × Qj is a subgrid of
G. Let H be a (k, l)-grid with vertex set {Pi × Qj | i = 1, . . . , k, j = 1, . . . , l}.
As before, two distinct vertices x = Pi × Qj and y = Pi0 × Qj 0 are adjacent
in H if and only if they are in the same row or in the same column, i.e.
i = i0 or j = j 0 . Suppose that x and y are adjacent, it remains to determine
the orientation of edge xy in H. Recall that x and y are subgrids of G and
therefore by the USO property x and y have unique sinks ux and uy in G,
respectively. If ux has an outgoing edge to some vertex of y in G, then we
make x point to y in H. Otherwise we make v point to u. This orientation is
well-defined due to the acyclicity of an (m, n)-grid USO (see figure 2). Such
a grid H is called induced grid of G. What’s more, it was proved that the
induced grid H also suffices the USO property [1]:
6

Figure 2: (a) let P1 = {1, 2}, P2 = {3}, Q1 = {1} and Q2 = {2, 3}. The
(3, 3)-grid USO is divided into four subgrids accordingly. (b) The induced
grid USO defined according to the partition.
Lemma 3. Let G be a 2-dimensional grid USO and H be an induced grid
constructed from G. Then H is also a 2-dimensional grid USO and the sink
of H is the subgrid of G which contains the sink of G.

3

Vertex Query Model

This section is contributed to the vertex query model. We first explore
an important combinatorial property of the 2-dimensional grid USO. Then
we exploit this property to obtain an optimal deterministic algorithm using
m + n − 1 vertex queries in the worst case. Next we provide an intuitive
interpretation of this algorithm in connection with linear programs on N − 2polytope with N facets. To end this section, we adapt our algorithm to higher
dimensional case.
Let G be an (m, n)-grid USO. For a queried vertex v = uij , let Iv  [m]
be the collection of the first-coordinates such that u  v for any u ∈ Iv × {j}.
Note that v itself is included in Iv × {j}. Jv  [n] is defined analogously.
Clearly v is the unique sink of the subgrid Iv × Jv . Hence if v is not the
global sink of G, every vertex in the subgrid Iv × Jv is excluded from being
the global sink, since otherwise there would be two sinks in Iv × Jv . Suppose
v is not the global sink, the query of v eliminates exactly the corresponding
subgrid Iv × Jv .
Assume that m = n. First query arbitrary n vertices {v1 , . . . , vn } in
distinct rows and distinct columns. Suppose w.l.o.g. that none of them is
the sink of G, then the subgrids Ivi × Jvi are eliminated, for i = 1, . . . , n.

7

Figure 3: Induction on a (6, 6)-grid USO. White vertices are eliminated. All
vertices in I × {6} and {6} × J are larger than v6 .
Now there are a lot of eliminated vertices. The lemma below answers in a
way how many such vertices there are.
Lemma 4. Let G be an (n, n)-grid USO. After querying arbitrary n vertices
of G in distinct rows and distinct columns and eliminating corresponding
subgrids, at least one row and one column are eliminated.
Proof. We adopt induction on the scale n. There is nothing to prove in
the trivial case n = 1. Assume the lemma holds for smaller values of n.
Also we assume that none of the n vertices has ever been the global sink,
since otherwise the lemma naturally holds. Note that shuffling rows and
columns does not change the underlying structure of G. So by rearranging
the coordinates, we may assume that all queried vertices {v1 , . . . , vn } lie in
the diagonal, i.e. vi = uii , and further assume that for all 1 ≤ i < j ≤ n
either vi  vj or vi and vj are incomparable. Consider the (2, 2)-subgrid
Hi,j spanned by vi and vj . By the assumption there is no path from vj to vi
in Hi,j . Hence by the USO property vj cannot be the source of Hi,j , which
implies in Hi,j there is at least one incoming edge of vj . This simple fact was
first observed by Barba et al. [1].
In particular, vn has at least one incoming edge in each subgrid Hi,n ,
which means either i ∈ Ivn or i ∈ Jvn , for 1 ≤ i ≤ n − 1. Let I = Ivn ∩ [n − 1]
8

and J = [n − 1]\I. Clearly J ⊆ Jvn ∩ [n − 1], since J ∩ Ivn = ∅. Accordingly,
we divide the (n − 1, n − 1)-grid spanned by {v1 , . . . , vn−1 } into subgrids
I × I, J × J, I × J and J × I. The subgrid J × I is of no relevance in our
discussion. The subgrid I × J ⊆ Ivn × Jvn and therefore all of its vertices are
eliminated. Square subgrids I × I and J × J both contain queried vertices
in their diagonals, respectively. So by the inductive assumption both of
them contain one eliminated row and one eliminated column, respectively.
Let i ∈ I be the coordinate such that {i} × I is the eliminated row in
I × I. The subgrid {i} × J ⊆ I × J and therefore is eliminated. The
vertex {i} × {n} ∈ Ivn × {n} and is also eliminated. To sum up, the row
{i} × [n] = {i} × (I ∪ J ∪ n) is eliminated. Similarly, let j ∈ J be the
coordinate such that J × {j} is the eliminated column in J × J. The column
[n] × {j} turns out to be an eliminated column of the original grid by the
same argument. The proof now is completed. See Figure 3 for an intuitive
example.
Lemma 4 makes full use of the information from the queried vertices and
naturally leads to the following algorithm depicted as Algorithm 1.
Algorithm 1: Diagonal Algorithm
Input: An (n, n)-grid USO G
Output: The unique sink of G
1 query arbitrary n vertices in distinct rows and distinct columns;
2 while the sink has not been queried do
3
eliminate one row and one column, say the i-th row and the j-th
column;
4
if two distinct queried vertex uij 0 and ui0 j are eliminated then
5
query vertex ui0 j 0 ;
6
end
7 end
We first query arbitrary n vertices in distinct rows and distinct columns
(line 1). By Lemma 4, there are one row and one column excluded from being
the global sink, say the i-th row and the j-th column (line 3). Now we need to
handle a subgrid USO of scale n − 1. Note that at most 2 queried vertices are
eliminated, since each row (or column) contains exactly one queried vertex.
If two distinct queried vertex uij 0 and ui0 j are eliminated, one more query of
vertex ui0 j 0 would make the subgrid contain n − 1 queried vertices in distinct
rows and distinct columns (line 4-6). Otherwise, the subgrid has already
contained n − 1 such queried vertices. At either case, we can apply Lemma 4
9

again and at most another n − 1 queries suffice to find the global sink. The
argument above leads to the theorem below.
Theorem 1. There exists a deterministic algorithm using 2n − 1 vertex
queries in the worst case to find the unique sink of an (n, n)-grid USO.
We can easily extend Algorithm 1 to an arbitrary (m, n)-grid USO. Assume that m < n. First query m vertices in distinct rows and distinct
columns. Then the m columns with queried vertices in them form an (m, m)subgrid USO. By Lemma 4, one column is eliminated, and there remains
m − 1 queried vertices. Next, one more appropriate vertex query would
again exclude one column. Repeat this procedure until there remains exactly m columns, i.e. an (m, m)-subgrid USO, which contains m − 1 queried
vertices. Now we can eliminate both one row and one column at the same
time after every vertex query and another m queries suffice to determine the
global sink. To conclude we have
Theorem 2. There exists a deterministic algorithm using m + n − 1 vertex
queries in the worst case to find the unique sink of an (m, n)-grid USO.
Combined with Lemma 2, this theorem implies that Tv (m, n) = m+n−1,
so Algorithm 1 is optimal.
As is mentioned before, the vertex-edge graph of a (N − 2)-polytope
with N facets is isomorphic to an (m, n)-grid USO G for some m, n with
N = m+n. There are totally N coordinates in G. Each coordinate represents
a facet of the original polytope. Note that a vertex v = uij of G is the
intersection of some (N − 2) facets. The coordinates i and j mean that v
does not lie in the corresponding facets. Two vertices are adjacent in the
vertex-edge graph if and only if both of them belong to exactly the same
N − 3 facets. If in some way (e.g. by Lemma 4), the i-th row (or column) is
excluded from being the global sink, we can deduce that the global sink must
lie in the corresponding facet. The procedure of Algorithm 1 becomes rather
clear. At each step, Algorithm 1 arbitrarily queries a new vertex which is
not adjacent to the previously queried vertices (line 1) in order to involve as
many facets as possible. Once every vertex is adjacent to at least one queried
vertex, it is guaranteed that the global sink must belong to certain facet or
(intersection of several facets) (line 3). Later queries are indeed restricted in
that facet (line 4-6). From the view of linear programs, such an algorithm is
rather interesting.
Though being less practical than the edge query model, the vertex query
model still has potential applications. One of them is to reach a better upper
bound for the general grid USO of d dimension, combined with the inherited
10

grid USO structure. Roughly speaking, fix the coordinates of two dimensions
of size n1 and n2 , and vertices share the fixed two coordinates form a subgrid
of the original grid. The vertex set of the inherited grid is the collection of
the n1 × n2 subgrids. The definition and the orientation of the edges are the
same as those in the induced grid USO. Let N̂ be the sum of the sizes of each
dimension and T̂v (d) be the time overhead for the grid USO of d dimension
in the worst case. Running Algorithm 1 on the inherited grid USO yields the
following recurrence
T̂v (d) ≤ (n1 + n2 − 1) · T̂v (d − 2).
By solving it, we have the following corollary,
Corollary 1. There exists a deterministic algorithm using O(N̂ dd/2e ) vertex
queries in the worst case to find the unique sink of a d-dimensional grid USO.

4

Edge Query Model

Though being optimal, Algorithm 1 may not be a good choice to solve optimization problems like one line and N points, for implementing a vertex
query actually takes linear time. However, there are potential applications
of this result. An immediate one is a fast algorithm under the edge query
model.
Throughout this section we assume that m = n, since one can always add
rows or columns to make the grid square without changing the structure of
the original grid and the position of the global sink. We extend the divideand-conquer strategy in [1] to an almost linear algorithm using Algorithm 1
as a black box. The formal description is depicted as Algorithm 2.
Algorithm 2: Divide-and-Conquer
Input: An (n, n)-grid USO G
Output: The unique sink of G
1 construct an induced (k, k)-grid USO H from G;
2 run Algorithm 1 on H under the vertex query model;
Let G be an (n, n)-grid USO, and H be an induced (k, k)-grid USO constructed from G. The construction of H is indeed two respective partitions
of [n] and takes constant time (line 1). As is shown in Algorithm 2, the main
idea is to run Algorithm 1 on H under the vertex query model (line 2). By
Theorem 1, 2k − 1 vertex queries suffice to determine the sink of H. Recall
11

that each vertex in H corresponds to a subgrid in G, and that the sink of
H is the subgrid of G which contains the sink of G. Note that a vertex
query returns the orientation of all the incident edges. Hence according to
the definition of the orientation of edges in H, to implement a vertex query
in H, we need to (i) find the sink of the corresponding subgrid in G and (ii)
query all edges incident to this local sink in G. In a word, a vertex query
in H is equivalent to at most Te ( nk ) + 2n − 2 edge queries in G. The above
argument implies the recurrence below,
n
Te (n) ≤ (2k − 1) Te ( ) + 2n − 2 .
k




Note that our careful definition of Tv (m, n), the number of vertex queries
in the worst case, pays off here — the sink of H has already been queried,
which means that the sink of the corresponding subgrid in G, i.e. the sink
of G, has been found.
Solve the recurrence will get Te (n) = O(nlogk (2k−1) ) if setting k = O(1),
which √
coincides with the result in [1] when k = 4. Furthermore, we set
k = 22√ log n , where log means the logarithm to base 2. Assume that Te (n) ≤
cn · 22 log n , where c > 4, for smaller values of n, then we have
√
Te (n)

≤

2kc nk
q
2

log n−log k

2

·2

√

log n−2

+ 4kn
√
log n
2 log n
+ 4n · 2
.

= 2cn · 2
√
2 log n
To make Te (n) ≤ cn · 2
, we only need to assure
q
√
√
2c
2( log n− log n−2 log n)
≥
.
2
c−4

The left side is monotone decreasing and its limit
√ is 4, hence setting c ≥ 8
2 log n
the inequality holds. √
Therefore Te (n) = O(n · 2
).
Notice that n · 22 log n = o(n1+ ), for any  > 0. Algorithm 2 is mildly
superlinear. We conclude this section by the following theorem,
√
2 log N
) deterministic algorithm to find
Theorem 3. There exists an O(N · 2
the sink of an (m, n)-grid USO under the edge query model, where N = m+n.

5

Conclusion

In this paper, we have discovered a new combinatorial property (Lemma 4)
of the 2-dimensional grid USO and developed deterministic algorithms for
12

both oracle models based on it, one optimal, the other nearly optimal. In
the randomized setting, however, all the known randomized algorithms only
reach an upper bound of O(log2 N ), against the lower bound of Ω(log N ). By
further exploiting Lemma 4, one may devise an optimal algorithm to close
the gap. In the general d-dimensional grid USO, it is of interest whether
there exists a similar combinatorial property.

References
[1] Luis Barba, Malte Milatz, Jerri Nummenpalo, and Antonis Thomas. Deterministic algorithms for unique sink orientations of grids. Computing
and Combinatorics Conference, pages 357–369, 2016.
[2] Robert G Bland. New finite pivoting rules for the simplex method.
Mathematics of Operations Research, 2(2):103–107, 1977.
[3] Richard W Cottle and George B Dantzig. A generalization of the linear
complementarity problem. Journal of Combinatorial Theory, 8(1):79–
90, 1970.
[4] Stefan Felsner, Bernd Gärtner, and Falk Tschirschnitz. Grid orientations, (d,d + 2)-polytopes, and arrangements of pseudolines. Discrete
and Computational Geometry, 34(3):411–437, 2005.
[5] Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex
algorithm. In Proceedings of the forty-third annual ACM symposium on
Theory of computing, pages 283–292. ACM, 2011.
[6] Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. Randomfacet and random-bland require subexponential time even for shortest
paths. arXiv preprint arXiv:1410.7530, 2014.
[7] Bernd Gärtner, Walter Morris, and Leo Rüst. Unique sink orientations
of grids. Algorithmica, 51(2):200–235, 2008.
[8] Bernd Gärtner and Ingo Schurr. Linear programming and unique sink
orientations. Symposium on Discrete Algorithms, pages 749–757, 2006.
[9] Bernd Gärtner, Falk Tschirschnitz, Emo Welzl, József Solymosi, and
Pavel Valtr. One line and n points. Random Structures and Algorithms,
23(4):453–471, 2003.

13

[10] Fred Holt and Victor Klee. A proof of the strict monotone 4-step conjecture. Contemporary Mathematics, 223:201–216, 1999.
[11] Gil Kalai. A subexponential randomized simplex algorithm. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 475–482. ACM, 1992.
[12] Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on
Theory of computing, pages 302–311. ACM, 1984.
[13] Leonid G Khachiyan. Polynomial algorithms in linear programming.
USSR Computational Mathematics and Mathematical Physics, 20(1):53–
72, 1980.
[14] Jiřı́ Matoušek. Lower bounds for a subexponential optimization algorithm. Random Structures and Algorithms, 5(4):591–607, 1994.
[15] Jiřı́ Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound
for linear programming. Algorithmica, 16(4-5):498–516, 1996.
[16] Jiřı́ Matoušek and Tibor Szabó. Random edge can be exponential on
abstract cubes. Advances in Mathematics, 204(1):262–277, 2006.
[17] Malte Milatz. Directed random walks on polytopes with few facets.
CoRR, abs/1705.10243, 2017.
[18] Tibor Szabó and Emo Welzl. Unique sink orientations of cubes. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium
on, pages 547–555. IEEE, 2001.

14

