Parallel linear programming in fixed dimension almost surely in constant time.
For any fixed dimension ) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986
Introduction
The linear programming problem in fixed dimension is to maximize a linear function of
a fixed number, d, of variables, subject to n linear inequality constraints, where n is not
fixed. Megiddo [11] showed that for any d, this problem can be solved in O(n) time.
Clarkson [4] and Dyer [7] improved the constant of proportionality. Clarkson [5] later
developed linear-time probabilistic algorithms with even better complexity. The problem
in fixed dimension is interesting from the point of view of parallel computation, since
the general linear programming problem is known to be P-complete. The algorithm of
[11] can be parallelized efficiently, but the exact parallel complexity of the problem in
fixed dimension is still not known. 1 Here we develop a very efficient probabilistic parallel
algorithm based on Clarkson's [5] scheme.
In this paper, when we say that a sequence of events fE n g 1
occurs almost surely,
we mean that there exists an ffl ? 0 such that prob(E n
. A consequence of
this estimate is that with probability 1, only a finite number of the events do not occur.
The main result of this paper generalizes a known fact [12; 10] that the maximum of n
items can be computed almost surely in constant time.
As mentioned above, the basic idea of the underlying sequential algorithm is due to
Clarkson [5]. His beautiful iterative sequential algorithm uses an idea of Welzl [14]. As in
Clarkson's algorithm, we also sample constraints repeatedly with variable probabilities.
Several additional ideas and some modifications were, however, required in order to
achieve the result of this paper. Our probabilistic analysis is also different, and focuses
on probabilities of failure to meet time bounds, rather than on expected running times.
In particular, a suitable sequential implementation of our algorithm can be shown to
terminate almost surely within the best known asymptotic bounds on the expected time.
1 Ajtai and Megiddo recently developed deterministic algorithms which run on a linear number of
processors in poly(log log n) time.
In Section 2 we present a special form of the output required from a linear programming
problem, which unifies the cases of problems with optimal solutions and unbounded
ones. In Section 3 we describe the algorithm and provide the necessary probabilistic analysis

2. Preliminaries
The purpose of this section is to state the required form of the output of the linear
programming problem, which turns out to be useful for our purposes in this paper.
2.1 A special form of the output
ng and suppose the linear programming problem is given in the form
Minimize c \Delta x
subject to a i
where fc; a 1 ; . ; a n g ae R d and b 1 ; . ; b n are real scalars. An inequality a i \Delta x - b i is
called a constraint. We denote by LP S a similar problem where only a subset S ae N of
the constraints is imposed. If LP is infeasible (i.e., there is no x such that a i
exists a set Z ' N with jZj - d that LPZ is infeasible.
In this case we refer to the lexicographically minimal such Z as the defining subset.
For any S ' N , and for any fixed scalar t, denote by P S (t) the problem:
Minimize
subject to a i
The objective function of P S (t) is strictly convex, hence if LP S is feasible, then P S (t) has
a unique optimal solution x S (t). It is easy to see that the latter can be characterized
as the closest point to the origin, among all points x such that a i
c
Fix t, and let S ' N denote the set of indices i for which a i \Delta x N Obviously,
(t). Moreover, the classical Karush-Kuhn-Tucker optimality conditions imply
that is a nonnegative linear combination of the vectors a i (i 2 S), i.e.,
. By a classical theorem of linear programming, there exists a
set B ' S such that fa i g i2B are linearly independent and i2B . It
follows that x N d. Moreover, we have a i \Delta x N B). For
this particular value of t, the optimal solution does not change if the inequalities of PB (t)
are replaced by equalities. The importance of this argument about B is that it shows
the piecewise linear nature of the parametric solution.
2.2 Analysis of the parametric solution
Denote by B the matrix whose rows are the vectors a i (i 2 B), and let bB denote the
vector whose components are the corresponding b i 's. Assuming LPB is feasible, since
subject to Bx = bB , it follows that there exists a
jBj such that
Since the rows of B are linearly independent, we can represent the solution in the form:
so
where
and
The vector u however, will be the solution of PB (t) only for t such that y B (t) - 0.
Denote by I B the set of all values of t for which y B (t) - 0, and also a i \Delta
for all i 2 N . Obviously, I B is precisely the interval of t's in which x N
We have shown that if LP is feasible, then x N (t) varies piecewise linearly with t,
where each linearly independent set B contributes at most one linear piece. Thus, there
exists a "last" set Z ae N with jZj - d, and there exists a t 0 , such that for all t - t 0 ,
Given the correct Z, it is easy to compute
and the (semi-infinite) interval I Z in which x N . It is
interesting to distinguish the two possible cases. First, if v
for means that the original problem has a minimum, which is the same as
if only the constraints corresponding to Z were present. In this case, u Z is the optimal
solution that has the minimum norm among all optimal solutions. Second, if v Z 6= 0,
then the original problem is unbounded, and fu Z is a feasible ray along
which c \Delta x tends to \Gamma1. Moreover, each point on this ray has the minimum norm among
the feasible points with the same value of c \Delta x.
In view of the above, we can now define the vectors u N and v N to be equal to u Z
and v Z , respectively. Indeed, for any subset S ' N (whose corresponding vectors a i may
be linearly dependent), we can define the appropriate vectors u S and v S to describe the
output required in the problem LP S . To summarize, we have proven the following:
Proposition 2.1. If the ray coincides with the optimal solution of PN (t) for
all sufficiently large t, then there exists a subset Z ae N , whose corresponding vectors are
linearly independent, such that the ray coincides with the optimal solution of PZ (t) for
all such t.
For every point on a polyhedron, there exists precisely one face of the polyhedron which
contains the point in its relative interior. Consider the lexicographically minimal set Z
which describes this face. We say that this set Z is the defining subset of the solution
2.3 The fundamental property
Denote by V (u; v) the set of indices i 2 N for which a i sufficiently
large values of t. If we say that the corresponding constraint is asymptotically
violated on (u; v). Obviously, if is the set of indices i 2 N such
that a i \Delta only if either a i
and a i \Delta
The following proposition is essentially due to Clarkson [5]:
Proposition 2.2. For any S ae N such that V and for any I ae N such
that val(N; sufficiently large
Proof: If on the contrary V we arrive at the contradiction that
for all sufficiently large t,
where the strict inequality follows from the uniqueness of the solution of P S (t).
The importance of Proposition 2.2 can be explained as follows. If a set S has been
found such that at least one constraint is violated at the optimal solution of LP S , then
at least one of these violated constraints must belong to the defining set. Thus, when
the probabilistic weight of each violated constraint increases, we know that the weight of
at least one constraint from the defining set increases.
3. The algorithm
As mentioned above, the underlying scheme of our algorithm is the same as that of the
iterative algorithm in the paper by Clarkson [5], but the adaptation to a parallel machine
requires many details to be modified.
During a single iteration, the processors sample a subset S of constraints and solve
the subproblem LP S with "brute force." If the latter is infeasible then so is the original
one and we are done. Also, if the solution of the latter is feasible in the original problem,
we can terminate. Typically, though, some constraints of the original problem will be
violated at the solution of the sampled subproblem. In such a case, the remainder of the
iteration is devoted to modifying the sample distribution for the next iteration, so that
such violated constraints become more likely to be sampled. The process of modifying
the distribution is much more involved in the context of parallel computation. It amounts
to replicating violated constraints, so that processors keep sampling from a "uniform"
distribution. The replicating procedure is carried out in two steps. First, the set of
violated constraints is "compressed" into a smaller area, and only then the processors
attempt to replicate.
During the run of the algorithm, the probability that the entire "defining set" is
included in the sample increases rapidly. In order to implement the above ideas efficiently
on a PRAM, several parameters of the algorithm have to be chosen with care
and special mechanisms have to be introduced. The algorithm utilizes
processors d) the largest integer such that
d
first describe the
organization of the memory shared by our processors.
3.1 The shared memory
The shared memory consists of four types of cells as follows.
(i) The Base B, consisting of k cells, B[ 1 ]; . ; B[k].
2 The notation means that there exists a constant c ? 0 such that f(n) - cg(n).
(ii) The Sequence S, consisting of 2n cells, S[ 1 ]; . ; S[2n]. We also partition the
Sequence into 2n 3=4 blocks of length n 1=4 , so these cells are also addressed as S[I; J ],
(iii) The Table T , consisting of
log(16d) 2. We also partition the Table into C d blocks of length
so these cells are also addressed as T [I; J
(iv) The Area R, consisting of n 3=4 cells, R[ 1 ]; . ; R[n 3=4 ]. We also partition the
Area into n 1=4 blocks of size
n, so these cells are also addressed as R[I; J ],
Each memory cell stores either some halfspace H
the space R d . Initially, the other cells store the space
R d . The Base always describes a subproblem LPK where K is the set of the constraints
stored in the Base. By the choice of our parameters, every Base problem can be solved
by "brute force" in O(log 2 d) time as we show in Proposition 3.1 below.
The Sequence is where the sample space of constraints is maintained. Initially, the
Sequence stores one copy of each constraint. Throughout the execution of the algorithm,
more copies are added, depending on the constraints that are discovered to be violated at
solutions of subproblems. The role of the Table and the Area is to facilitate the process
of modifying the sample distribution.
3.2 The base problem
As already indicated, the algorithm repeatedly solves by "brute force" subproblems consisting
of k constraints
Proposition 3.1. Using a (2nd= log 2 d)-processor CRCW PRAM, any subproblem LPK
with d) constraints can be solved deterministically in O(log 2 d) time.
Proof: Recall that d. In order to solve the Base problem, p=
d
processors
are allocated to each subset B ae K such that d. Thus, the number of processors
assigned to each B is bounded from below by maxfd 3 ; kd= log 2 dg. It follows that
all the subproblems LPB can be solved in O(log 2 d) time, as each of them amounts
to solving a system of linear equations of order (2d) \Theta (2d), and we have at least
d 3 processors (see [2]). If any of the LPB 's is discovered to be infeasible then LP
is infeasible, and the algorithm stops. Otherwise, for each B the algorithm checks
whether asymptotically feasible (i.e., feasible for all sufficiently large t) in
LPK . With d= log 2 d processors, it takes O(log 2 d) time to evaluate the inner product
of two d-vectors. 3 Since there are at least kd= log 2 d processors assigned to each B,
3 It is easy to see that the inner product can be evaluated by d= log d processors in O(log d) time.
Here we can afford O(log 2 d) time, so we can save on the number of processors.
the asymptotic feasibility of all the in LPK can be checked in O(log 2 d)
time. Finally, the algorithm finds the best among the solutions of the LPB 's which are
feasible in LPK or, in case none of these is feasible in LPK , the algorithm recognizes
that LPK , and hence also LP , is infeasible. The final step is essentially a computation
of the minimum of
d
An algorithm of Valiant 4 [13] (which
can be easily implemented on a CRCW PRAM) finds the minimum of m elements,
using p processors, in O(log(log m= log(p=m))) time. Here,
d
d, so the time is O(log d).
3.3 The iteration
We now describe how the sampling works and how the sample space is maintained.
Sampling a base problem
An iteration of the algorithm starts with sampling a Base problem. As indicated above,
the sample space is stored in the S-cells. There are 2n such cells and each stores either
a constraint or the entire space; one constraint may be stored in more than one S-cell.
To perform the sampling, each of the first k processors P i generates a random integer 5
I i uniformly between 1 and 2n, and copies the contents of the S-cell S[I i ] into the B-cell
4 We note that with a different choice of k, namely, if k is such that \Gamma k
d
p, then the use of Valiant's
algorithm can be avoided.
5 We assume each of the processors can generate random numbers of O(log n) bits in constant time.
all the processors jointly solve the subproblem LPK currently stored in the
Base (see Proposition 3.1) in O(log 2 d) time.
Asymptotically violated constraints
Assuming LPK is feasible, the algorithm now checks which S-cells store constraints that
are violated asymptotically on the ray fu K sufficiently large. This task
is accomplished by assigning d= log 2 d processors to each cell S[ i ] as follows. For each i
the processors P j with 1 are assigned
to the cell S[ i ]; they check the asymptotic feasibility of the constraint stored therein, as
explained in Section 2. This step also takes O(log 2 d) time, since it essentially amounts
to an evaluation of inner products of d-vectors. For brevity, we say that an S-cell storing
an asymptotically violated constraint is itself violated.
Replicating violated constraints
Having identified the violated S-cells, the processors now "replicate" the contents of each
such cell n 1=(4d) times. The idea is that by repeating this step several times, the members
of the "defining set" get a sufficiently large probability to be included in the sample
(in which case the problem is solved). Since it is not known in advance which S-cells
are violated, and since there are only O(n) processors, the algorithm cannot decide in
advance which processors will replicate which cells. For this reason, the replication step is
carried out on a probabilistic CRCW PRAM in two parts. First, the violated S-cells are
injected into the Table (whose size is only O(n 1\Gamma1=(2d) )), and then replications are made
from the Table back into the Sequence, using a predetermined assignment of processors
to cells. The first part of this step is performed as follows.
Injecting into the Table: Operation 1
First, for any violated cell S[ i ], processor P i generates a random integer I 1
and m 0 , and attempts to copy the contents of S[ i
attempted
to write and failed, then it generates a random integer I 2
attempts
again to copy the contents of S[ i
In general, each such processor attempts
to write at most C d \Gamma 1 times, each time into a different block of the Table.
Proposition 3.2. The conditional probability that at least n 1=4 processors will fail to
write during all the C given that at most n
16d processors attempt to
write during the first trial, is at most e \Gamma\Omega\Gamma n 1=4 ) .
Proof: Let X i be the random variable representing the number of processors that failed
to write during the first i rounds (and therefore attempt to write during the (i 1)-st
round). Suppose
16d . Note that for each processor attempting to write
during the i-th round, the conditional probability that it will be involved in a write
conflict, given any information on the success or failure of the other processors during
this round, is at most X Thus, we can apply here estimates for independent
Bernoulli variables. By an estimate due to Chernoff [3] (apply Proposition 4.1 part (i)
with
Let j denote the largest integer such that
log(16d) for n sufficiently large. Notice that if indeed
all
and hence,
Thus,
16d . The probability that j does not satisfy the latter is at
most e \Gamma\Omega\Gamma n 1=4 ) . Combining this with Proposition 4.1 part (ii), we get
We note that, as pointed out by one of the referees, the analysis in the last proposition
can be somewhat simplified by having the processors try to inject the violated constraints
to the same table for some C 0
d times (or until they succeed). It is easy to see that for,
say, C 0
16d the conclusion of Proposition 3.2 will hold. However, this will increase the
running time of each phase of our algorithm to \Omega\Gamma d) and it is therefore better to perform
the first part of the injection as described above. Alternatively, the time increase can be
avoided by making all C 0
d attempts in parallel and then, in case of more than one success,
erase all but the first successful replication. We omit the details of the implementation.
Injecting into the Table: Operation 2
To complete the step of injecting into the Table, one final operation has to be performed.
During this operation, the algorithm uses a predetermined assignment of some
processors to each of the 2n 3=4 S-blocks, e.g., processor P j is assigned to the block
An S-cell is said to be active at this point if it has failed C
to be injected into the Table. An S-block is said to be active if it contains at least one
active cell. 6 For each active block S[ all the q processors assigned
to S[ ; J ] attempt to write the symbol J into the Area R as follows. The i-th processor
among those assigned to S[ ; J ] generates a random 7 integer I i between 1 and p
n, and
attempts to write the symbol J into the cell R[I
6 It takes constant time to reach the situation where each of the q processors knows whether or not it
is assigned to an active S-block.
7 This last step can also be done deterministically with hash functions.
Proposition 3.3. If there are less than n 1=4 active S-blocks, then the probability that
conflicts will occur in every single R-block is less than e \Gamma\Omega\Gamma n 1=4 ) .
Proof: At most n 1=4 processors attempt to write into any R-block (whose length is
n), so the probability of a conflict within any fixed R-block is less than 1=2. Thus,
the probability of conflicts in every single R-block is less than 2 \Gamman 1=4
It takes constant time to reach a situation where all the processors recognize that
a specific block R[ ; J   conflict (assuming at least one such block exists).
At this point, the names of all the active S-blocks have been moved into one commonly
known block R[ ; J   ]. The role of the area R is to facilitate the organization of the work
involved in replicating the remaining active S-blocks into the last T -block.
Next, n 1=4 processors are assigned to each cell R[I; J
n). Each such
cell is either empty or contains the index J I of some active S-block S[ ; J I ]. In the latter
case, the processors assigned to R[I; J   ] copy the contents of the active cells of S[ ; J I ]
into the last T -block, according to some predetermined assignment.
From the Table to the Sequence
For the second half of the replication step, the algorithm uses a predetermined (many-to-
assignment of the first C d n 1\Gamma1=(4d) processors to the
-cells, where n 1=(4d) processors are assigned to each cell. Each processor P j copies the
contents of T [oe(j)] into a cell S[ ' ], where
depends both on the processor and on the iteration number -. Later, we will discuss the
actual number of iterations. We will show that almost surely ' - 2n. In the unlikely
event that the number of iterations gets too large, the algorithm simply restarts with
3.4 Probabilistic analysis
In this section we analyze the probability that the algorithm fails to include the defining
set in the sample after a certain constant number of iterations.
Estimating the number of violated S-cells
Let - be any fixed weak linear order on N . Given the contents of the Sequence S and
the random Base set K, denote by -(S; K;-) the number of S-cells which store
halfspaces H i such that 8 j OE i for all j such that H j is in the Base.
Proposition 3.4. For any possible contents of the Sequence and for every ffl ? 0,
8 We write j OE i if and only if j - i and i 6- j.
Proof: For any x ? 0,
In particular, for
d+1 +ffl this probability is at most
Our claim follows from the fact that
For any M ' N such that LPM is feasible, denote by M
- the weak linear order induced
on N by the asymptotic behavior of the quantities b tends to
infinity. More precisely, j
only if for all sufficiently large t,
For brevity, denote - 0
Corollary 3.5. For any ffl ? 0, the conditional probability that there will be more than
violated S-cells on u K that LPK is feasible, is less than
d
Proof: Consider the set L of orders B
corresponds to a set of linearly
independent vectors (and hence jBj - d), and LPB is feasible. If LPK is feasible, then
by Proposition 2.1 there exists Z ' K, whose corresponding constraints are linearly
independent, such that
-2 L. By Proposition 3.4, for
any fixed M ,
d
d
Proposition 3.6. During each iteration, the probability that at least one active S-cell
will fail to inject its contents into the Table is at most e \Gamma\Omega\Gamma n 1=(16d) ) .
Proof: The proof follows immediately from Corollary 3.5 with
with Propositions 3.2 and 3.3.
Successful iterations
Let LPK denote the current Base problem. An iteration is considered successful in either
of the following cases:
(i) The problem LPK is discovered to be infeasible, hence so is LP and the algorithm
stops.
(ii) The problem LPK is feasible and its solution u turns out to be feasible for
LP for all sufficiently large t, so it is also the solution of LP and the algorithm
stops.
(iii) For at least one i in the defining set Z (see Section 2), H i is asymptotically violated
on storing H i are injected into the Table.
Proposition 3.7. During any iteration, given any past history, the conditional probability
of failure is at most e
Proof: By Proposition 2.2, if the solution of LP has not been found, then H i is violated,
for at least one i 2 Z, and hence every processor checking a copy of H i will attempt to
inject it into the Table. The result now follows from Proposition 3.6.
Proposition 3.8. For any fixed d, the probability that the algorithm will not finish within
9d 2 iterations is at most e \Gammad 2 n 1=(16d) ) .
Proof: Notice that in 9d 2 iterations, for sufficiently large n, only the first n
are possibly accessed. By Proposition 3.7, in each itera-
tion, the conditional probability of failure, given any past history, is at most e \Gamma\Omega\Gamma n 1=(16d) ) .
Therefore, the probability of less than 5d 2 successes in 9d 2 iterations is less than
To complete the proof, we show that it is impossible to have 5d 2 successes. This
is because if there are that many successes, then there exists at least one i in the
"defining set" Z such that during at least 5d of the iterations, the contents of all the
S-cells storing the halfspace H i are successfully injected into the Table. 9 This means
that there are at least
S-cells storing H i , whereas the total length of the Sequence is only 2n. Hence, a
contradiction.
Thus, we have proven the following:
Theorem 3.9. There exists a probabilistic parallel algorithm for the linear programming
problem with d variables and n constraints, which runs on a (2nd= log 2 d)-processor
CRCW PRAM with performance as follows. The algorithm always finds the correct so-
lution. There exists an ffl ? 0 (e.g., such that for every fixed d and for all
sufficiently large n, the probability that the algorithm takes more than O(d 2 log 2 d) time
is less than e \Gamma\Omega\Gamma n ffl=d ) .
A further improvement
It is not too difficult to modify the algorithm to obtain one for which there are two
constants independent of d with performance as follows. For every fixed dimension
d, and for all sufficiently large n, the probability that the running time will exceed
9 The Table is erased after each iteration.
d is at most 2 \Gamma\Omega\Gamma n ffl ) . This is done by choosing the size k of the Base problem so
that k
d
n. This enables us to solve during each iteration
random Base problems
simultaneously. As before, processors are assigned to S-cells. Each such processor
chooses randomly one of the Base problems. The processor then checks whether the
constraint in its cell is violated at the solution of the Base problem. With each of the
Base problems we associate a Table of size n 1
32d . Next, each processor which has a
violated S-cell (with respect to the Base problem i that was chosen by that processor)
attempts to inject the contents of its cell into the Table of Base problem i. This is done
as in the corresponding steps of the algorithm described above. We call a Base problem
successful if all the processors attempting to write succeed eventually. Note that if Base
problem i is successful, then not too many S-cells (among those whose processors chose
the Base problem i) were violated. Therefore, with high probability, not too many S-cells
altogether were violated at the solution of this Base problem. The algorithm now chooses
a successful Base problem. It then continues as the previous algorithm, i.e., it checks
which of all the S-cells are violated, injects these cells into a Table of size 2C d n 1\Gamma1=(4d) ,
and replicates each of the violated ones n 1=5d times. We say that an iteration is successful
if at least one of its
Base problems is successful, and the contents of all the violated
S-cells are injected successfully into the Table. It is not too difficult to check that the
conditional probability that an iteration will not be successful, given any information
about the success or failure of previous iterations, is at most e
We omit the details.
Remarks
The total work done by all the processors in our algorithm is O(d 3 n), whereas Clarkson's
sequential algorithm [5] runs in expected O(d 2 n) time. We can easily modify our algorithm
to run on a probabilistic CRCW PRAM with n=(d log 2 d) processors in O(d 3 log 2 d)
time, so that the total work is O(d 2 n). Moreover, the probability of a longer running
time is exponentially small in terms of n. To this end, observe that, using our previous
algorithm, we can solve in O(d 2 log 2 d) time and n=(d log 2 d) processors a Base problem
of size n=d 2 . Hence, we can repeat the previous algorithm by choosing Base problems
of size n=d 2 , solving them, checking all the violated S-cells in O(d 2 log 2 d) time, and
replicating each violated S-cell
times. Such an algorithm terminates almost surely
in O(d) iterations. Hence, the total parallel time is O(d 3 log 2 d).
4.

Appendix


The following proposition summarizes the standard estimates of the binomial distribution
which are used in the paper. A random variable X has the binomial distribution with
parameters n; p, if it is the sum of n independent (0; 1)-variables, each with expectation
p.
Proposition 4.1. If X is a binomial random variable with parameters n; p, then
(i) For every a ? 0,
ag
In particular, for a = 0:5np,
(ii) If a ? e 2 np then probfX ? ag ! e \Gammaa .
Proof: Part (i) is due to Chernoff [3]. (see also [1], p. 237). Part (ii) follows immediately
from the fact that
ag
a
a
en
a
' a ' a
' a

Acknowledgement

. We thank Moni Naor for helpful suggestions concerning the
step of injection into the Table, that led to a significant improvement in the estimate
of the failure probabilities. We also thank two anonymous referees for their helpful
comments.



--R

The Probabilistic Method
"Fast parallel matrix and GCD compu- tations,"
"A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations,"
"Linear programming in O(n3 d 2 ) time,"
"Las Vegas algorithms for linear and integer programming when the dimension is small,"
"An optimal parallel algorithm for linear programming in the plane,"
"On a multidimensional search technique and its application to the Euclidean one-center problem,"
"A randomized algorithm for fixed dimensional linear pro- gramming,"
"Linear programming with two variables per inequality in poly log time,"
"Parallel algorithms for finding the maximum and the median almost surely in constant-time,"
"Linear programming in linear time when the dimension is fixed,"
"A fast probabilistic parallel sorting algorithm,"
"Parallelism in comparison algorithms,"
"Partition trees for triangle counting and other range searching problems,"
--TR
Linear programming in O(n MYAMPERSANDtimes; 3<supscrpt>d<supscrpt>2</></>) time
On a multidimensional search technique and its application to the Euclidean one centre problem
Partition trees for triangle counting and other range searching problems
A randomized algorithm for fixed-dimensional linear programming
Linear programming with two variables per inequality in poly-log time
Linear Programming in Linear Time When the Dimension Is Fixed

--CTR
Sandeep Sen, Parallel multidimensional search using approximation algorithms: with applications to linear-programming and related problems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 24-26, 1996, Padua, Italy
Surender Baswana , Sandeep Sen, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Random Structures & Algorithms, v.30 n.4, p.532-563, July 2007
parallel computation;probabilistic computation;linear programming;computational geometry;multidimensional search