next up previous
Next: A Toy Problem Up: The Algorithm In Detail Previous: The Iterative Part

Computational Complexity

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 $A$ once. Therefore the expected computational complexity for solving one LP-problem is ${\cal
O}\left(m^2\left\Vert S_\mathrm{\scriptscriptstyle sep}\right\Vert\right)$, where $m$ 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 $\left\Vert S_\mathrm{\scriptscriptstyle sep}\right\Vert$ of a similar size.

For every $\vec s_\mathrm{\scriptscriptstyle mar}\in S_\mathrm{\scriptscriptstyle mar}$ 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 $A$ and vector $\vec b$ from Equation [*]. The vector $\vec c$, that defines the objective function, obviously does vary with $\vec s_\mathrm{\scriptscriptstyle mar}$. Therefore, we expect a total computational complexity of ${\cal
O}\left(m^2\left\Vert S_\mathrm{\scriptscriptstyle mar}\right\Vert\left\Vert S_\mathrm{\scriptscriptstyle sep}\right\Vert\right)$ for updating one cluster $S_\mathrm{\scriptscriptstyle mar}$. 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.


next up previous
Next: A Toy Problem Up: The Algorithm In Detail Previous: The Iterative Part
Martijn Leisink 2003-08-18