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

<p>No, it's just a <a href="https://en.wikipedia.org/wiki/Selection_algorithm" rel="nofollow noreferrer">selection problem</a>, for which there are <a href="https://en.wikipedia.org/wiki/Quickselect" rel="nofollow noreferrer">well-known linear algorithms</a>.</p>

CC BY-SA 4.0
2018-05-16T07:57:27.693Z
2018-05-16T07:57:27.693Z
Peter Taylor
<p>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.</p>

<p>The example comes from <a href="https://arxiv.org/pdf/0809.3232.pdf" rel="nofollow noreferrer">this paper</a> 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$.</p>

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

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

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

<ds.algorithms><approximation-algorithms>
How can algorithms with nested combinatorial searches be quasi-linear?
user3209815
# How can algorithms with nested combinatorial searches be quasi-linear?

(Asked by: username_0 on 2018-05-15)

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](https://arxiv.org/pdf/0809.3232.pdf) 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.

**Tags:** ds.algorithms, approximation-algorithms


---

## 1 answers

### Answer by username_1 on 2018-05-16. Score: 2

> 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](https://en.wikipedia.org/wiki/Selection_algorithm), for which there are [well-known linear algorithms](https://en.wikipedia.org/wiki/Quickselect).


---

