I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of nodes $N_{k+1} \leq 0.5N_{k}$.

I think this means that the overall complexity should be order $\log N \times T(N)$ where $T(N)$ is the complexity of the FIRST linear relaxation. since the problem size gets at least cut in half each iteration. But there's two issues.

1) The complexity of the inner problem is reduced each iteration, so we're not doing $\log N$ iterations of $T(N)$ complexity, but something like $\sum_{i=0}^{\log N} T(N/2^i)$ or something. But is this the same as $\log N \times T(N)$ asymptotically or can I tighten my bound?

2) How do I find the complexity of my linear program? I've heard the figure $O(n^{3.5})$ where $n = $ number of variables for interior point methods and $n^3$ for average case Simplex, but I can't find a good source.

  • 1
    $\begingroup$ These are two separate unrelated questions. Please stick to one question per question. For the first question, try writing a recurrence relation and solving it. For the second one, the answers are well-documented -- what research have you done? $\endgroup$ – D.W. Apr 30 '15 at 21:44
  • $\begingroup$ possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – D.W. Apr 30 '15 at 21:44

Answering your first question, whether you can tighten the analysis depends on the function $T$. If $T$ is constant, for example, then the analysis is tight; if $T$ is a polynomial, then the analysis is not tight, and in fact you can remove the logarithmic factor: the answer is simply $O(T(N))$.

Answering your second question, the best known time complexity for solving linear programming is given in Yin Tat Lee and Aaron Sidford's recent paper, top of page 43: $$ \tilde{O}\left(\sqrt{\operatorname{rank}(A)}(\operatorname{nnz}(A)+\operatorname{rank}(A)^\omega)L\right). $$ Here:

  • $\tilde{O}$ hides logarithmic factors.
  • $A$ is the constraint matrix.
  • $\operatorname{rank}(A)$ is the rank of $A$.
  • $\operatorname{nnz}(A)$ is the number of non-zero entries in $A$.
  • $\omega$ is the matrix multiplication constant. The best known value currently, due to Le Gall, is $\omega < 2.3728639$, but it is suspected that $\omega = 2$.
  • $L$ is the bit complexity of the LP, roughly the number of bits in the encoding of the LP (see footnote 2 on page 2 for the exact definition).

The smoothed complexity of the simplex algorithm might be better, but unless your instance is random, smoothed complexity isn't going to help you.

| cite | improve this answer | |
  • $\begingroup$ Great stuff! Well $T$ must be polynomial since it's an LP, but I'm not quite sure how to arrive at the conclusion that I can drop the logarithmic factor? $\endgroup$ – Benjamin Lindqvist Apr 30 '15 at 14:55
  • 1
    $\begingroup$ It's a calculation. For example, if $T(N) = N$ then $\sum_{i=0}^\infty T(N/2^i) = N \sum_{i=0}^\infty (1/2)^i = 2N = 2T(N)$. $\endgroup$ – Yuval Filmus May 1 '15 at 0:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.