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 . 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.