0
$\begingroup$

I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without stating any relaxing conditions. Since I haven't encountered any proofs that specifically target this issue, I wonder if there is something obvious I'm missing in algorithm analysis.

The example comes from this paper by Spielman and Teng, more specifically section 2.1, algorithm Nibble. The algorithm is a for-loop (with the number iterations defined approximately by $log_2(n) ln(n)$, where $n$ is the number of vertices in the graph). However, step 3.c states that the algorithm will exit, if a suitable set of $j$ vertices exists that satisfies some conditions. This set is in the paper's terminology designated as $S_j(q_t)$ and is defined as "the set of $j$ vertices $u$ that maximize $\frac{q_t(u)}{d(u)}$", where $d(u)$ is the degree of vertex $u$.

Note that the focus here is on the general problem of generating a subset of elements that fulfills some conditions and is subject to a constrained number of elements. Other aspects of the algorithm were covered in the proof.

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set. Also, I found no mention of it in the proof section. That, the reputability of the authors and the prominence of the paper makes me think that it's something obvious.

My question is what factors would make such an algorithm quasi-linear? Citing a paper where a similar algorithm's complexity is proven and the proof focuses this issue is most welcome.

$\endgroup$
2
$\begingroup$

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set.

No, it's just a selection problem, for which there are well-known linear algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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