---
abstract: 'Sharir and Welzl introduced an abstract framework for optimization problems, called [*LP-type problems*]{} or also [*generalized linear programming problems*]{}, which proved useful in algorithm design.  We define a new, and as we believe, simpler and more natural framework: [*violator spaces*]{}, which constitute a proper generalization of LP-type problems.  We show that Clarkson’s randomized algorithms for low-dimensional linear programming work in the context of violator spaces.  For example, in this way we obtain the fastest known algorithm for the *${\mathrm{P}}$-matrix generalized linear complementarity problem* with a constant number of blocks.  We also give two new characterizations of LP-type problems: they are equivalent to [*acyclic*]{} violator spaces, as well as to [*concrete*]{} LP-type problems (informally, the constraints in a concrete LP-type problem are subsets of a linearly ordered ground set, and the value of a set of constraints is the minimum of its intersection).' 
address:
- ' Institute of Theoretical Computer Science, ETH Zürich, 8092 Zürich, Switzerland '
- ' Department of Applied Mathematics and Institute of Theoretical Computer Science, Charles University, Malostranské nám.  25, 118 00  Praha 1, Czech Republic '
author:
- 'B. Gärtner'
- 'J. Matoušek'
- 'L. Rüst'
- 'P. Škovroň'
title: 'Violator Spaces: Structure and Algorithms '
---

,

,

,

LP-type problem ,generalized linear programming ,violator space ,Clarkson’s algorithms ,unique sink orientation , generalized linear complementarity problem

Introduction
============

The framework of LP-type problems, invented by Sharir and Welzl in 1992 [@sw-cblpr-92], has become a well-established tool in the field of geometric optimization.  Its origins are in linear programming: Sharir and Welzl developed a randomized variant of the dual simplex algorithm for linear programming and showed that this algorithm actually works for a more general class of problems they called LP-type problems. 

For the theory of linear programming, this algorithm constituted an important progress, since it was later shown to be *subexponential* in the RAM model [@msw-sblp-92].  Together with a similar result independently obtained by Kalai [@k-srsa-92], this was the first linear programming algorithm provably requiring a number of arithmetic operations subexponential in the dimension and number of constraints (independent of the precision of the input numbers). 

For many other geometric optimization problems in fixed dimension, the algorithm by Sharir and Welzl was the first to achieve expected linear runtime, simply because these problems could be formulated as LP-type problems.  The class of LP-type problems for example includes the problem of computing the minimum-volume ball or ellipsoid enclosing a given point set in ${{\mathbf{R}}}^d$, and the problem of finding the distance of two convex polytopes in ${{\mathbf{R}}}^d$. Many other problems have been identified as LP-type problems over the years [@msw-sblp-92; @a-bbhdn-94; @a-httgl-94; @bsv-dsapg-01; @halman]. 

Once it is shown that a particular optimization problem is an LP-type problem, and certain algorithmic primitives are implemented for it, several efficient algorithms are immediately at our disposal: the Sharir–Welzl algorithm, two other randomized optimization algorithms due to Clarkson [@c-lvali-95] (see [@gw-lpraf-96; @cm-ltdao-96] for a discussion of how it fits the LP-type framework), a deterministic version of it [@cm-ltdao-96], an algorithm for computing the minimum solution that violates at most $k$ of the given $n$ constraints [@m-gofvc-95], and probably more are to come in the future. 

The framework of LP-type problems is not only a prototype for concrete optimization problems, it also serves as a mathematical tool by itself, in algorithmic [@GWSampl01; @ChanTukey] and non-algorithmic contexts [@a-spiht-96]. 

An (abstract) LP-type problem is given by a finite set $H$ of [*constraints*]{} and a [*value*]{} $w(G)$ for every subset $G\subseteq H$. The values can be real numbers or, for technical convenience, elements of any other linearly ordered set.  Intuitively, $w(G)$ is the minimum value of a solution that satisfies all constraints in $G$. The assignment $G\mapsto w(G)$ has to obey the axioms in the following definition. 

\[def:lptype\] An [*abstract LP-type problem*]{} is a quadruple $(H,w,W,\leq)$, where $H$ is a finite set, $W$ is a set linearly ordered by $\leq$, and $w\colon 2^H\to W$ is a mapping satisfying the following two conditions:

  --------------- -------------------------------------------------------------------------
  Monotonicity:   for all $F\subseteq G\subseteq H$ we have $w(F)\leq w(G)$, and
  Locality:       for all $F\subseteq G\subseteq H$ and all $h\in H$ with $w(F)=w(G)$ and
                  $w(G)<w(G\cup\{h\})$, we have $w(F)<w(F\cup\{h\})$.
  --------------- -------------------------------------------------------------------------

As our running example, we will use the smallest enclosing ball problem, where $H$ is a finite point set in ${{\mathbf{R}}}^d$ and $w(G)$ is the radius of the smallest ball that encloses all points of $G$. In this case monotonicity is obvious, while verifying locality requires the nontrivial but well known geometric result that the smallest enclosing ball is unique for every set. 

It seems that the order $\leq$ of subsets is crucial; after all, LP-type problems model *optimization problems*, and indeed, the subexponential algorithm for linear programming and other LP-type problems [@msw-sblp-92] heavily relies on such an order. 

A somewhat deeper look reveals that often, we only care whether two subsets have the *same* value, but not how they compare under the order $\leq$. The following definition is taken from [@sw-cblpr-92]:

\[def:lp\_type\_basis\] Consider an abstract LP-type problem $(H,w,W,\leq)$. We say that $B\subseteq H$ is a [*basis*]{} if for all proper subsets $F\subset B$ we have $w(F)\neq w(B)$. For $G\subseteq H$, a *basis of $G$* is a minimal subset $B$ of $G$ with $w(B)=w(G)$.

We observe that a minimal subset $B\subseteq G$ with $w(B)=w(G)$ is indeed a basis. 

Solving an abstract LP-type problem $(H,w,W,\leq)$ means to find a basis of $H$. In the smallest enclosing ball problem, a basis of $H$ is a minimal set $B$ of points such that the smallest enclosing ball of $B$ has the same radius (and is in fact the same) as the smallest enclosing ball of $H$, $w(B)=w(H)$.

In defining bases, and in saying what it means to solve an LP-type problem, we therefore do not need the order $\leq$. The main contribution of this paper is that many of the things one can prove about LP-type problems do not require a concept of order. 

We formalize this by defining the new framework of *violator spaces*.  Intuitively, a violator space is an LP-type problem without order.  This generalization of LP-type problems is proper, and we can exactly characterize the violator spaces that “are” LP-type problems.  In doing so, we also establish yet another equivalent characterization of LP-type problems that is closer to the applications than the abstract formulation of Definition \[def:lptype\].  In a concrete LP-type problem, the constraints are not just elements of a set, but they are associated with subsets of some linearly ordered ground set $X$, with the minimal elements in the intersections of such subsets corresponding to “solutions”.  The framework of concrete LP-type problems is similar to the model presented in [@a-httgl-94] as a mathematical programming problem, with a few technical differences. 

These are our main findings on the structural side.  Probably the most surprising insight on the algorithmic side is that Clarkson’s algorithms [@c-lvali-95] work for violator spaces of fixed dimension, leading to an expected linear-time algorithm for “solving” the violator space.  Clarkson’s algorithms were originally developed for linear programs with small dimension.  They can be generalized for LP-type problems [@gw-lpraf-96; @cm-ltdao-96].  The fact that the scheme also works for violator spaces may come as a surprise since the structure of violator spaces is not acyclic in general (in contrast to LP-type problems).  The LP-type algorithm from [@msw-sblp-92] is also applicable to violator spaces, but its analysis breaks down. 

We give an application of Clarkson’s algorithms in the more general setting by linking our new violator space framework to well-known abstract and concrete frameworks in combinatorial optimization.  For this, we show that any *unique sink orientation* (USO) of the cube [@SW; @grid_uso; @M02; @MatUSO; @MCube; @Develin; @MS; @SchSz; @SS; @lptouso] or the more general grid [@grid_uso] gives rise to a violator space, but not to an LP-type problem in general.  Grid USO capture some important problems like linear programming over products of simplices, *generalized linear complementarity problems* over $\mathrm{P}$-matrices [@grid_uso] or games like parity, mean-payoff, and simple stochastic games [@sweden1; @sweden2; @ssg_pglcp]. 

We show that we can find the sink in a unique sink orientation by solving the violator space, for example with Clarkson’s algorithms.  A concrete new result is obtained by applying this to ${\mathrm{P}}$-matrix generalized linear complementarity problems.  These problems are not known to be polynomial-time solvable, but NP-hardness would imply NP=co-NP [@Meg; @grid_uso].  Since any ${\mathrm{P}}$-matrix generalized linear complementarity problem gives rise to a unique sink orientation [@grid_uso], we may use violator spaces and Clarkson’s algorithms to solve the problem in expected linear time in the (polynomially solvable) case of a *fixed* number of *blocks*.  This is optimal and beats all previous algorithms. 

The rest of the paper is organized as follows.  In Section \[sec:basics\], we formally define the frameworks of concrete LP-type problems and violator spaces, along with their essential terminology.  Then we state our main structural result. 

In Section \[sec:mainproof\], we prove this result by deriving the equivalence of abstract and concrete LP-type problems, and of *acyclic* violator spaces. 

Section \[sec:clarkson\] shows that Clarkson’s algorithms work for (possibly cyclic) violator spaces.  Section \[grid\_uso\], finally, shows how unique sink orientations induce violator spaces.  A unique sink orientation can be cyclic, and a cyclic orientation gives rise to a cyclic violator space.  Unique sink orientations are therefore nontrivial examples of possibly cyclic violator spaces. 

Structural Results {#sec:basics}
==================

Concrete LP-type problems. 
--------------------------

Although intuitively one thinks about $w(G)$ as the value of an optimal solution of an optimization problem, the solution itself is not explicitly represented in Definition \[def:lptype\].  In specific geometric examples, the constraints can usually be interpreted as a subset of some ground set $X$ of points, and the optimal solution for $G$ is the point with the smallest value in the intersection of all constraints in $G$. For example, in linear programming, the constraints are halfspaces, the value is given by the objective function, and the optimum is the point with minimum value in the admissible region, i.e., the intersection of the halfspaces.  In order to have a unique optimum for every set of constraints (which is needed for $w$ to define an LP-type problem), one assumes that the points are linearly ordered by the value; for linear programming, we can always take the lexicographically smallest optimal solution, for instance. 

Such an interpretation is possible for the smallest enclosing ball problem too, although it looks a bit artificial.  Namely, the “points” of $X$ are all balls in ${{\mathbf{R}}}^d$, where the ordering can be an arbitrary linear extension of the partial ordering of balls by radius.  The “constraint” for a point $h\in H$ is the set of all balls containing $h$.

The following definition captures this approach to LP-type problems. 

\[def:concrete\_LPtype\] A [*concrete LP-type problem*]{} is a triple $(X,\preceq,{\mathcal H})$, where $X$ is a set linearly ordered by $\preceq$, ${\mathcal H}$ is a finite multiset whose elements are subsets of $X$, and for any ${\mathcal G}\subseteq{\mathcal H}$, if the intersection $\bigcap{\mathcal G}:=\bigcap_{G\in\mathcal{G}}G$ is nonempty, then it has a minimum element with respect to $\preceq$ (for ${\mathcal G}=\emptyset$ we define $\bigcap{\mathcal G}:=X$). 

The definition allows $\mathcal H$ to be a multiset, i.e., a constraint set $A\subseteq X$ may be included several times.  For example, in an instance of linear programming, some constraints can be the same, which we can reflect by this.  In Subsection \[sec:examples\] we provide an example of an abstract LP-type problem, for which the multiplicity comes in handy to represent it as a concrete LP-type problem. 

A similar model has been presented in [@a-httgl-94] (mathematical programming problem).  The slight difference is that it allows several points to have the same value but the constraints form a set rather than a multiset. 

Bases are defined analogously to Definition \[def:lp\_type\_basis\]. 

\[def:concrete\_basis\] Consider a concrete LP-type problem $(X,\preceq,{\mathcal H})$. We say that $\mathcal{B}\subseteq\mathcal{H}$ is a [*basis*]{} if for all proper submultisets $\mathcal{F}\subset\mathcal{B}$ we have $\min(\bigcap\mathcal{F})\prec
\min(\bigcap\mathcal{B})$. For $\mathcal{G}\subseteq\mathcal{H}$, a *basis of $\mathcal{G}$* is a minimal $\mathcal{B}\subseteq\mathcal{G}$ with $\min(\bigcap\mathcal{B})=\min(\bigcap\mathcal{G})$.

As before, a minimal $\mathcal{B}\subseteq\mathcal{G}$ with $\min(\bigcap\mathcal{B})=\min(\bigcap\mathcal{G})$ is indeed a basis. 

Given any concrete LP-type problem ${\mathcal P}=(X,\preceq,{\mathcal H})$, we obtain an abstract LP-type problem $P=({\mathcal H},w,X,\preceq)$ according to Definition \[def:lptype\] by putting $w({\mathcal G})=\min(\bigcap {\mathcal G})$ (or $w({\mathcal G})=+\infty$, if $\bigcap{\mathcal G}$ is empty), as is easy to check (proof omitted).  It is clear that $\mathcal{B}\subseteq\mathcal{G}$ is a basis of $\mathcal{G}$ in $P$ if and only if $\mathcal{B}$ is a basis of $\mathcal{G}$ in $\mathcal{P}$. We say that $P$ is *basis-equivalent* to $\mathcal{P}$.

Somewhat surprising is the converse, which we prove below in Theorem \[thm:main\]: Any abstract LP-type problem $(H,w,W,\leq)$ has a “concrete representation”, that is, a concrete LP-type problem that is basis-equivalent to $(H,w,W,\leq)$.

Strictly speaking, if the multiset ${\mathcal H}$ in the concrete LP-type problem has elements with multiplicity bigger than 1, then ${\mathcal H}$ cannot be used as the set of constraints for the abstract LP-type problem (since it is not a set).  However, we can bijectively map $\mathcal H$ to a set, i.e., we take any set $H$ with $|H|=|{\mathcal H}|$ and a mapping $f\colon H\to{\mathcal H}$ such that for any $\bar h\in{\mathcal H}$, the number of elements $h\in H$ that map to $\bar h$ is equal to the multiplicity of $\bar h$. For $G\subseteq H$ we then define $w(G)=\min(\bigcap_{g\in G} f(g))$ which gives us a fair abstract LP-type problem $P=(H,w,X,\preceq)$ basis-equivalent to $\mathcal{P}$. In this case, by basis-equivalence we mean the existence of a suitable mapping $f$ together with the condition that $B\subseteq G$ is a basis of $G$ in $P$ if and only if the multiset $\{f(b)\colon b\in B\}$ is a basis of $\{f(g)\colon g\in G\}$ in $\mathcal{P}$.

Violator spaces. 
----------------

Let $(H,w,W,\leq)$ be an abstract LP-type problem.  It is natural to define that a constraint $h\in H$ [*violates*]{} a set $G\subseteq H$ of constraints if $w(G\cup\{h\})>w(G)$. For example, in the smallest enclosing ball problem, a point $h$ violates a set $G$ if it lies outside of the smallest ball enclosing $G$ (which is unique). 

The *violator mapping* of $(H,w,W,\leq)$ is defined by ${{\sf V}}(G)=\{h\in H\colon w(G\cup\{h\})>w(G)\}$. Thus, ${{\sf V}}(G)$ is the set of all constraints violating $G$.

It turns out that the knowledge of ${{\sf V}}(G)$ for all $G\subseteq H$ is enough to describe the “structure” of an LP-type problem.  That is, while we cannot reconstruct $W$, $\leq$, and $w$ from this knowledge, it is natural to consider two LP-type problems with the same mapping ${{\sf V}}\colon 2^H\to 2^H$ the same (isomorphic).  Indeed, the algorithmic primitives needed for implementing the Sharir–Welzl algorithm and the other algorithms for LP-type problems mentioned above can be phrased in terms of testing violation (does $h\in {{\sf V}}(G)$ hold for a certain set $G\subseteq H$?),  and they never deal explicitly with the values of $w$.

We now introduce the notion of [*violator space*]{}:

\[def:vs\] A [*violator space*]{} is a pair $(H,{{\sf V}})$, where $H$ is a finite set and ${{\sf V}}$ is a mapping $2^H\to2^H$ such that

  -------------- ----------------------------------------------------------------------------------
  Consistency:   $G\cap {{\sf V}}(G)=\emptyset$ holds for all $G\subseteq H$, and
  Locality:      for all $F\subseteq G\subseteq H$, where $G\cap {{\sf V}}(F)=\emptyset$, we have
                 ${{\sf V}}(G)={{\sf V}}(F)$.
  -------------- ----------------------------------------------------------------------------------

A basis of a violator space is defined in analogy to a basis of an LP-type problem. 

\[def:vbasis\] Consider a violator space $(H,{{\sf V}})$. We say that $B\subseteq H$ is a [*basis*]{} if for all proper subsets $F\subset B$ we have $B\cap {{\sf V}}(F)\neq\emptyset$. For $G\subseteq H$, a *basis of $G$* is a minimal subset $B$ of $G$ with ${{\sf V}}(B)={{\sf V}}(G)$.

Observe that a minimal subset $B\subseteq G$ with ${{\sf V}}(B)={{\sf V}}(G)$ is indeed a basis: Assume for contradiction that there is a set $F\subset B$ such that $B\cap {{\sf V}}(F)=\emptyset$. Locality then yields ${{\sf V}}(B)={{\sf V}}(F)={{\sf V}}(G)$, which contradicts minimality of $B$.

We will check in Subsection \[sec:abstract-&gt;acyclicVS\] that the violator mapping of an abstract LP-type problem satisfies the two axioms above.  Consistency is immediate: since $w(G)=w(G\cup\{h\})$ for $h\in G$, no element in $G$ violates $G$. The locality condition has the following intuitive interpretation: adding only non-violators to a set does not change the value. 

We actually show more: given an abstract LP-type problem $(H,w,W,{\leq})$, the pair $(H,{{\sf V}})$, with ${{\sf V}}$ being the violator mapping, is an *acyclic* violator space. ( Acyclicity of a violator space will be defined later in Definition \[def:vsetord\].)  It turns out in Subsection \[sec:acyclicVS-&gt;concrete\] that acyclicity already characterizes the violator spaces obtained from LP-type problems, and thus any acyclic violator space can be represented as an LP-type problem (abstract or concrete).  These equivalences are stated in our main theorem. 

\[thm:main\] The axioms of abstract LP-type problems, of concrete LP-type problems, and of acyclic violator spaces are equivalent.  More precisely, every problem in one of the three classes has a basis-equivalent problem in each of the other two classes. 

The construction is illustrated on simple instances of problems of linear programming and the smallest enclosing ball in Subsection \[sec:examples\].  Several more results concerning violator spaces have been achieved in the MSc.  thesis of the fourth author [@Skovron]. 

Equivalence of LP-type Problems and Acyclic Violator Spaces {#sec:mainproof}
===========================================================

In this section we prove Theorem \[thm:main\]. 

Preliminaries on Violator Spaces {#sec:preliminaries}
--------------------------------

To show that every acyclic violator space $(H,{{\sf V}})$ originates from some concrete LP-type problem, we need an appropriate linearly ordered set $X$ of “points”, and then we will identify the elements of $H$ with certain subsets of $X$.

What set $X$ will we take?  Recall that for smallest enclosing balls, $X$ is the set of all balls, and the subset for $h\in H$ is the subset of balls containing $h$. It is not hard to see that we may restrict $X$ to smallest enclosing balls of *bases*; in fact, we may choose $X$ as the set of bases, in which case the subset for $h$ becomes the set of bases not violated by $h$.

This also works for general acyclic violator spaces, with bases suitably ordered.  The only blemish is that we may get several minimal bases for $G\subseteq H$; for smallest enclosing balls, this corresponds to the situation in which several bases define the same smallest enclosing ball.  To address this, we will declare such bases as equivalent and choose $X$ as the set of all equivalence classes instead. 

In the following, we fix a violator space $(H,{{\sf V}})$. The set of all bases in $(H,{{\sf V}})$ will be denoted by $\mathcal B$.

\[def:vequiv\] $B,C\in \mathcal B$ are *equivalent*, $B\sim C$, if ${{\sf V}}(B)={{\sf V}}(C)$.

Clearly, the relation $\sim$ defined on $\mathcal{B}$ is an equivalence relation.  The equivalence class containing a basis $B$ will be denoted by $[B]$.

Now we are going to define an ordering of the bases, and we derive from this an ordering of the equivalence classes as well as the notion of acyclicity in violator spaces. 

\[def:vsetord\] For $F,G\subseteq H$ in a violator space $(H,{{\sf V}})$, we say that $F\leq_0 G$ ($F$ is [*locally smaller*]{} than $G$) if $F\cap {{\sf V}}(G)=\emptyset$.

For equivalence classes $[B],[C]\in{{{\mathcal B}/\!\sim}}$, we say that $[B]\leq_0 [C]$ if there exist $B'\in[B]$ and $C'\in[C]$ such that $B'\leq_0 C'$.

We define the relation $\leq_1$ on the equivalence classes as the transitive closure of $\leq_0$. The relation $\leq_1$ is clearly reflexive and transitive.  If it is antisymmetric, we say that the violator space is [*acyclic*]{}, and we define the relation $\leq$ as an arbitrary linear extension of $\leq_1$.

The intuition of the *locally-smaller* notion comes from LP-type problems: if no element of $F$ violates $G$, then $G\cup F$ has the same value as $G$ (this is formally proved in Lemma \[lem:conseqloc\] below), and monotonicity yields that value-wise, $F$ is smaller than or equal to $G$.

Note that in the definition of $[B]\leq_0[C]$ we do not require $B'\leq_0 C'$ to hold for [*every*]{} $B'$ and $C'$. In fact $B'\not\leq_0 C'$ may happen for some bases $B'$ and $C'$, but $C'\leq_0 B'$ can not hold (which can easily be shown).  To show that acyclicity does not always hold, we conclude this section with an example of a cyclic violator space. 

We begin with an intuitive geometric description; see Figure \[fig:cyclic\].  We consider a triangle without the center point.  We say that a point is “locally smaller” if it is farther clockwise with respect to the center.  The constraints in our violator space are the three halfplanes $f,g,h$.

The locally smallest point within each halfplane is marked, and a halfplane violates a set of halfplanes if it does not contain the locally smallest point in their intersection. 

Now we specify the corresponding violator space formally.  We have $H=\{f,g,h\}$, and ${{\sf V}}$ is given by the following table:

0.3cm

        $G$         $\emptyset$   $f$   $g$   $h$   $f,g$   $f,h$   $g,h$     $f,g,h$
  ---------------- ------------- ----- ----- ----- ------- ------- ------- -------------
   ${{\sf V}}(G)$     $f,g,h$     $h$   $f$   $g$    $h$     $g$     $f$    $\emptyset$

This $(H,{{\sf V}})$ is really a violator space, since we can easily check both consistency and locality.  The bases are $\emptyset$, one-element sets, and $H$. We have $\{f\}\leq_0\{h\}\leq_0\{g\}\leq_0\{f\}$, but none of the one-element bases are equivalent; i.e., $\leq_1$ is not antisymmetric. 

Abstract LP-type Problems yield Acyclic Violator Spaces {#sec:abstract->acyclicVS}
-------------------------------------------------------

In this subsection, we show that the violator mapping of an abstract LP-type problem is an acyclic violator space.  To this end, we need the following two lemmas. 

\[lem:conseqloc\] Consider an abstract LP-type problem $(H,w,W,\leq)$ with violator mapping ${{\sf V}}$. Let $A,B\subseteq H$, where $B$ is not violated by any $h\in A$ ($A\cap {{\sf V}}(B)=\emptyset$).  Then $w(A\cup B)=w(B)$.

From monotonicity, we immediately obtain the inequality “$\geq$”.  The inequality “$\leq$” can be shown by induction on $|A|$. If $|A|=1$, i.e., $A=\{h\}$, then $w(B\cup\{h\})>w(B)$ would imply that $B$ is violated by $h\in A$, a contradiction. 

Let $|A|>1$ and $A=A_0\mathbin{\dot\cup}\{h\}$ (disjoint union).  From the induction hypothesis we have $w(B\cup A_0)=w(B)$. Now, if $w(B\cup A_0)<w(B\cup A_0\cup \{h\})$, then by locality (for $B\cup A_0$, $B$ and $h$) we get $w(B)<w(B\cup\{h\})$. This means that $h\in{{\sf V}}(B)$, and since $h\in A$ we have $h\in A\cap{{\sf V}}(B)$, a contradiction.  So $w(B)=w(B\cup A_0) \geq w(B\cup A_0\cup\{h\})=w(B\cup A)$. We have proved $w(A\cup B)\leq w(B)$.

\[lem:separbasis\] Consider an abstract LP-type problem $(H,w,W,\leq)$ with violator mapping ${{\sf V}}$. Then for any $A,B\subseteq H$ with ${{\sf V}}(A)={{\sf V}}(B)$ we have $w(A)=w(B)$. Conversely, $w(A)=w(B)=w(A\cup B)$ implies ${{\sf V}}(A)={{\sf V}}(B)$. In particular, if $A\subseteq B$ and $w(A)=w(B)$, then ${{\sf V}}(A)={{\sf V}}(B)$.

Note that the condition $w(A)=w(B)$ generally does not suffice for ${{\sf V}}(A)={{\sf V}}(B)$. For example, having any $H$, we can define $w$ by $w(G)=|G|$ for all $G\subseteq H$ (it can be checked that it is an abstract LP-type problem).  Then any $G$’s of the same size have the same $w$, however, ${{\sf V}}(G)=H\setminus G$, and so no distinct $G$’s share the value of ${{\sf V}}$. Roughly speaking, the equality $w(A)=w(B)$ may hold just “by accident”.  This is one way in which we can see that $w$ by itself does not reflect the combinatorial structure of the problem in a natural way. 

[PROOF of Lemma \[lem:separbasis\].]{}  Let $w(A)\neq w(B)$. Without loss of generality we assume $w(A)>w(B)$ (note that here we use the linearity of the ordering $\leq$).  If $A\cap {{\sf V}}(B)=\emptyset$, from Lemma \[lem:conseqloc\] we would get $w(A\cup B)=w(B)$, which contradicts $w(A\cup B)\geq w(A)>w(B)$. So there necessarily exists $h\in A\cap {{\sf V}}(B)$, but since $h\in A$, we have $h\not\in {{\sf V}}(A)$. So ${{\sf V}}(A)\neq {{\sf V}}(B)$.

Conversely, suppose $w(A)=w(B)=w(A\cup B)$. We want to show ${{\sf V}}(A)={{\sf V}}(B)$, i.e., that $w(A)<w(A\cup\{h\})$ holds iff $w(B)<w(B\cup\{h\})$ holds.  By symmetry, it suffices to show only one of the implications.  We assume $w(A)<w(A\cup\{h\})$. Then $w(A\cup B)=w(A)<w(A\cup\{h\}) \leq
w(A\cup B\cup\{h\})$. Since $B\subseteq A\cup B$ and $w(B)=w(A\cup B)$, we may use locality, which gives $w(B)<w(B\cup\{h\})$. So the desired equivalence holds. 

\[prop:abstract-&gt;acyclicVS\] Consider an abstract LP-type problem $(H,w,W,\leq)$, and let ${{\sf V}}$ be its violator mapping.  Then $(H,{{\sf V}})$ is an acyclic violator space.  Moreover, $(H,{{\sf V}})$ is basis-equivalent to $(H,w,W,\leq)$.

Clearly $G\cap{{\sf V}}(G)=\emptyset$, since $w(G\cup\{g\})=w(G)$ for any $g\in G$, so consistency holds.  If $G\cap {{\sf V}}(F)=\emptyset$ for $F \subseteq G$, then by Lemma \[lem:conseqloc\] we get $w(F\cup G)=w(F)$. Since $F\subseteq G$, we have $F \cup G=G$ and so $w(G)=w(F)$. Lemma \[lem:separbasis\] then yields ${{\sf V}}(G)={{\sf V}}(F)$, so locality holds. 

We proceed to prove acyclicity of $(H,{{\sf V}})$. Fix $[B]$ and $[C]$, $[B]\neq [C]$, with $[B]\leq_0[C]$, that is $B'\cap {{\sf V}}(C')=\emptyset$ for some $B'\in [B]$ and $C'\in [C]$. Lemma \[lem:conseqloc\] implies $w(C')=w(B'\cup C')$. For contradiction, assume $w(B')\geq w(C')$; then $w(B')\geq w(B'\cup C')$ which with monotonicity yields $w(B')=w(B'\cup C')=w(C')$. Lemma \[lem:separbasis\] gives ${{\sf V}}(B')={{\sf V}}(C')$, a contradiction to $[B]\neq [C]$. Thus $[B]\leq_0[C]$ for $[B]\neq [C]$ implies $w(B')<w(C')$ for some bases $B'$ and $C'$ out of the respective equivalence classes.  By Lemma \[lem:separbasis\], $w(B')$ is the same for all $B'\in [B]$ (because all bases in $[B]$ have the same violators).  Therefore, by chaining several $\leq_0$’s we also get $w(B')<w(C')$ for $[B]\leq_1[C]$. This proves that $\leq_1$ is necessarily antisymmetric (since $\leq$ is an ordering of $W$). 

Finally, observe that by Lemma \[lem:separbasis\], $B\subseteq G$ is an inclusion-minimal subset of $G$ with $w(B)=w(G)$ if and only if $B$ is an inclusion-minimal subset of $G$ with ${{\sf V}}(B)={{\sf V}}(G)$. So, $B\subseteq G$ is a basis of $G$ in $(H,w,W,\leq)$ if and only if $B$ is a basis of $G$ in $(H,{{\sf V}})$. Thus $(H,{{\sf V}})$ is basis-equivalent to $(H,w,W,\leq)$.

At first glance, one might think that for $F\subseteq G$ we should have ${{\sf V}}(F)\supseteq {{\sf V}}(G)$. Unfortunately, this is not the case, as the linear programming example in Figure \[fig:counterexample\] shows (the $y$-coordinate is to be minimized). 

We put $F=\{h_1,h_2\}$ and $G=\{h_1,h_2,h_3\}\supseteq F$. The point $1$ is minimum in the intersection of $F$, and $2$ is minimum in the intersection of $G$. We have $1\in h^*$, $2\not\in h^*$, and so $h^*\not\in{{\sf V}}(F)$ and $h^*\in{{\sf V}}(G)$.

Acyclic Violator Spaces yield Concrete LP-type Problems {#sec:acyclicVS->concrete}
-------------------------------------------------------

The following proposition is the last ingredient for Theorem \[thm:main\]. 

\[prop:acyclicVS-&gt;concrete\] Every acyclic violator space $(H,{{\sf V}})$ can be represented as a concrete LP-type problem that is basis-equivalent to $(H,{{\sf V}})$.

We are given an acyclic violator space $(H, {{\sf V}})$ and we define the mapping $S\colon H\to 2^{{{\mathcal B}/\!\sim}}$ that will act as a “concretization” of the constraints in $H$: $$S(h)=\{[B]\colon B\in{\mathcal B},\, h\not\in {{\sf V}}(B)\}.$$ Further, let ${\mathcal H}$ be the image of the mapping $S$ taken as a multiset, i.e., $${\mathcal H}=\{S(h)\colon h\in H\}.$$ Thus, $S$ is a bijection between $H$ and $\mathcal H$. By saying that a mapping $S$ is a bijection between a set and a multiset we mean that for any $\bar h\in{\mathcal H}$, the number of $h\in H$ that map to $\bar h$ is equal to the multiplicity of $\bar h$. Note that we cannot use some common properties of set bijections; for instance we have to avoid using the inverse mapping $S^{-1}$.

Additionally, let $\sigma$ be the induced bijection of $2^H$ and $2^{\mathcal H}$ defined by $\sigma(G)=\{S(h)\colon h\in G\}$, for $G\subseteq H$.

Now, consider the triple $({{{\mathcal B}/\!\sim}},\leq,{\mathcal H})$, where $\leq$ is an arbitrary linear extension of $\leq_1$ (such an extension exists since $(H,{{\sf V}})$ is acyclic and $\leq_1$ therefore antisymmetric).  This is a concrete LP-type problem: The only thing to check is the existence of a minimal element of every nonempty intersection $\bigcap{\mathcal G}$ ($\mathcal G \subseteq \mathcal H$), which is guaranteed by the linearity of $\leq$ (remember from Definition \[def:concrete\_LPtype\] that $\bigcap{\mathcal G}:=\bigcap_{G\in\mathcal{G}}G$). 

It remains to prove basis-equivalence, which we do with the following two lemmas. 

\[lem:equ1\] If $B$ is an inclusion-minimal subset of $G$ with ${{\sf V}}(B)={{\sf V}}(G)$ in $(H,{{\sf V}})$ (that is, $B$ is a basis of $G$), then $\min(\bigcap\sigma(B))=
\min(\bigcap\sigma(G))$ in $({{{\mathcal B}/\!\sim}},\leq,{\mathcal H})$.

It is clear that $[B]\in \bigcap\sigma(G)$. Therefore, showing that there is no other basis in $\bigcap\sigma(G)$ that is locally smaller than $[B]$ proves the lemma, because then $\min(\bigcap\sigma(G))=[B]=\min(\bigcap\sigma(B))$ (the second equality holds since $B$ is a basis of $B$; just replace $G$ by $B$ in the following proof).  Assume for contradiction that a $C$ with $[C]\neq [B]$, $[C]\in\bigcap\sigma(G)$ and $C\leq_0[B]$ exists.  By $[C]\in\bigcap\sigma(G)$ we have $G\cap{{\sf V}}(C)=\emptyset$, which is equivalent to $$(G\cup C)\cap{{\sf V}}(C)=\emptyset,$$ and by $C\leq_0[B]$ we have $C\cap{{\sf V}}(B)=\emptyset$ which is equivalent to (because $B$ is a basis of $G$) $$(G\cup C)\cap{{\sf V}}(B)=\emptyset.$$ Applying locality in $(H,{{\sf V}})$ to these two equations tells us that ${{\sf V}}(C)={{\sf V}}(B)$, a contradiction to $[C]\neq [B]$.

\[lem:equ2\] If $\sigma(B)$ is an inclusion-minimal submultiset of $\sigma(G)$ with $\min(\bigcap\sigma(B))=\min(\bigcap\sigma(G))$ in $({{{\mathcal B}/\!\sim}},\leq,{\mathcal H})$ (that is, $\sigma(B)$ is a basis of $\sigma(G)$), then ${{\sf V}}(B)={{\sf V}}(G)$ in $(H,{{\sf V}})$.

Let $A$ be a basis of $B$, so ${{\sf V}}(A)={{\sf V}}(B)$. Note that $[A]\in\bigcap\sigma(B)$. Let $[C]=\min(\bigcap\sigma(B))$, thus $B\cap{{\sf V}}(C)=\emptyset$ and therefore also $A\cap{{\sf V}}(C)=\emptyset$. This means that $[A]\leq_0 [C]$ from which we conclude that $[A]=[C]$. From $\min(\bigcap\sigma(G))=[C]$ we get $G\cap{{\sf V}}(C)=\emptyset$ which is equivalent to $$G\cap{{\sf V}}(B)=\emptyset.$$ As $\sigma(B)\subseteq\sigma(G)$ if and only if $B\subseteq G$, we can apply locality and derive ${{\sf V}}(B)={{\sf V}}(G)$ as needed. 

Lemmas \[lem:equ1\] and \[lem:equ2\] prove that $(H,{{\sf V}})$ and $({{{\mathcal B}/\!\sim}},\leq,{\mathcal H})$ are basis-equivalent, in the sense that $B$ is a basis of $G$ in $(H,{{\sf V}})$ if and only if $\sigma(B)$ is a basis of $\sigma(G)$ in $({{{\mathcal B}/\!\sim}},\leq,{\mathcal H})$: Starting with a basis $B$ of $G$ in $(H,{{\sf V}})$, Lemma \[lem:equ1\] yields $\min(\bigcap\sigma(B))=\min(\bigcap\sigma(G))$. This $\sigma(B)$ is inclusion-minimal w.r.t.  $\sigma(G)$, since otherwise Lemma \[lem:equ2\] would yield a contradiction to the inclusion-minimality of $B$ w.r.t.  $G$ (where we again use that $\sigma(B)\subseteq\sigma(G)$ if and only if $B\subseteq G$).  The reasoning for inclusion-minimality in the other direction is analogous.  This concludes the proof of Proposition \[prop:acyclicVS-&gt;concrete\]. 

Propositions \[prop:abstract-&gt;acyclicVS\] and \[prop:acyclicVS-&gt;concrete\], together with the fact that every concrete LP-type problem can be transformed into an abstract one (as described below Definition \[def:concrete\_basis\]), yield Theorem \[thm:main\]. 

Examples {#sec:examples}
--------

Here we present some particular abstract LP-type problems and we demonstrate the construction (via acyclic violator spaces) of their concrete representations. 

Let $a$, $b$, $c$ and $d$ be the vertices of a unit square (in the counterclockwise order); let $H=\{a,b,c,d\}$. For $G\subseteq H$ let $w(G)$ be the radius of the smallest circle enclosing all the points of $G$ (for $G=\emptyset$ put $w(G)=-\infty$).  The corresponding acyclic violator space is described by the following table:

0.4cm

        $G$         $\emptyset$       $a$        $b$        $c$           $d$          $ab$          $ac$          $ad$
  ---------------- ------------- ------------- ------- ------------- ------------- ------------- ------------- -------------
   ${{\sf V}}(G)$     $abcd$         $bcd$      $acd$      $abd$         $abc$         $cd$       $\emptyset$      $bc$
        $G$            $bc$          $bd$       $cd$       $abc$         $abd$         $acd$         $bcd$        $abcd$
   ${{\sf V}}(G)$      $ad$       $\emptyset$   $ab$    $\emptyset$   $\emptyset$   $\emptyset$   $\emptyset$   $\emptyset$

The bases are $\emptyset$, $a$, $b$, $c$, $d$, $ab$, $ac$, $ad$, $bc$, $bd$, $cd$; the only equivalent pair is $ac\sim bd$. There is no inconvenience concerning differences between $\leq_0$ on sets and equivalence classes and $\leq_1$; the ordering $\leq_1$ is given by the Hasse diagram in Figure \[fig:hasse\]. 

As the linear extension $\leq$ of $\leq_1$ we may choose $\emptyset<a<b<c<d<ab<bc<cd<ad<[ac]$. Finally, the concrete representation $S$ is as follows:

0.4cm

    $h$          $a$              $b$              $c$              $d$
  -------- ---------------- ---------------- ---------------- ----------------
   $S(h)$   $a,ab,ad,[ac]$   $b,ab,bc,[ac]$   $c,bc,cd,[ac]$   $d,cd,ad,[ac]$

In the geometric view that we have mentioned earlier, $S(a)$ corresponds to the set of all “canonical” (i.e., basic) balls that contain the point $a$ (inside or on the boundary).  The same holds for the other points. 

As the other example, consider the following LP problem in the positive orthant (rotated by 45 degrees for convenience).  Beside the restriction to the positive orthant, the constraints are the four halfplanes depicted in Figure \[fig:lp\_example\].  The optimization direction is given by the arrow. 

Here the violator space bases are $\emptyset$, $a$, $b$, $c$, $d$, $ac$, $ad$, $bc$, $bd$; the equivalence classes are $O=\emptyset$, $A=\{a\}$, $B=\{b\}$, $C=\{c\}$, $D=\{d\}$ and $Q=\{ac\}\sim\{ad\}\sim\{bc\}\sim\{bd\}$. Note that the equivalence classes correspond to the points in the plane.  We have $O\leq_1 B\leq_1 A\leq_1 Q$ and $O\leq_1 C\leq_1 D\leq_1 Q$; we choose $\leq$ to be $O<B<A<C<D<Q$. The concrete representation is

0.4cm

    $h$      $a$      $b$       $c$      $d$
  -------- ------- --------- --------- -------
   $S(h)$   $A,Q$   $A,B,Q$   $C,D,Q$   $D,Q$

. 

Here we may interpret $S(a)$ as the set of all “canonical” points lying in the halfplane $a$.

To see why we allow $\mathcal H$ in the definition of a concrete LP-type problem to be a multiset, consider the abstract LP-type problem with $H=\{a,b\}$ and $w(G)=0$ for every $G\subseteq H$. The only basis is $\emptyset$ and it is not violated by any $h\in H$. Thus we have $S(a)=S(b)=\{[\emptyset]\}$. If we do not allow $\mathcal H$ to be a multiset, we have ${\mathcal H}=\{S(a),S(b)\} =
\bigl\{ \{[\emptyset]\} \bigr\}$ with only one constraint; it seems improper to define this to be basis-equivalent to $H$. We could alter the construction of $\mathcal H$ and get $S(a)=\{0\}$, $S(b)=\{0,1\}$, which does represent the original abstract LP-type problem with $\mathcal H$ being a set; however, we believe that our definition catches the structure in a more straightforward way, although it may seem unusual at first glance. 

Clarkson’s Algorithms {#sec:clarkson}
=====================

We show that Clarkson’s randomized reduction scheme, originally developed for linear programs with many constraints and few variables, actually works for general (possibly cyclic) violator spaces.  The two algorithms of Clarkson involved in the reduction have been analyzed for LP and LP-type problems before [@c-lvali-95; @gw-lpraf-96; @cm-ltdao-96]; the analysis we give below is almost identical on the abstract level.  Our new contribution is that the combinatorial properties underlying Clarkson’s algorithms also hold for violator spaces. 

We start off by deriving these combinatorial properties; the analysis of Clarkson’s reduction scheme is included for completeness. 

Violator spaces revisited
-------------------------

We recall that an abstract LP-type problem is of the form $(H,w,W,\leq)$. In this subsection we will view a violator space as an “LP-type problem without the order $\leq$”, i.e., we will only care whether two subsets $F$ and $G$, $F\subseteq G\subseteq H$, have the same value (and therefore the same violators, see Lemma \[lem:separbasis\]), but not how they compare under the order $\leq$. It turns out that the order is irrelevant for Clarkson’s algorithms. 

Even without an order, we can talk about monotonicity in violator spaces:

Any violator space $(H,{{\sf V}})$ satisfies

  --------------- -------------------------------------------------------------------------------
  Monotonicity:   ${{\sf V}}(F)={{\sf V}}(G)$ implies ${{\sf V}}(E)={{\sf V}}(F)={{\sf V}}(G)$,
                  for all sets $F\subseteq E\subseteq G\subseteq H$.
  --------------- -------------------------------------------------------------------------------

\[lem:monotonicity\]

Assume ${{\sf V}}(E)\neq {{\sf V}}(F),{{\sf V}}(G)$. Then locality yields $\emptyset \neq E\cap {{\sf V}}(F) = E\cap {{\sf V}}(G)$ which contradicts consistency. 

Recall Definition \[def:vbasis\]: A basis is a set $B$ satisfying $B\cap {{\sf V}}(F)\neq\emptyset$ for all proper subsets $F$ of $B$. A basis of $G$ is an inclusion-minimal subset of $G$ with the same violators.  This can be used to prove the following observation, well-known to hold for LP-type problems [@gw-lpraf-96]. 

\[obs:extreme\] Let $(H,{{\sf V}})$ be a violator space.  For $R\subseteq H$ and all $h\in H$, we have

1.   ${{\sf V}}(R)\neq {{\sf V}}(R\cup\{h\})$ if and only if $h\in {{\sf V}}(R)$, and

2.   ${{\sf V}}(R)\neq {{\sf V}}(R\setminus\{h\})$ if and only if $h$ is contained in every basis of $R$.

An element $h$ such that (ii) holds is called *extreme* in $R$.

\(i) If $h\notin{{\sf V}}(R)$, we get ${{\sf V}}(R)={{\sf V}}(R\cup\{h\})$ by Lemma \[lem:conseqloc\].  If $h\in{{\sf V}}(R)$, then ${{\sf V}}(R)\neq {{\sf V}}(R\cup\{h\})$ is a consequence of consistency applied to $G=R\cup\{h\}$. (ii) if ${{\sf V}}(R)={{\sf V}}(R\setminus\{h\})$, there is a basis $B$ of $R\setminus\{h\}$, and this basis is also a basis of $R$ not containing $h$. Conversely, if there is some basis $B$ of $R$ not containing $h$, then ${{\sf V}}(R)={{\sf V}}(R\setminus\{h\})$ follows from monotonicity. 

We are particularly interested in violator spaces with small bases. 

Let $(H,{{\sf V}})$ be a violator space.  The size of a largest basis is called the *combinatorial dimension* $\delta=\delta(H,{{\sf V}})$ of $(H,{{\sf V}})$.

Observation \[obs:extreme\] implies that in a violator space of combinatorial dimension $\delta$, every set has at most $\delta$ extreme elements.  This in turn yields a bound for the *expected* number of violators of a random subset of constraints, using the *sampling lemma* [@GWSampl01]. 

[[@GWSampl01]]{} Consider a triple $(H,w,W)$, where $w$ is a function mapping subsets of the set $H$ to the set $W$ (not necessarily ordered).  For $R\subseteq H$, we define $$\begin{aligned}
V(R) &:=& \{h\in H\setminus R: w(R)\neq w(R\cup\{h\}), \\
X(R) &:=& \{h\in R: w(R)\neq w(R\setminus\{h\}).\end{aligned}$$ For $0\leq r\leq |H|$, let $v_r$ be the expected value of $|V(R)|$, for $R$ chosen uniformly at random among all subsets of $H$ with $r$ elements.  $x_r$ is defined similarly as the expected value of $|X(R)|$. Then for $0\leq r<n$, the following equality holds.  $$\frac{v_r}{n-r}=\frac{x_{r+1}}{r+1}.$$

To apply this in our situation, we fix a set $W\subseteq H$, and we define $w(R)={{\sf V}}(W\cup R)$. Since then $|X(R)|\leq\delta$ for all $R$, the following Corollary is obtained. 

\[cor:sampling\] Let $(H,{{\sf V}})$ be a violator space of combinatorial dimension $\delta$ and $W\subseteq H$ some fixed set.  Let $v_r$ be the expected number of violators of the set $W\cup R$, where $R\subseteq H$ is a random subset of size $r< n=|H|$. Then $$v_r \leq \delta \frac{n-r}{r+1}.$$

The Trivial Algorithm
---------------------

Given a violator space $(H,{{\sf V}})$ of combinatorial dimension $\delta$, the goal is to find a basis of $H$. For this, we assume availability of the following primitive. 

\[prim:viol\] Given $G\subseteq H$ and $h\in H\setminus G$, decide whether $h\in {{\sf V}}(G)$.

Given this primitive, the problem can be solved in a brute-force manner by going through all sets of size $\leq \delta$, testing each of them for being a basis of $H$. More generally, $B\subseteq G$ is a basis of $G$ if and only if $$\begin{array}{rcll}
h&\in& {{\sf V}}(B\setminus\{h\}), \quad & \forall h\in B, \\
h&\notin& {{\sf V}}(B), & \forall h\in G\setminus B. 
\end{array}$$ Consequently, the number of times the primitive needs to be invoked in order to find a basis of $H$ is at most $$n \sum_{i=0}^{\delta}{n\choose i} = O(n^{\delta+1}).$$ The next two subsections show that this can be substantially improved. 

Clarkson’s First Algorithm
--------------------------

Fix a violator space $(H,{{\sf V}})$ of combinatorial dimension $\delta$, implicitly specified through Primitive \[prim:viol\].  Clarkson’s first algorithm calls Clarkson’s second algorithm ([[]{.nodecor}]{}) as a subroutine.  Given $G\subseteq H$, both algorithms compute a basis $B$ of $G$.

====[[]{.nodecor}]{}$(G)$:\
(\* computes a basis $B$ of $G$ \*)\
[[]{.nodecor}]{} $|G|\leq 9\delta^2$ [[]{.nodecor}]{}\
[[]{.nodecor}]{} [[]{.nodecor}]{}$(G)$\
[[]{.nodecor}]{}\
$r:=\lfloor\delta\sqrt{|G|}\rfloor$\
$W:=\emptyset$\
[[]{.nodecor}]{}\
choose $R$ to be a random $r$-element subset of $G$, $R\in{G\choose r}$\
$C:={\textnormal{\textrm{\texttt{Basis2}}}}(W\cup R)$\
${{\sf V}}:=\{h\in G\setminus C\colon h\in {{\sf V}}(C)\}$\
[[]{.nodecor}]{} $|{{\sf V}}|\leq 2\sqrt{|G|}$ [[]{.nodecor}]{}\
$W:=W\cup {{\sf V}}$\
[[]{.nodecor}]{}\
[[]{.nodecor}]{} ${{\sf V}}=\emptyset$\
[[]{.nodecor}]{} $C$\
[[]{.nodecor}]{}\

Assuming [[]{.nodecor}]{} is correct, this algorithm is correct as well: if $B$ is a basis of $W\cup R\subseteq G$ that in addition has no violators in $G$, $B$ is a basis of $G$. Moreover, the algorithm augments the working set $W$ at most $\delta$ times, which is guaranteed by the following observation. 

\[obs:basis\] If $C\subseteq G$ and $G\cap {{\sf V}}(C)\neq \emptyset$, then $G\cap {{\sf V}}(C)$ contains at least one element from every basis of $G$.

Let $B$ be a basis of $G$. Assuming $$\emptyset = B\cap G\cap {{\sf V}}(C) = B \cap {{\sf V}}(C),$$ consistency yields $C\cap {{\sf V}}(C)=\emptyset$, implying $(B\cup C)\cap {{\sf V}}(C)=\emptyset$. From locality and monotonicity (Lemma \[lem:monotonicity\]), we get $${{\sf V}}(C)={{\sf V}}(B\cup C)={{\sf V}}(G),$$ meaning that $G\cap {{\sf V}}(G)= G\cap {{\sf V}}(C)=\emptyset$, a contradiction. 

It is also clear that [[]{.nodecor}]{} is called only with sets of size at most $3\delta\sqrt{|G|}$. Finally, the expected number of iterations through the [[]{.nodecor}]{} loop is bounded by $2\delta$: by Corollary \[cor:sampling\] (applied to $(G,{{\sf V}}|_G)$) and the Markov inequality, the expected number of calls to [[]{.nodecor}]{} before we next augment $W$ is bounded by $2$.

Algorithm [[]{.nodecor}]{} computes a basis of $G$ with an expected number of at most $2\delta|G|$ calls to Primitive \[prim:viol\], and an expected number of at most $2\delta$ calls to [[]{.nodecor}]{}, with sets of size at most $3\delta\sqrt{|G|}$.

Clarkson’s Second Algorithm
---------------------------

This algorithm calls the trivial algorithm as a subroutine.  Instead of adding violated constraints to a working set, it gives them larger probability of being selected in further iterations.  Technically, this is done by maintaining $G$ as a multiset, where $\mu(h)$ denotes the multiplicity of $h$ (we set $\mu(F):=\sum_{h\in F}\mu(h)$).  Sampling from $G$ is done as before, imagining that $G$ contains $\mu(h)$ copies of the element $h$.

====[[]{.nodecor}]{}$(G)$:\
(\* computes a basis $B$ of $G$ \*)\
[[]{.nodecor}]{} $|G|\leq 6\delta^2$ [[]{.nodecor}]{}\
[[]{.nodecor}]{} [[]{.nodecor}]{}$(G)$\
[[]{.nodecor}]{}\
$r:=6\delta^2$\
[[]{.nodecor}]{}\
choose random $R\in{G\choose r}$\
$C:={\textnormal{\textrm{\texttt{Trivial}}}}(R)$\
${{\sf V}}:=\{h\in G\setminus C\colon h\in {{\sf V}}(C)\}$\
[[]{.nodecor}]{} $\mu({{\sf V}})\leq \mu(G)/3\delta$ [[]{.nodecor}]{}\
$\mu(h) := 2\mu(h), \quad h\in {{\sf V}}$\
[[]{.nodecor}]{}\
[[]{.nodecor}]{} ${{\sf V}}=\emptyset$\
[[]{.nodecor}]{} $C$\
[[]{.nodecor}]{}\

Invoking Corollary \[cor:sampling\] again (which also applies to multisets as we use them), we see that the expected number of calls to [[]{.nodecor}]{} before we next reweight elements (a *successful* iteration), is bounded by $2$. It remains to bound the number of successful iterations. 

Let $k$ be a positive integer.  After $k\delta$ successful iterations, we have $$2^k \leq \mu(B)\leq |G|e^{k/3},$$ for every basis $B$ of $G$. In particular, $k< 3\ln |G|$.

Every successful iteration multiplies the total weight of elements in $G$ by at most $(1+1/3\delta)$, which gives the upper bound (not only for $\mu(B)$ but actually for $\mu(G)$).  For the lower bound, we use Observation \[obs:basis\] again to argue that each successful iteration doubles the weight of some element in $B$, meaning that after $k\delta$ iterations, one element has been doubled at least $k$ times.  Because the lower bound exceeds the upper bound for $k\geq 3\ln |G|$, the bound on $k$ follows. 

Summarizing, we get the following lemma. 

Algorithm [[]{.nodecor}]{} computes a basis of $G$ with an expected number of at most $6\delta |G|\ln|G|$ calls to Primitive \[prim:viol\], and expected number of at most $6\delta\ln |G|$ calls to [[]{.nodecor}]{}, with sets of size $6\delta^2$.

Combining the Algorithms
------------------------

\[thm:runtime\] Using a combination of the above two algorithms, a basis of $H$ in a violator space $(H,{{\sf V}})$ can be found calling Primitive \[prim:viol\] expected $$O\left(\delta n + \delta^{O(\delta)}\right)$$ many times. 

Using the above bound for the trivial algorithm, [[]{.nodecor}]{} can be implemented to require an expected number of at most $$O\left(\delta\log |G|(|G| + \delta^{O(\delta)})\right)$$ calls to the primitive.  Applying this as a subroutine in [[]{.nodecor}]{}$(H)$ with $|H|=n$, $|G|$ is bounded by $3\delta\sqrt{n}$, and we get an overall expected complexity of $$O\left(\delta n + \delta^2 (\log n(\delta \sqrt{n} + 
\delta^{O(\delta)}))\right)$$ in terms of the number of calls to Primitive \[prim:viol\].  The terms $\delta^2\log n~ \delta\sqrt{n}$ and $\delta^2\log n~ \delta^{O(\delta)}$ are asymptotically dominated by either $\delta n$ or $\delta^{O(\delta)}$, and we get the simplified bound of $O\left(\delta n + \delta^{O(\delta)}\right)$.

Grid USO as Models for Violator Spaces {#grid_uso}
======================================

We show in this section that the problem of finding the sink in a $\delta$-dimensional *grid unique sink orientation* [@grid_uso] can be reduced to the problem of finding the (unique) basis of a violator space of combinatorial dimension $\delta$.

Unique sink orientations of grids arise from various problems, including linear programming over products of simplices and generalized linear complementarity problems (GLCP) over ${\mathrm{P}}$-matrices [@grid_uso].  The GLCP has been introduced by Cottle and Dantzig [@cd-glcp-70] as a generalization of the well known LCP [@lcp].  There are also applications in game theory; for instance [@sweden1; @sweden2; @ssg_pglcp] show how parity, mean-payoff, and simple stochastic games are related to grid USO. 

Grid USO
--------

Fix a partition $$\Pi=(\Pi_1,\ldots,\Pi_{\delta})$$ of the set $H:=\{1,\ldots,n\}$ into $\delta$ nonempty subsets, where we refer to $\Pi_i$ as the *block $i$*.  A subset $J\subseteq H$ is called a *vertex* if $|J\cap \Pi_i|=1$ for all $i$. The vertices naturally correspond to the Cartesian product of the $\Pi_i$. Let ${{\mathcal V}}$ be the set of all vertices. 

In the following definition, we introduce the *grid spanned* by subsets $\Pi'_i$ whose union is $G\subseteq H$. The vertex set of this grid contains all vertices $J\subseteq G$ ($J\in {{\mathcal V}}$), with two vertices being adjacent whenever they differ in exactly two elements. 

The $\delta$-dimensional *grid* spanned by $G \subseteq H$ is the undirected graph ${{\mathcal G}}(G)=({{\mathcal V}}(G),{{\mathcal E}}(G))$, with $${{\mathcal V}}(G):=\{J\in {{\mathcal V}}\colon J\subseteq G\},\quad
{{\mathcal E}}(G):=\{\{J,J'\}\subseteq{{\mathcal V}}(G)\colon |J\oplus J'|=2\}.$$ Here, $\oplus$ is the symmetric difference of sets. 

${{\mathcal V}}(G)$ is in one-to-one correspondence with the Cartesian product $$\prod_{i=1}^{\delta}G_i, \quad G_i:=G\cap \Pi_i,$$ and the edges in ${{\mathcal E}}(G)$ connect vertices in ${{\mathcal V}}(G)$ whose corresponding tuples differ in exactly one coordinate.  See Figure \[fig:grid\] left for an example of a grid. 

Note that ${{\mathcal G}}(G)$ is the empty graph whenever $G_i=G\cap \Pi_i=\emptyset$ for some $i$. We say that such a $G$ is *not $\Pi$-valid*, and it is *$\Pi$-valid* otherwise. 

A *subgrid* of ${{\mathcal G}}(G)$ is any graph of the form ${{\mathcal G}}(G')$, for $G'\subseteq G$.

An orientation $\psi$ of the graph ${{\mathcal G}}:={{\mathcal G}}(H)$ is called a *unique sink orientation* (USO) if all nonempty subgrids of ${{\mathcal G}}$ have unique sinks w.r.t.  $\psi$.

We are interested in finding the sink in a USO of ${{\mathcal G}}$ as fast as possible, since the sink corresponds to the solution of the underlying problem (the ${\mathrm{P}}$-matrix GLCP, for example).  Our measure of complexity will be the expected number of *edge evaluations*, see [@grid_uso].  An edge evaluation returns the orientation of the considered edge and can typically be implemented to run in polynomial time (depending on the underlying problem).  In the remainder of this paper, we derive the following theorem. 

\[thm:uso\_algo\] The sink of a unique sink grid orientation can be found by evaluating expected $O\left(\delta n + \delta^{O(\delta)}\right)$ edges. 

Note that a USO $\psi$ can be cyclic (see the thick edges in Figure \[fig:grid\] right).  If $\psi$ induces the directed edge $(J,J')$, we also write $J\stackrel{\psi}{\rightarrow}J'$. Any USO can be specified by associating each vertex $J$ with its outgoing edges.  Given $J$ and $j\in H\setminus J$, we define $J\rhd j$ to be the unique vertex $J'\subseteq J\cup\{j\}$ that is different from $J$, and we call $J'$ the *neighbor* of $J$ *in direction* $j$. Note that $J$ is a neighbor of $J'$ in some direction different from $j$.

Given an orientation $\psi$ of ${{\mathcal G}}$, the function $s_{\psi}:{{\mathcal V}}\rightarrow 2^{H}$, defined by $$s_{\psi}(J) := \{j\in H\setminus J\colon J\stackrel{\psi}{\rightarrow} J\rhd j\},$$ is called the *outmap* of $\psi$.

By this definition, any sink w.r.t.  $\psi$ has empty outmap value. 

Reduction to Violator Spaces
----------------------------

Let us fix a unique sink orientation $\psi$ of ${{\mathcal G}}$. Given a $\Pi$-valid subset $G\subseteq H$, we define ${\mathop{\rm sink}}(G)\in
{{\mathcal V}}(G)$ to be the unique sink vertex in ${{\mathcal G}}(G)$. For a subset $G$ that is not $\Pi$-valid, let $$\bar{G}:=\bigcup_{i\colon\, G_i=\emptyset}\Pi_i.$$ Thus $\bar{G}$ is the set of elements occurring in blocks of $\Pi$ disjoint from $G$.

\[def:gridtoviol\] For $G\subseteq H$, define $${{\sf V}}(G)=
\left\{
\begin{array}{ll}
s_{\psi}({\mathop{\rm sink}}(G)), &\quad\textit{if $G$ is $\Pi$-valid}\\
\bar{G}, &\quad\textit{if $G$ is not $\Pi$-valid.} 
\end{array}
\right.$$

The pair $(H,{{\sf V}})$ from Definition \[def:gridtoviol\] is a violator space of combinatorial dimension $\delta$. Moreover, for all $\Pi$-valid $G\subseteq H$, the unique sink of the subgrid $\mathcal{G}(G)$ corresponds to the unique basis of $G$ in $(H,{{\sf V}})$.

For every $G \subseteq H$, consistency holds by definition of ${\mathop{\rm sink}}(G), s_{\psi}(J)$ and $\bar{G}$. In order to prove locality for $F\subseteq G\subseteq H$, we look at three different cases. 

#### $\mathbf{G}$ is not $\mathbf{\Pi}$-valid. {# mathbfg-is-not-mathbfpi-valid.  .unnumbered}

Then, $F\subseteq G$ is not $\Pi$-valid either.  The condition $\emptyset=G\cap {{\sf V}}(F)=G\cap\bar{F}$ means that $F$ is disjoint from the same blocks as $G$. This implies $\bar{G}=\bar{F}$, hence ${{\sf V}}(G)={{\sf V}}(F)$.

#### $\mathbf{G}$ and $\mathbf{F}$ are both $\mathbf{\Pi}$-valid. {# mathbfg-and-mathbff-are-both-mathbfpi-valid.  .unnumbered}

Then ${{\mathcal G}}(F)$ is a nonempty subgrid of ${{\mathcal G}}(G)$, and $G \cap {{\sf V}}(F)=\emptyset$ means that the sink of ${{\mathcal G}}(F)$ has no outgoing edges into ${{\mathcal G}}(G)$. Thus the unique sink of ${{\mathcal G}}(F)$ is also a sink of ${{\mathcal G}}(G)$ and therefore the unique one.  This means that ${\mathop{\rm sink}}(G)={\mathop{\rm sink}}(F)$, from which ${{\sf V}}(G)={{\sf V}}(F)$ follows. 

#### $\mathbf{G}$ is $\mathbf{\Pi}$-valid, $\mathbf{F}$ is not $\mathbf{\Pi}$-valid. {# mathbfg-is-mathbfpi-valid-mathbff-is-not-mathbfpi-valid.  .unnumbered}

Then the condition $G \cap {{\sf V}}(F)=\emptyset$ can never be satisfied since ${{\sf V}}(F)=\bar{F}$ contains at least one full block $\Pi_i$, and $G_i=G\cap\Pi_i\neq \emptyset$.

Next we prove that a largest basis in $(H,{{\sf V}})$ has at most $\delta$ elements.  For this, let $G\subseteq H$ be a set of size larger than $\delta$. If $G$ is $\Pi$-valid, we have $${{\sf V}}(G):=s_{\psi}({\mathop{\rm sink}}(G))=s_{\psi}({\mathop{\rm sink}}({\mathop{\rm sink}}(G)))=:{{\sf V}}({\mathop{\rm sink}}(G)),$$ since $J={\mathop{\rm sink}}(J)$ for any vertex $J$. This means that $G$ has a subset of size $\delta$ with the same violators, so $G$ is not a basis. 

If $G$ is not $\Pi$-valid, we consider some subset $B$ that contains exactly one element from every block intersected by $G$. By definition, we have $\bar{G}=\bar{B}$ and ${{\sf V}}(G)={{\sf V}}(B)$. Since $B$ has less than $\delta$ elements, $G$ cannot be a basis in this case, either. 

It remains to prove that for $G$ being $\Pi$-valid, the vertex ${\mathop{\rm sink}}(G)$ is the unique basis of $G$ in $(H,{{\sf V}})$. We have already shown that ${{\sf V}}(G)={{\sf V}}({\mathop{\rm sink}}(G))$ must hold in this case.  Moreover, ${{\sf V}}({\mathop{\rm sink}}(G))$ contains no full block $\Pi_i$. On the other hand, any proper subset $F$ of ${\mathop{\rm sink}}(G)$ is not $\Pi$-valid, so its violator set *does* contain at least one full block.  It follows that $V(F)\neq V({\mathop{\rm sink}}(G))$, so ${\mathop{\rm sink}}(G)$ is a basis of $G$. The argument is complete when we can prove that no other vertex $J\subseteq G$ is a basis of $G$. Indeed, such a vertex $J$ is not a sink in ${{\mathcal G}}(G)$, meaning that $G\cap {{\sf V}}(J)\neq \emptyset$. This implies ${{\sf V}}(J)\neq {{\sf V}}(G)$.

Note that the global sink of the grid USO corresponds to the unique $\delta$-element (and $\Pi$-valid) set $B$ with ${{\sf V}}(B)=\emptyset$. This is exactly the set output by the call `Basis1`$(H)$ of Clarkson’s algorithms, when we apply it to the violator space constructed in Definition \[def:gridtoviol\]. 

Primitive \[prim:viol\] corresponds to one edge evaluation in the USO setting.  With Theorem \[thm:runtime\], we therefore have proved Theorem \[thm:uso\_algo\].  For small $\delta$, the running time given in the theorem is faster than the one from the *Product Algorithm* [@grid_uso] which needs expected $O(\delta!n+H_n^{\delta})$ edge evaluations, where $H_n$ is the $n$-th harmonic number. 

Conclusions
===========

We introduced violator spaces as a new framework for optimization problems and showed that acyclic violator spaces are equivalent to abstract and concrete LP-type problems.  It turned out that the explicit ordering inherent to LP-type problems is not necessary in order to capture the structure of the underlying optimization problem.  Violator spaces are more general than LP-type problems, yet Clarkson’s algorithms still work on them. 

The Sharir-Welzl algorithm is also applicable for violator spaces in a straightforward way.  However, the most obvious translation of this algorithm to the setting of violator spaces is not even guaranteed to finish, since for a general violator space it may run in a cycle and the subexponential analysis thus breaks down. 

We have seen that unique sink orientations are models for possibly cyclic violator spaces, and with Clarkson’s algorithms we therefore have a fast scheme to solve fixed dimensional USO problems like the generalized linear complementarity problem with a ${\mathrm{P}}$-matrix.  The GLCP with a ${\mathrm{P}}$-matrix has in general a cyclic structure and therefore gives rise to a cyclic USO.  A violator space obtained from a cyclic USO is again cyclic.  It is interesting that there are no cycles in a 2-dimensional grid USO [@grid_uso].  Whether the same is true for violator spaces of combinatorial dimension 2 is an open question. 

Acknowledgment {#acknowledgment .unnumbered}
==============

We thank an anonymous referee for useful comments.  The second author would like to thank Nina Amenta for discussions concerning LP-type problems, possibly already forgotten by her as they took place many years ago, but nevertheless helpful for reaching the results in this paper. 

[10]{} url \#1[`#1`]{}urlprefix

M. Sharir, E. Welzl, A combinatorial bound for linear programming and related problems, in: Proc.  9th Symposium on Theoretical Aspects of Computer Science (STACS), Vol.  577 of Lecture Notes in Computer Science, Springer-Verlag, 1992, pp.  569–579. 

J. Matoušek, M. Sharir, E. Welzl, A subexponential bound for linear programming, Algorithmica 16 (1996) 498–516. 

G. Kalai, A subexponential randomized simplex algorithm, in: Proc.  24th Annual ACM Symposium on Theory of Computing (STOC), 1992, pp.  475–482. 

N. Amenta, Bounded boxes, [H]{}ausdorff distance, and a new proof of an interesting [H]{}elly-type theorem, in: Proc.  10th Annual Symposium on Computational Geometry (SCG), ACM Press, 1994, pp.  340–347. 

N. Amenta, [H]{}elly theorems and generalized linear programming, Discrete and Computational Geometry 12 (1994) 241–261. 

H. Bj[ö]{}rklund, S. Sandberg, S. Vorobyov, A discrete subexponential algorithm for parity games, in: Proc.  20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, 2003, pp.  663–674. 

N. Halman, Discrete and lexicographic [H]{}elly theorems and their relations to [LP]{}-type problems, Ph.D. thesis, Tel-Aviv University (2004). 

K. L. Clarkson, [L]{}as [V]{}egas algorithms for linear and integer programming, Journal of the ACM 42 (1995) 488–499. 

B. G[ä]{}rtner, E. Welzl, Linear programming - randomization and abstract frameworks, in: Proc.  13th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, London, UK, 1996, pp.  669–687. 

B. Chazelle, J. Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Journal of Algorithms 21 (1996) 579–597. 

J. Matoušek, On geometric optimization with few violated constraints, Discrete and Computational Geometry 14 (1995) 365–384. 

B. G[ä]{}rtner, E. Welzl, A simple sampling lemma - analysis and applications in geometric optimization, Discrete and Computational Geometry 25 (4) (2001) 569–590. 

T. Chan, An optimal randomized algorithm for maximum [T]{}ukey depth, in: Proc.  15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2004, pp.  423–429. 

N. Amenta, A short proof of an interesting [H]{}elly-type theorem, Discrete and Computational Geometry 15 (1996) 423–427. 

T. Szabó, E. Welzl, Unique sink orientations of cubes, in: Proc.  42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2000, pp.  547–555. 

B. G[ä]{}rtner, W. D. Morris[, Jr.]{}, L. R[ü]{}st, Unique sink orientations of grids, in: Proc.  11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Vol.  3509 of Lecture Notes in Computer Science, Springer-Verlag, 2005, pp.  210–224. 

W. D. Morris[, Jr.]{}, Randomized principal pivot algorithms for [P]{}-matrix linear complementarity problems, Mathematical Programming, Series A 92 (2002) 285–296. 

J. Matoušek, The number of unique sink orientations of the hypercube, Combinatorica, to appear (2006). 

W. D. Morris[, Jr.]{}, Distinguishing cube orientations arising from linear programs, Manuscript (2002). 

M. Develin, [LP]{}-orientations of cubes and crosspolytopes, Advances in Geometry 4 (2004) 459–468. 

J. Matoušek, T. Szabó, [R]{}andom [E]{}dge can be exponential on abstract cubes, in: Proc.  45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004, pp.  92–100. 

I. Schurr, T. Szab[ó]{}, Finding the sink takes some time, Discrete and Computational Geometry 31 (2004) 627–642. 

I. Schurr, T. Szabó, Jumping doesn’t help in abstract cubes, in: Proc.  11th Conference on Integer Programming and Combinatorial Optimization (IPCO), Vol.  3509 of Lecture Notes in Computer Science, Springer-Verlag, 2005, pp.  225–235. 

B. G[ä]{}rtner, I. Schurr, Linear programming and unique sink orientations, in: Proc.  17th Annual Symposium on Discrete Algorithms (SODA), 2006, pp.  749–757. 

H. Bj[ö]{}rklund, S. Vorobyov, Combinatorial structure and randomized subexponential algorithms for infinite games, Theoretical Computer Science (in press). 

H. Bj[ö]{}rklund, S. Sandberg, S. Vorobyov, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, in: Proc.  29th International Symposium on Mathematical Foundations of Computer Science (MFCS), Vol.  3153 of Lecture Notes in Computer Science, Springer-Verlag, 2004, pp.  673–685. 

B. G[ä]{}rtner, L. R[ü]{}st, Simple stochastic games and [P]{}-matrix generalized linear complementarity problems, in: Proc.  15th International Symposium on Fundamentals of Computation Theory (FCT), Vol.  3623 of Lecture Notes in Computer Science, Springer-Verlag, 2005, pp.  209–220. 

N. Megiddo, A note on the complexity of [P]{}-matrix [LCP]{} and computing an equilibrium, Tech.  rep.,  IBM Almaden Research Center, San Jose (1988). 

P. [Š]{}kovro[ň]{}, Generalized linear programming, Master’s thesis, Charles University, Prague, Faculty of Mathematics and Physics (2002). [ http://kam.mff.cuni.cz/\~{}xofon/diplomka/](http://kam.mff.cuni.cz/~{}xofon/diplomka/)

R. W. Cottle, G. B. Dantzig, A generalization of the linear complementarity problem, Journal on Combinatorial Theory 8 (1970) 79–90. 

R. W. Cottle, J. Pang, R. E. Stone, The Linear Complementarity Problem, Academic Press, 1992.