0
$\begingroup$

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements.

Question: true or false?

Approximation Algorithms, Vazirani, 2001, 1e, p.16, Algorithm 2.2:

  1. $C \leftarrow \varnothing$
  2. While $C \neq U$ do Find the set whose cost-effectiveness is smallest, say $S$.

Let $\alpha = \frac{c(S)}{|S - C|}$, i.e., the cost-effectiveness of $S$.

Pick $S$, and for each $e \in S - C$, set $\text{price}(e) = \alpha$.

$C \leftarrow C \cup S.$

  1. Output the picked sets.

In the first iteration, the cost-effectiveness of $M$ sets have to be computed.

In the second iteration, the cost-effectiveness of $M-1$ sets have to be computed.

Since everything between $1$ and $M$ iterations may be needed to find the sets that cover all elements, in the mean it may be $M/2$ iterations.

I.e. in the worst case we need to compute $M + (M-1) + (M-2) + ... + 1 = M(M+1)/2$ times the cost effectiveness.

Determining cost-effectiveness requires the computation of a difference which has time complexity proportional to the number of elements.

Hence, the time complexity is dominated by the term $M^2N$.


EDIT

If the greedy algorithm outlined above does not have time complexity of $M^2N$, where's the flaw in estimating the computation time?

The following diagram shows the computation time per atomic operation versus the test index of 65 tests I ran my code on. The tests range from 6 sets to 1215 sets, and the values on the y-axis are computed as

$$ \text{computation time per atomic operation} = \text{cpu time used} / (M^2N). $$

From what I can tell, the assumed time complexity $M^2N$ seems to model the behavior well. Otherwise, the computation time per atomic operation wouldn't be that stable. Small values for the y-axis are either due to the computation time being too short to be measured, or if the number of elements is substantially smaller than the number of sets ($N \ll M$).

enter image description here


EDIT (Sun APR 19 2020)

This post cites exercise 35.3-3 taken from Introduction to Algorithms (3e) claiming that the (unweighted) set cover problem can be solved in time

$$ \mathcal{O}\left(\sum_{S \in \mathcal{F}}|S|\right), $$

where $S$ is a set of the problem description, and $\mathcal{F}$ are all the sets in the problem description.

Compared to the naming convention I'm using, this would mean that the problem can be solved in quadratic time $\mathcal{O}(MN)$. But how?

The algorithm still requires to find the set with the maximum number of elements involved, which requires to evaluate every set modulo the recently added one. Hence,

$$ M + (M - 1) + ... + 1 = (M + 1)M / 2, $$

which is quadratic in $M$ again.

Or is there a more efficient way to do so?


EDIT (Mon APR 20 2020)

My initial estimate of $\mathcal{O}(M^2N)$ does not seem to be that bad. Refering to Introduction to Algorithms (3e), page 1119, last paragraph of section A greedy approximation algorithm, it is said

a simple implementation runs in time $\mathcal{O}(|X||\mathcal{F}|\min(|X|, |\mathcal{F}|))$

where $|X|$ is the overall number of elements, and $|\mathcal{F}|$ reflects the overall number of sets.

Dividing the cpu time by this new upper bound, the variance of the time per atomic operation is clearly smaller compared to the upper bound used initially:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Feb 29 at 20:16
0
$\begingroup$

Acc. to Introductions to Algorithms (3e), given a "simple implementation" of the above given greedy set cover algorithm, and assuming the overall number of elements equals the overall number of sets ($|X| = |\mathcal{F}|$), the code runs in time $\mathcal{O}(|X|^3)$. So there are cases when the algorithm behaves cubic.

| cite | improve this answer | |
$\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.