12
$\begingroup$

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight $x(F)=\sum_{e\in F}x(e)$ of a feasible solution $F\in{\cal F}$. An algorithm has the approximation factor $\alpha\leq 1$ on ${\cal F}$, if it always (for every input $x$) gives a solution at least $\alpha$ times the optimal solution.

The standard greedy algorithm solves this problem by ordering the elements $x(e_1)\geq x(e_2)\geq \ldots \geq x(e_n)$, heaviest first. Then it starts with the empty partial solution, and treats the elements in that order. At the $i$-th step, it accepts the next element $e_i$ (adds it to the partial solution) iff it can be accepted, i.e. if the extended solution is still feasible. It is assumed that the algorithm is "pessimistic" in that it will always choose the worst possible ordering between equally weighted elements.

Via an amazingly simple argument (see below1), Hausmann, Jenkyns and Korte have shown in about 1980 that, for every downwards closed family ${\cal F}$ ($A\subset B$ and $B\in{\cal F}$ implies $A\in{\cal F}$), the approximation factor of the greedy algorithm on ${\cal F}$ just coincides with the purely combinatorial characteristic of ${\cal F}$ called the rank quotient, and defined by: $$ r({\cal F})=\min\ \left\{\frac{lr(S)}{ur(S)}\colon S\subseteq E, \ ur(S)\neq 0\right\}\,, $$ where $lr(S)$ (the "lower rank") is the minimum and $ur(S)$ (the "upper rank") is the maximum cardinality of a maximal under set inclusion feasible subset of $S$. Note that $r({\cal F})$ is the worst possible ratio between the greedy solution and the optimal solution on $0$-$1$ inputs. In particular, $r({\cal F})=1$ iff ${\cal F}$ is a matroid, and it known that $r({\cal F})\geq 1/k$ if ${\cal F}$ is an intersection of $k$ matroids. Thus, this result is a far-reaching extension of the classical Rado-Edmonds theorem for matroids, and shows that the worst-case approximation factor of the greedy algorithm is achieved already on $0$-$1$ weightings, i.e. that these are the hardest inputs.

Still, this is a "worst case" result: for every input weighting $x$, we have $\mathrm{alg}(x)\geq r({\cal F})\cdot \mathrm{opt}(x)$, and there exist an input weighting $x$ for which $\mathrm{alg}(x)= r({\cal F})\cdot \mathrm{opt}(x)$. But what about the "average case": can greedy achieve a better approximation factor on most inputs $x$? To be more specific, consider a random $m$-weighting $\mathbf{x}:E\to \{0,1,\ldots,m-1\}$ which assigns each element $e\in E$ its weight independently at random with probability $1/m$. The following two "amortized" versions of approximation factor seem to be quite natural:

  • The typical approximation factor $\alpha_p({\cal F})$ = largest $\alpha$ such that $\mathrm{alg}(\mathbf{x})/\mathrm{opt}(\mathbf{x})\geq \alpha$ holds with probability $\geq p$.
  • The expected approximation factor $\alpha[{\cal F}]$ = expected value of $\mathrm{alg}(\mathbf{x})/\mathrm{opt}(\mathbf{x})$.

Since the expected weight $\frac{m-1}{2}|A|$ of every subset $A\subseteq E$ depends only on the cardinality of $A$, we have that $\alpha[{\cal F}]\geq r({\cal F})$. We also have that $\alpha_p({\cal F})\geq \alpha_1({\cal F}) = r({\cal F})$. But, for some families ${\cal F}$, greedy can have much better "amortized" behavior.

For example, if ${\cal F}$ is the family of all $|{\cal F}|=2^n+1$ feasible solutions for the vertex packing (or maximum weight independent set) problem on the star $K_{1,n}$ with $n$ edges, then $r({\cal F})=1/n$, implying that greedy cannot achieve any better approximation factor than $1/n$ in the worst case. But the random $m$-weighting $\mathbf{x}$ will put the center of the star as the first only with probability $\leq 1/m$, meaning that $\alpha_p({\cal F})=1$ already for $p= 1-1/m$. Thus, even though greedy fails baldly in the worst case, it is optimal on all but a small proportion $1/m$ of all inputs $x$! The expected factor $\alpha[{\cal F}]$ is also near to $1$ for this family.

Does anybody know of more examples of families ${\cal F}$, for which $\alpha_p({\cal F})$ and/or $\alpha[{\cal F}]$ are much larger than the rank quotient $r({\cal F})$?

Question: Are there any combinatorial/probabilistic lower bounds on $\alpha_p({\cal F})$ and/or $\alpha[{\cal F}]$ depending only on ${\cal F}$, but not on the weightings (as the rank quotient)?

Strangely enough, from the literature somehow related to this question, I could only find this paper (and the literature therein).


Proof of HJK: If $e_1,\ldots,e_n$ is any ordering of $E$, then for every subset $A\subseteq E$ and for every weighting $x:E\to \{0,1,\ldots\}$, we have $x(A)=\sum_{i=1}^n|A_i|\cdot \left( x(e_{i})-x(e_{i+1})\right)$, where $x(e_{n+1}):=0$ and $A_i=A\cap E_i$ with $E_i=\{e_1,\ldots,e_i\}$. This holds, because the difference $|A_i|-|A_{i-1}|$ is either $0$ or $1$, and is $1$ if and only if $e_i\in A_i$. If $A$ is the solution produced by the greedy algorithm, then the way the greedy algorithm works yields that $|A_i|\geq lr(E_i)$ must hold for all $i$. On the other hand, $|B_i|\leq ur(E_i)$ clearly holds for all feasible solutions $B$, including an optimal one. By the definition of the rank quotient, $lr(E_i)\geq r({\cal F})\cdot ur(E_i)$ holds for all $i$. Moreover, all differences $x(e_{i})-x(e_{i+1})$ are nonnegative, since the greedy algorithm uses the heaviest first ordering $x(e_1)\geq x(e_2)\geq\ldots\geq x(e_n)$. This yields $x(A)\geq r({\cal F})\cdot x(B)$, as desired.

To see that the approximation factor cannot be larger than $r({\cal F})$, take a set $S\subseteq E$ and two its subsets $A,B\subseteq S$ achieving the minimum in the definition of $r({\cal F})$; hence, $r({\cal F})=|A|/|B|$. Give weight $1$ to all elements of $A\cup B$, and weight $0$ to the rest. Then the pessimistic greedy will output $A$, whereas the optimum is at least $|B|$. $\Box$

$\endgroup$
  • $\begingroup$ Perhaps, for any $\cal F$, the ratios you ask about are maximized when in your $m$-weighting $m=2$? Considering that the algorithm must break ties in the worst order, this seems plausible. Maybe you know a counter-example? (Also, for fixed $m$, the phrase "not on the weightings" in your Question is a little strange, as you've stipulated that weights must be assigned using a random $m$-weighting.) $\endgroup$ – Neal Young May 20 '17 at 22:40

Your Answer

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

Browse other questions tagged or ask your own question.