LP-problems have been thoroughly studied in the literature.
The computational complexity of such problems is shown to be
polynomial khachiyan. But more importantly, for most
practical problems the number of iterations needed is close to linear
in the number of variables or the number of constraints, whichever
is less todd. In each iteration a `pivoting action'
needs to be performed, which is some operation that roughly accesses
all the elements of the matrix 
once. Therefore the expected
computational complexity for solving one LP-problem is
, where 
is the number of constraints.
The actual observed computation time depends heavily on the particular
problem, but in general LP-problems upto tens of thousands
of variables and constraints are reasonable. This makes the presented
method tractable for separators with
of a similar size.
For every
we need to solve two
LP-problems: one for the upper and one for the lower bound.
Note that in this iteration, we do not need to change the matrix
and vector 
from Equation ![[*]](crossref.png)
. The vector 
, that
defines the objective function, obviously does vary with
.
Therefore, we expect a total computational complexity of
for updating one cluster
. How quickly the algorithm converges is more difficult to
estimate. In the next section, however, we address this topic on the
basis of a toy problem.
To conclude this section, we remark that when the LP-problem is not tractable, one can always leave out as many constraints as needed, paying the price of getting looser bounds.