An algorithm $\mathscr{A}$ for a maximization problem (optimal value $z(I)$) has relative error $\frac{z(I)-\mathscr{A}(I)}{z(I)}$ at most $\varepsilon=\frac14$. What is its relative guarantee $\alpha$, meant as a bound on the ratio $z(I)/\mathscr{A}(I)$?
$\alpha=\frac43$
$\alpha=\frac54$
$\alpha=\frac34$
$\alpha=4$
Explanation. For a maximization problem $z-\mathscr{A}\le\varepsilon z$ gives $z/\mathscr{A}\le\frac{1}{1-\varepsilon}=\frac43$; for a minimization problem one would get $1+\varepsilon=\frac54$.
For a minimization problem, a heuristic finds $\mathscr{A}(I)=12$ and the optimal value is $z(I)=10$. What are the performance ratio $\mathscr{A}(I)/z(I)$ and the relative error $\frac{\mathscr{A}(I)-z(I)}{z(I)}$?
$\frac56$ and $20\%$
$\frac65$ and $2$
$\frac56$ and $16.7\%$
$\frac65$ and $20\%$
Explanation. For minimization the ratio is $\mathscr{A}(I)/z(I)=\frac{12}{10}$, always at least $1$; the relative error is $\frac{12-10}{10}=20\%$; the additive error is $2$.
An approximation scheme receives an instance and an $\varepsilon>0$ and returns a solution with relative error at most $\varepsilon$. Which statement on PTAS and FPTAS is correct?
In both a PTAS and an FPTAS the time is polynomial for every fixed $\varepsilon$, and in neither in $\frac1\varepsilon$
A time $O(n^{1/\varepsilon})$ is polynomial both in the size and in $\frac1\varepsilon$, hence it gives an FPTAS
In a PTAS the time is polynomial for every fixed $\varepsilon$; in an FPTAS it is polynomial in $\frac1\varepsilon$ too
In a PTAS the time is polynomial in $\frac1\varepsilon$ too; in an FPTAS only for every fixed $\varepsilon$
Explanation. A running time such as $O(n^{1/\varepsilon})$ is polynomial for fixed $\varepsilon$ (PTAS) but not in $\frac1\varepsilon$; an FPTAS, such as $O(n^2/\varepsilon)$, is polynomial in both.
For a minimization problem, the relative guarantee of an algorithm $\mathscr{A}$ is a constant $\alpha$ with $\mathscr{A}(I)\le\alpha\,z(I)$ for every instance $I$. On some instance $\mathscr{A}$ has ratio $\mathscr{A}(I)/z(I)=\frac32$. What does this instance prove?
That every constant larger than $\frac32$ is a relative guarantee of $\mathscr{A}$
That no constant smaller than $\frac32$ is a relative guarantee of $\mathscr{A}$
That $\frac32$ is a relative guarantee of $\mathscr{A}$, valid for every instance
That the worst-case ratio of $\mathscr{A}$ is exactly $\frac32$
Explanation. An instance only gives a lower bound on $r(\mathscr{A})$: proving that $\frac32$ is a guarantee requires a proof valid for every instance.
For a maximization problem, the performance ratio of an algorithm $\mathscr{A}$ on instance $I$ is $z(I)/\mathscr{A}(I)$, with $z(I)$ the optimal value. A knapsack heuristic finds $\mathscr{A}(I)=16$ on an instance with $z(I)=20$. What is the ratio?
$4$
$\frac{9}{5}$
$\frac54$
$\frac45$
Explanation. $20/16=\frac54\ge 1$. In maximization problems the optimum goes in the numerator, so the ratio is always at least $1$ as in minimization problems; $\frac45$ is the inverted ratio.
The worst-case performance ratio $r(\mathscr{A})$ is the supremum of the performance ratios of $\mathscr{A}$ over all instances, and $\mathscr{A}$ is an $\alpha$-approximation if the ratio is at most $\alpha$ on every instance. Which statement is correct?
$r(\mathscr{A})$ is always attained by some instance
$\mathscr{A}$ is an $\alpha$-approximation if and only if $\alpha\ge r(\mathscr{A})$
$\mathscr{A}$ is an $\alpha$-approximation if and only if $\alpha=r(\mathscr{A})$
$\mathscr{A}$ is an $\alpha$-approximation if and only if $\alpha\le r(\mathscr{A})$
Explanation. Every ratio is at most the supremum, so $\alpha=r(\mathscr{A})$ and every larger $\alpha$ are guarantees; a smaller constant is not. The supremum may only be approached, as for $GR^e$ in the knapsack.
For a minimization problem, $\mathscr{A}$ has additive guarantee $\beta$ if $\mathscr{A}(I)-z(I)\le\beta$ for every instance. An algorithm for coloring planar graphs uses at most $5$ colors, and the graph contains a triangle. Which additive guarantee follows on these graphs?
$\beta=2$, because $\chi(G)\ge 3$
$\beta=5$, the number of colors used
$\beta=\frac53$, the ratio of colors used to chromatic number
$\beta=1$, because $\chi(G)\le 4$
Explanation. With a triangle $\chi(G)\ge 3$, hence $5-\chi(G)\le 2$. The additive guarantee measures the difference, not the ratio.
For a minimization problem, an algorithm with additive guarantee $\beta$ satisfies $\mathscr{A}(I)\le z(I)+\beta$. What does it imply for the performance ratio $\mathscr{A}(I)/z(I)$?
$\mathscr{A}(I)/z(I)\le\beta$ for every instance
$\mathscr{A}(I)/z(I)\ge 1+\beta$ for every instance
Nothing: the two guarantees are independent
$\mathscr{A}(I)/z(I)\le 1+\beta/z(I)$, which tends to $1$ as $z(I)$ grows
Explanation. Dividing by $z(I)>0$ gives $1+\beta/z(I)$: on instances with large optimal value an additive guarantee is stronger than any constant relative guarantee.
For a minimization problem, an $\alpha$-approximation satisfies $\mathscr{A}(I)\le\alpha\,z(I)$ for every instance. A $2$-approximation returns a solution of value $30$. What is known about the optimal value $z(I)$?
$30\le z(I)\le 60$
$z(I)\le 15$
$15\le z(I)\le 30$
$z(I)=15$
Explanation. The solution is feasible, so $z(I)\le 30$; the guarantee gives $30\le 2z(I)$, i.e., $z(I)\ge 15$. The guarantee provides a dual bound even without a relaxation.
An approximation scheme for a maximization problem is a family of algorithms $\{\mathscr{A}_\varepsilon\}_{\varepsilon\in(0,1)}$ which, for every $\varepsilon$ and every instance, have relative error $\frac{z(I)-\mathscr{A}_\varepsilon(I)}{z(I)}$ at most $\varepsilon$. What is expected of the running time as $\varepsilon$ decreases?
That it becomes exponential for every $\varepsilon<\frac12$
That it grows: a smaller allowed error needs more time
That it decreases: with small $\varepsilon$ there are fewer solutions to examine
That it stays constant: $\varepsilon$ changes only the guarantee
Explanation. It is natural that time grows when the allowed error decreases; PTAS and FPTAS differ exactly in how it grows with respect to $\frac1\varepsilon$.
An approximation scheme with $n$ input elements and error parameter $\varepsilon$ is an FPTAS if the time is polynomial both in the instance size and in $\frac1\varepsilon$. Which of the following times gives an FPTAS?
$O(n^2/\varepsilon)$
$O(n^{1/\varepsilon})$
$O(2^{1/\varepsilon}\,n)$
$O(n^{1/\varepsilon^2})$
Explanation. $n^2/\varepsilon$ is a polynomial in $n$ and $\frac1\varepsilon$: it is the time of the Basic-FPTAS for the knapsack. The others are polynomial in $n$ for fixed $\varepsilon$ (PTAS) but not in $\frac1\varepsilon$.
A PTAS for a problem has time $O(n^{1/\varepsilon})$ on instances with $n$ elements. How does the time change going from $\varepsilon=\frac12$ to $\varepsilon=\frac1{10}$?
From $O(n^2)$ to $O(n^{2/10})$: it decreases
It stays $O(n^2)$: the exponent does not depend on $\varepsilon$
It becomes exponential in $n$
From $O(n^2)$ to $O(n^{10})$: polynomial for every fixed $\varepsilon$, but with growing exponent
Explanation. For every fixed $\varepsilon$ the time is a polynomial in $n$, but its degree grows as $\frac1\varepsilon$: this is why it is not an FPTAS.
For a heuristic algorithm $\mathscr{A}$ and an instance $I$, $z(I)$ is the optimal value and $\mathscr{A}(I)$ the heuristic value, both assumed positive. Why is positivity assumed?
Because every optimization problem has positive values
Because $\mathscr{A}(I)$ must equal $z(I)$
Because negative values are infeasible
So that the ratios $\mathscr{A}(I)/z(I)$ and $z(I)/\mathscr{A}(I)$ are defined and meaningful
Explanation. Relative guarantees compare the two values through a ratio: with a zero value or values of different sign the ratio would lose meaning.
The performance ratio of an algorithm $\mathscr{A}$ on an instance $I$ is $\mathscr{A}(I)/z(I)$ for a minimization problem and $z(I)/\mathscr{A}(I)$ for a maximization problem ($z(I)$ = optimal value). What is it with $z=40$, $\mathscr{A}=50$ (minimum) and with $z=40$, $\mathscr{A}=32$ (maximum)?
$1.25$ in both cases
$1.25$ and $0.8$
$0.8$ and $1.25$
$0.8$ in both cases
Explanation. $50/40=1.25$ and $40/32=1.25$. With these definitions the ratio is always at least $1$, whatever the direction of optimization.
In approximation algorithms a heuristic is evaluated in the worst case, with a relative (multiplicative) or an absolute (additive) guarantee. What does the absolute guarantee measure?
The ratio between the heuristic value and the optimal value
The worst-case running time
The difference between the optimal value and a lower bound
The difference between the heuristic value and the optimal value
Explanation. The relative guarantee bounds a ratio, the absolute one the error $|\mathscr{A}(I)-z(I)|$, over all instances.
An algorithm for a maximization problem has absolute performance guarantee $k=3$: $z(I)-\mathscr{A}(I)\le3$ on every instance. On an instance with $z(I)=50$, which heuristic value is guaranteed?
At least $53$
At least $150$
At least $47$
At least $50/3$
Explanation. The absolute error is at most $3$: $\mathscr{A}(I)\ge50-3$. $50/3$ confuses the absolute guarantee with a ratio.
A maximization problem has $z(I)=30$ and an algorithm $\mathscr{A}$ returns $\mathscr{A}(I)=20$. What is the performance ratio on $I$?
$10$
$\frac13$
$\frac32$
$\frac23$
Explanation. For a maximization problem the ratio is $z(I)/\mathscr{A}(I)=30/20=\frac32$, written with the optimum in the numerator so that it is at least $1$.
If an algorithm $\mathscr{A}$ always returns a feasible solution, what can be said of its performance ratio on every instance?
It can be negative
It is at least $1$
It is at most $1$
It is always exactly $1$
Explanation. A feasible solution is never better than the optimum: the ratio (defined with the optimum «on the right side») is $\ge1$, with equality only at the optimum.
An algorithm for a minimization problem has $\mathscr{A}(I)\le 2z(I)$ on every instance. What can be concluded?
It is a $2$-approximation algorithm
It is a $2$-additive algorithm
Its relative error is at most $\frac12$
It is an approximation scheme
Explanation. $\mathscr{A}(I)/z(I)\le2$ for every $I$ is exactly the definition of an $\alpha$-approximation with $\alpha=2$; the relative error is at most $1$.
An algorithm for a maximization problem has $\mathscr{A}(I)\ge\frac12 z(I)$ on every instance. Which $\alpha$-approximation is it?
$\alpha=\frac12$
$\alpha=\frac32$
None: for maximization problems $\alpha$ is less than $1$
$\alpha=2$
Explanation. For a maximization problem one requires $z(I)/\mathscr{A}(I)\le\alpha$: from $\mathscr{A}(I)\ge\frac12z(I)$ we get $z(I)/\mathscr{A}(I)\le2$. In the course $\alpha\ge1$ always.
An algorithm is proved to be a $\frac32$-approximation and a family of instances is found on which the ratio tends to $\frac32$. What has additionally been shown?
That the guarantee $\frac32$ is tight
That the algorithm is optimal
That the problem has no approximation scheme
That $r(\mathscr{A})<\frac32$
Explanation. A family of instances whose ratio tends to $\alpha$ rules out every $\alpha'<\alpha$: the guarantee is tight and $r(\mathscr{A})=\frac32$.
A maximization problem has $z(I)=17$; which values can a $2$-additive algorithm return on this instance?
Only $15$
Any value between $\frac{17}{2}$ and $17$
Any value between $15$ and $17$
Any value between $17$ and $19$
Explanation. For a maximization problem the additive guarantee is $z(I)-\mathscr{A}(I)\le2$, and $\mathscr{A}(I)\le z(I)$: hence $15\le\mathscr{A}(I)\le17$.
What is an approximation scheme for a problem $\mathscr{P}$?
A pseudo-polynomial exact algorithm
A family of instances on which a guarantee is tight
A family of algorithms $\mathscr{A}_\varepsilon$
A single algorithm with relative error at most $\frac12$
Explanation. The scheme lets one choose the precision: for every $\varepsilon$ there is an algorithm with relative error $\le\varepsilon$ on all instances.
A scheme runs in time $O(n^{1/\varepsilon})$. What is it?
A polynomial exact algorithm
A PTAS, but not an FPTAS
An FPTAS
Neither a PTAS nor an FPTAS
Explanation. For fixed $\varepsilon$ the time is polynomial in $n$ (PTAS), but the exponent grows with $\frac1\varepsilon$: it is not polynomial in $\frac1\varepsilon$, hence not an FPTAS.
What is called the «accuracy» of an approximation scheme?
The relative error $\varepsilon$
The ratio $1+\varepsilon$
The running time
The quantity $\frac1\varepsilon$
Explanation. The smaller $\varepsilon$, the larger $\frac1\varepsilon$ and the more precise the solution: this is why $\frac1\varepsilon$ is called the accuracy.
A scheme for a maximization problem has relative error $\varepsilon=\frac14$. Which approximation guarantee does it give?
$\varepsilon=\frac14$, i.e. $\frac14$
$1-\varepsilon=\frac34$
$\frac{1}{1-\varepsilon}=\frac43$
$1+\varepsilon=\frac54$
Explanation. For a maximization problem $\mathscr{A}_\varepsilon(I)\ge(1-\varepsilon)z(I)$, hence $z(I)/\mathscr{A}_\varepsilon(I)\le\frac{1}{1-\varepsilon}$; $1+\varepsilon$ holds for minimization problems.
Which relation links the worst-case ratio $r(\mathscr{A})$ to the relative guarantees of $\mathscr{A}$?
$r(\mathscr{A})=1$ for every feasible algorithm, whatever the guarantee $\alpha$
It is the smallest guarantee $\alpha$, i.e. the tight one
Every guarantee $\alpha$ of $\mathscr{A}$ is strictly smaller than $r(\mathscr{A})$, and no guarantee is tight
$r(\mathscr{A})$ is always finite, and every guarantee $\alpha\ge1$ is tight for $\mathscr{A}$
Explanation. Every guarantee is $\ge r(\mathscr{A})$ and $r(\mathscr{A})$ itself is a guarantee (if finite): it is the smallest one, i.e. the tight one.
$\mathscr{A}_\varepsilon(I)=z(I)$ for $\varepsilon$ small enough
Explanation. From $(\mathscr{A}_\varepsilon(I)-z(I))/z(I)\le\varepsilon$ we get $\mathscr{A}_\varepsilon(I)\le(1+\varepsilon)z(I)$: the guarantee is relative, not additive.
What does $e(\mathscr{A})=\infty$ mean for an algorithm $\mathscr{A}$?
$\mathscr{A}$ has no finite relative guarantee
$\mathscr{A}$ does not terminate
$\mathscr{A}$ returns infeasible solutions
$\mathscr{A}$ has no finite additive guarantee
Explanation. $e(\mathscr{A})$ is the smallest additive guarantee: if it is infinite, the difference from the optimum is bounded by no constant. A relative guarantee may still exist.
Which relation holds between the classes of approximation schemes?
PTAS and FPTAS are the same thing
An FPTAS is not an approximation scheme
Every FPTAS is a PTAS, not conversely
Every PTAS is an FPTAS
Explanation. A time polynomial in $n$ and in $\frac1\varepsilon$ is in particular polynomial in $n$ for fixed $\varepsilon$; $O(n^{1/\varepsilon})$ shows that the converse is false.
The approximation guarantees of the chapter use $\mathscr{A}(I)\ge z(I)$ (minimization) or $\mathscr{A}(I)\le z(I)$ (maximization). Which assumption on $\mathscr{A}$ is needed?
That the instance has a unique optimal solution
That it always returns a feasible solution
That $\mathscr{A}$ is polynomial
That $\mathscr{A}$ is a greedy algorithm
Explanation. The comparison with the optimum holds because the heuristic solution is feasible: an infeasible solution could be worth more than the optimum.
Because otherwise the problem has no feasible solutions
Because greedy algorithms require positive weights
In order to use the additive guarantee
Explanation. With $z(I)=0$ the ratios are undefined and with values of different sign they make no sense; the additive guarantee instead does not need positivity.
An algorithm has $\mathscr{A}(I)\le 2z(I)$ on all instances except an infinite family. Is it a $2$-approximation?
Yes, if the family is infinite but rare
Yes: it is enough that it holds on the reference instances
Yes, if $r(\mathscr{A})<\infty$ on the other instances
No: it must hold for every instance
Explanation. The definition requires the inequality for every instance $I$: even a single instance with ratio larger than $2$ breaks the guarantee $2$.
In the definition of a PTAS the running time of $\mathscr{A}_\varepsilon$ must be polynomial in the instance size: for which $\varepsilon$?
Only for $\varepsilon=\frac12$
For no $\varepsilon$: pseudo-polynomial is enough
For every fixed $\varepsilon\in(0,1)$
Uniformly in $\varepsilon$, with the same polynomial
Explanation. For a PTAS it is enough that every $\mathscr{A}_\varepsilon$, with fixed $\varepsilon$, is polynomial; if the time is polynomial also in $\frac1\varepsilon$ the scheme is an FPTAS.
To prove that a relative guarantee $\alpha$ is tight, what is it enough to exhibit?
An instance with ratio larger than $\alpha$
An instance with ratio exactly $\alpha$
An instance on which the algorithm is optimal
A proof that $\mathscr{A}(I)\le\alpha z(I)$
Explanation. The inequality $\mathscr{A}(I)\le\alpha z(I)$ proves the guarantee; tightness requires instances that reach it or approach it arbitrarily closely. A ratio larger than $\alpha$ would disprove the guarantee.
On three instances an algorithm for a minimization problem has ratios $1$, $\frac32$ and $\frac43$, and no instance does worse than $\frac32$. What is $r(\mathscr{A})$?
$1$
$\frac{23}{18}$
$\frac32$
$\frac43$
Explanation. $r(\mathscr{A})$ is the supremum of the ratios over all instances, not the average: $\frac32$.
What does one confuse when calling «$\varepsilon$-approximation» a scheme with relative error $\varepsilon$?
Minimization with maximization
Running time with space
The error with the ratio
The PTAS with the FPTAS
Explanation. A relative error $\varepsilon$ gives ratio $1+\varepsilon$ (minimization) or $\frac{1}{1-\varepsilon}$ (maximization), never $\varepsilon<1$.
For the knapsack problem (KP): $GR$ is the greedy by efficiency, $GR^e$ takes the best of $GR$ and the best single item, $H^2$ tries all subsets of at most two items completing them with the greedy; $r(\cdot)$ is the worst-case ratio. Which statement is correct?
$GR$, $GR^e$ and $H^2$ all have ratio $2$
$GR$ has no constant guarantee, $GR^e$ has $r(GR^e)=2$, $H^2$ has $r(H^2)=\frac43$
$GR$ has $r(GR)=2$ and $GR^e$ has $r(GR^e)=\frac43$
$GR^e$ has $r(GR^e)=\frac32$ and $H^2$ has $r(H^2)=2$
Explanation. The greedy by efficiency can be arbitrarily bad; taking the best of $GR$ and the best single item gives $2$; guessing two items ($H^2$) gives $\frac43$; all the ratios are tight.
In the knapsack problem, $GR$ is the greedy by efficiency, $p_{\max}$ the maximum profit of an item and $GR^e(I)=\max\{GR(I),p_{\max}\}$; with the items sorted by efficiency, $s$ is the split item. Which facts are used to prove $z(I)/GR^e(I)\le 2$?
$z(I)=GR(I)$ with sorted items; $GR(I)\ge p_s$; $p_{\max}\ge p_s$
Explanation. $z(I)\le z(\mathrm{LP}_{\mathrm{KP}})\le\sum_{i<s}p_i+p_s\le GR(I)+p_{\max}\le 2\,GR^e(I)$: the greedy takes at least the items before $s$, and the best single item is worth at least $p_s$.
For the knapsack problem (KP), algorithm $H^{\ell}$ tries all subsets of at most $\ell$ items and completes each with the greedy by efficiency. Which worst-case performance ratio does it guarantee with $\ell=3$?
$\frac43$
$\frac32$
$\frac65$
$\frac54$
Explanation. $r(H^{\ell})=\frac{\ell+2}{\ell+1}$: with $\ell=3$ we get $\frac54$. The running time $O(n^{\ell+1})$ grows with $\ell$: the family is a PTAS, not an FPTAS.
For the knapsack problem (KP, $n$ items, capacity $c$, integer profits), an algorithm has absolute guarantee $k$ if $z(I)-\mathscr{A}(I)\le k$ for every instance. What does the theorem on the absolute guarantee for the KP state?
There is a polynomial algorithm with absolute guarantee $p_{\max}$, the maximum profit of an item
There is a polynomial algorithm with absolute guarantee $1$, obtained by rounding the Dantzig bound
An algorithm with absolute guarantee $k$ and time $O(f(n,c))$ would solve every instance optimally in the same time
An algorithm with absolute guarantee $k$ and time $O(f(n,c))$ would give an FPTAS with time $O(f(n,c)/k)$
Explanation. Multiplying the profits by $k+1$ turns an absolute error $\le k$ into zero error: an algorithm with a fixed absolute guarantee would solve the KP exactly in the same time.
0-1 knapsack with capacity $c=9$ and items already sorted by non-increasing efficiency $p_j/w_j$: $p=(10,7,6,4)$, $w=(5,4,3,3)$. The split item $s$ is the first one not fitting entirely, and $\mathit{rc}=c-\sum_{j<s}w_j$ is the residual capacity. What are $s$ and $\mathit{rc}$?
$s=2$, $\mathit{rc}=0$
$s=3$, $\mathit{rc}=3$
$s=4$, $\mathit{rc}=0$
$s=3$, $\mathit{rc}=0$
Explanation. The first two items weigh $5+4=9\le c$; adding the third gives $12>9$, hence $s=3$ and $\mathit{rc}=9-9=0$. The second item is the last that fits, not the split item.
In the 0-1 knapsack (weights $w_j\le c$, items sorted by non-increasing efficiency) the split item is the first one not fitting entirely. Why is $\sum_j w_j>c$ assumed?
Because otherwise the split item would be the first one
Because otherwise the greedy does not terminate
Otherwise all items fit, there is no split item and taking them all is optimal
Because otherwise the LP relaxation is unbounded
Explanation. With $\sum_j w_j\le c$ the instance is trivial: the greedy takes everything and is optimal. The assumption guarantees that the split item exists.
0-1 knapsack with capacity $c=8$ and items sorted by non-increasing efficiency: $p=(12,9,5,2)$, $w=(4,3,2,1)$. The greedy $GR$ examines the items in this order and takes every item that fits, even after the split item. What is $GR(I)$?
$28$
$23$
$21$
$24$
Explanation. Items $1$ and $2$ fit (weight $7$); item $3$ does not (it would be $9$); item $4$ does (weight $8$): $12+9+2=23$. Stopping at the split item would give $21$.
0-1 knapsack with large capacity $c=M$ and two items: $(p_1,w_1)=(2,1)$ and $(p_2,w_2)=(M,M)$. The greedy by efficiency $GR$ takes item $1$ first. What is the ratio $z(I)/GR(I)$?
$\frac M2$, which grows without bound with $M$
$2$, for every $M$
$1$: $GR$ is optimal
$\frac{M+2}{2}$, but bounded by $2$
Explanation. Item $1$ has efficiency $2>1$; after it item $2$ does not fit, so $GR(I)=2$ while $z(I)=M$. This is why $GR$ has no constant guarantee, and $GR^e$ adds the comparison with the best single item.
The Ext-Greedy algorithm for the knapsack is $GR^e(I)=\max\{GR(I),\,p_{\max}\}$, where $GR$ is the greedy by efficiency and $p_{\max}$ the largest profit of an item (fitting alone). On the instance with $c=M$, items $(2,1)$ and $(M,M)$, what is $GR^e(I)$?
$2$, the value of $GR$
$M+2$, the sum of the profits
$\frac M2$
$M$, the optimal value
Explanation. $GR(I)=2$ and $p_{\max}=M$, hence $GR^e(I)=M=z(I)$: the comparison with the single item repairs exactly the case where $GR$ fails.
For the 0-1 knapsack, the Ext-Greedy algorithm $GR^e(I)=\max\{GR(I),p_{\max}\}$ has ratio $z(I)/GR^e(I)\le 2$ on every instance. Which instance shows that $2$ cannot be improved?
All items equal: $GR^e$ is always optimal
A single item: the ratio is $1$
$c=2M$ and three items $(2,1)$, $(M,M)$, $(M,M)$: $GR^e$ is about $M$, the optimum $2M$
$c=M$ and two items $(2,1)$, $(M,M)$: $GR^e$ is optimal
Explanation. The greedy takes $(2,1)$ and one of the items $(M,M)$, then the other does not fit: $GR=M+2$; $p_{\max}=M$; the optimum takes the two large items, $2M$. The ratio $\frac{2M}{M+2}$ tends to $2$.
The $H^2$ algorithm for the knapsack tries every feasible pair of items $(i,k)$, $i<k$. After inserting $i$ and $k$, on which items does it run $GR^e$ to complete the solution?
On the items with profit larger than $\max\{p_i,p_k\}$
On the other items with profit at most $\min\{p_i,p_k\}$ and weight at most the residual capacity
On all the other items, whatever their profit
Only on the items more efficient than $i$ and $k$
Explanation. $H^2$ guesses the two items of largest profit of an optimal solution: the residual items must therefore have no larger profit. The result is the maximum over all completions and $p_{\max}$.
The $H^2$ algorithm for the knapsack with $n$ items tries $O(n^2)$ pairs of items and for each runs $GR^e$ on the residual items. How much time does it take?
$O(n^3)$, and $O(n^2)$ with a more careful implementation
$O(n\log n)$, as the greedy
$O(2^n)$, because it tries subsets
$O(n^4)$, for every implementation
Explanation. With the items already sorted by efficiency, every completion costs $O(n)$ and the pairs are $O(n^2)$; a more careful implementation goes down to $O(n^2)$. In exchange the guarantee drops from $2$ to $\frac43$.
The $H^{\ell}$ algorithm for the knapsack tries all sets of $\ell$ items and completes them with the greedy; it has worst-case ratio $\frac{\ell+2}{\ell+1}$ and time $O(n^{\ell+1})$. What are the guarantee and the time with $\ell=4$?
$\frac54$ and $O(n^4)$
$\frac65$ and $O(n^4)$
$\frac43$ and $O(n^5)$
$\frac65$ and $O(n^5)$
Explanation. $\frac{4+2}{4+1}=\frac65$ and $n^{4+1}=n^5$. Every extra item in the «guess» improves the guarantee and multiplies the time by $n$.
For the knapsack, $H^{\varepsilon}$ is $H^{\ell}$ with $\ell=\lceil 1/\varepsilon\rceil-2$ (at least $2$ and at most $n$), and $H^{\ell}$ has ratio $\frac{\ell+2}{\ell+1}$. With $\varepsilon=\frac1{10}$, which $\ell$ is used and which ratio is guaranteed?
$\ell=8$ and ratio $\frac98$
$\ell=9$ and ratio $\frac{11}{10}$
$\ell=8$ and ratio $\frac{10}{9}$
$\ell=10$ and ratio $\frac{12}{11}$
Explanation. $\ell=10-2=8$ and $\frac{8+2}{8+1}=\frac{10}{9}$, i.e., relative error at most $\frac1{10}$. The time $O(n^{\ell+1})$ is polynomial for fixed $\varepsilon$: the family is a PTAS.
The Basic-FPTAS $FP^{\varepsilon}$ for the knapsack guarantees $z(I)/FP^{\varepsilon}(I)\le\frac1{1-\varepsilon}$. With $\varepsilon=0.2$, which guarantee follows, and which relative error?
Ratio at most $5$, relative error at most $80\%$
Ratio at most $\frac54$, relative error at most $20\%$
Ratio at most $\frac65$, relative error at most $20\%$
Ratio at most $\frac54$, relative error at most $25\%$
Explanation. $\frac1{1-0.2}=\frac54$; in terms of error $\frac{z-FP}{z}\le\varepsilon=20\%$. $\frac65=1+\varepsilon$ would be the guarantee of a minimization problem.
The Basic-FPTAS for the knapsack replaces the profits $p_j$ with scaled profits $\lfloor p_j/K\rfloor$ and solves the scaled instance to optimality with dynamic programming by profits. Why does the time become polynomial in $n$ and $\frac1\varepsilon$?
The scaled profits are small (of order $n/\varepsilon$), and the DP by profits costs in proportion to the total profit
Because the DP on the capacity does not depend on the profits
Because the scaled instance has fewer items
Because rounding the profits makes the greedy optimal
Explanation. With $K$ proportional to $\varepsilon$ and to a bound on the optimum divided by $n$, the scaled profits are bounded by a polynomial in $n$ and $\frac1\varepsilon$; the DP by profits then takes $O(n^2/\varepsilon)$ steps.
The theorem on the absolute guarantee for the knapsack (integer profits) states that an algorithm with $z(I)-\mathscr{A}(I)\le k$ on every instance would solve every instance to optimality in the same time. Which construction is used in the proof?
Divide all profits by $k$ and round down
Add $k$ dummy items of zero profit
Reduce the capacity by $k$ units
Multiply all profits by $k+1$: two different values differ by at least $k+1$, so an error at most $k$ is zero
Explanation. On instance $I'$ with profits $(k+1)p_j$ the solutions are the same, $z(I')=(k+1)z(I)$, and the values are multiples of $k+1$: an error at most $k$ must be $0$, and the solution is optimal for $I$ too.
In the chapter on knapsack approximation, $z(I)$ is the optimal value and $\mathscr{A}(I)$ the profit of the solution of a heuristic $\mathscr{A}$. Which relations hold for every instance?
$\mathscr{A}(I)\ge z(I)$ and $\mathscr{A}(I)/z(I)\ge1$
$\mathscr{A}(I)=z(I)$
$\mathscr{A}(I)\le z(I)$ and $\mathscr{A}(I)/z(I)\ge1$
$\mathscr{A}(I)\le z(I)$ and $z(I)/\mathscr{A}(I)\ge1$
Explanation. The knapsack is a maximization problem: the heuristic solution is worth at most the optimum, and the ratio is written with the optimum in the numerator to be at least $1$.
The $H^2$ algorithm for the 0/1 knapsack considers every feasible ordered pair of items $(i,k)$: it inserts it, then fills the residual capacity with a greedy on the items of profit at most $\min\{p_i,p_k\}$. On which idea is it based?
It is enough to try the pairs of lightest items
The best pair is always the one of maximum total profit
An optimal solution either has a single item, or contains two items of maximum profit among its own, which $H^2$ guesses by trying all pairs
An optimal solution always contains the two most efficient items
Explanation. Trying all pairs, one of them is made of the two most profitable items of an optimal solution; the other optimal items have profit at most the minimum of the pair and remain candidates of the greedy.
The greedy $GR$ for the 0/1 knapsack inserts the items by non-increasing efficiency, while they fit. On the instance with $c=\vartheta$, item $1$ with $(p_1,w_1)=(2,1)$ and item $2$ with $(p_2,w_2)=(\vartheta,\vartheta)$, what is $z(I)/GR(I)$?
$(\vartheta+2)/\vartheta$
$\vartheta/2$, which grows without bound: $GR$ has no constant guarantee
$2$, for every $\vartheta$
$1$: $GR$ is optimal
Explanation. $GR$ takes item $1$ (efficiency $2$) and then item $2$ does not fit: $GR=2$, while $z=\vartheta$. Ext-Greedy, which also compares with the best single item, fixes the problem.
Why can the greedy $GR$ by efficiency be arbitrarily far from the optimum of the 0/1 knapsack?
A small and very efficient item can take the capacity that a large and profitable item would need
Because $GR$ does not respect the capacity
Because $GR$ sorts the items by weight
It cannot: $GR$ is a $2$-approximation
Explanation. With $c=\vartheta$, $(2,1)$ and $(\vartheta,\vartheta)$ the greedy is worth $2$ and the optimum $\vartheta$. The remedy is $GR^e=\max\{GR,\max_jp_j\}$.
Ext-Greedy for the 0/1 knapsack is $GR^e(I)=\max\{GR(I),\max_jp_j\}$ and guarantees $z(I)\le2\,GR^e(I)$. On the instance with $c=2\vartheta$ and items $(2,1)$, $(\vartheta,\vartheta)$, $(\vartheta,\vartheta)$, what is $z(I)/GR^e(I)$?
$1$
$\frac{\vartheta}{2}$
$\frac32$
$\frac{2\vartheta}{\vartheta+2}$, which tends to $2$: the guarantee is tight
Explanation. $GR$ takes $(2,1)$ and one $(\vartheta,\vartheta)$, then the other does not fit: $GR=\vartheta+2=GR^e$. The optimum takes the two large items: $2\vartheta$.
The $H^2$ algorithm for the 0/1 knapsack guarantees $z(I)\le\frac43H^2(I)$. On the instance with $c=4M$, item $(2,1)$ and four items $(M,M)$, $H^2$ is worth $3M+2$. Why does the ratio $\frac{4M}{3M+2}$ show that $\frac43$ cannot be improved?
It is smaller than $1$
It tends to $2$
It tends to $\frac43$ as $M\to\infty$
It equals $\frac43$ exactly for every $M$
Explanation. A pair of large items leaves capacity $2M$; the greedy first takes $(2,1)$, more efficient, then only one $(M,M)$: $2M+2+M$. The optimum is worth $4M$.
0/1 knapsack instance with $c=4M$, an item $(p,w)=(2,1)$ and four items $(M,M)$, with $M=10$. What are the optimal value and the value of $H^2$ (pair of items, then greedy by efficiency on the items of profit at most the minimum of the pair)?
$z=40$, $H^2=22$
$z=40$, $H^2=32$
$z=40$, $H^2=40$
$z=42$, $H^2=32$
Explanation. The optimum fills the knapsack with the four large items. The best pair for $H^2$ is two large items: then $(2,1)$ and only one more $(10,10)$ fit ($1+10\le20$): $20+2+10=32$.
The $H^{\ell}$ algorithm for the 0/1 knapsack tries all sets of at most $\ell$ items and completes each with the greedy; its guarantee is $\frac{\ell+2}{\ell+1}$, tight. What is it for $\ell=2$ and for $\ell=4$?
$\frac43$ and $\frac65$
$\frac32$ and $\frac54$
$2$ and $\frac43$
$\frac43$ and $\frac43$
Explanation. $\frac{2+2}{2+1}=\frac43$ (it is $H^2$) and $\frac{6}{5}$. The larger $\ell$, the better the guarantee, but the time $O(n^{\ell+1})$ grows.
The family $H^{\varepsilon}$, i.e., $H^{\ell}$ with $\ell(\varepsilon)=\lceil\frac1\varepsilon\rceil-2$, has time $O(n^{\ell(\varepsilon)+1})$. Why is it a PTAS but not an FPTAS for the 0/1 knapsack?
Because the time is exponential in $n$ for every $\varepsilon$
Because it does not guarantee relative error $\varepsilon$
It is also an FPTAS
For fixed $\varepsilon$ the time is polynomial in $n$, but the exponent grows with $\frac1\varepsilon$, so it is not polynomial in $\frac1\varepsilon$
Explanation. An FPTAS needs a time polynomial both in $n$ and in $\frac1\varepsilon$; with $\varepsilon=\frac1{10}$, $H^{\varepsilon}$ already needs $O(n^9)$.
For $H^{\varepsilon}$ (the 0/1 knapsack with $\ell(\varepsilon)=\lceil\frac1\varepsilon\rceil-2$ and time $O(n^{\ell+1})$), which exponent of $n$ is needed for a relative error $\varepsilon=\frac15$?
$n^2$
$n^6$
$n^4$, because $\ell=5-2=3$
$n^5$
Explanation. $\ell(\frac15)=\lceil5\rceil-2=3$ and the time is $O(n^{3+1})$. The growth of the exponent with the precision is what separates a PTAS from an FPTAS.
The Basic-FPTAS algorithm $FP^{\varepsilon}$ for the 0/1 knapsack scales the profits with $p'_j=\lfloor p_j/K\rfloor$, $K=\varepsilon\,GR^e(I)/n$, and solves the scaled instance to optimality. Which guarantee does it get?
$FP^{\varepsilon}(I)\ge z(I)-\varepsilon$
$FP^{\varepsilon}(I)\ge(1-\varepsilon)\,z(I)$
$FP^{\varepsilon}(I)=z(I)$
$FP^{\varepsilon}(I)\ge z(I)/2$
Explanation. Every profit loses less than $K$ in the rounding, so a solution loses less than $nK=\varepsilon\,GR^e(I)\le\varepsilon\,z(I)$.
The Basic-FPTAS for the 0/1 knapsack solves the scaled instance with the DP on profits, truncating the table at $Q=\lfloor2n/\varepsilon\rfloor$ columns, for a time $O(n^2/\varepsilon)$. Which fact justifies the truncation?
The guarantee $z(I)\le2\,GR^e(I)$ of Ext-Greedy bounds the optimal scaled value by $2n/\varepsilon$
The fact that the scaled profits are at most $1$
The fact that always $n\le Q$
None: the truncation may lose the optimum
Explanation. The optimal scaled value is at most $z(I)/K=z(I)\,n/(\varepsilon\,GR^e(I))\le2n/\varepsilon$. Without the guarantee of $GR^e$ the table would depend on $\sum_jp_j$.
Basic-FPTAS for the 0/1 knapsack with $n=10$ items and $\varepsilon=\frac1{10}$: the DP on the scaled profits has $n+1$ rows and at most $Q+1$ columns, with $Q=\lfloor2n/\varepsilon\rfloor$. What is $Q$?
$20$
$100$
$2000$
$200$
Explanation. $Q=\lfloor2\cdot10\cdot10\rfloor=200$, hence about $11\cdot201$ cells: the time $O(n^2/\varepsilon)$ does not depend on the original profits.
For the 0/1 knapsack the chapter determines the worst-case performance ratio $z(I)/\mathscr{A}(I)$ of several algorithms. Which ordering of the guarantees is correct?
All have ratio $2$
$GR$: $\frac43$; $GR^e$: no constant; $H^2$: $2$; $H^{\ell}$: $\frac{\ell+1}{\ell}$
$GR$: no constant; $GR^e$: $2$; $H^2$: $\frac43$; $H^{\ell}$: $\frac{\ell+2}{\ell+1}$
Explanation. Every algorithm improves the previous one at the price of more time; with growing $\ell$ one gets a PTAS, and with profit scaling an FPTAS.
In the 0/1 knapsack the critical item $s$ is the first item, in the order of non-increasing efficiency, that does not fit entirely together with the previous ones. Why does it always exist, under the assumption $\sum_jw_j>c$?
Because every item weighs more than $c/2$
It does not always exist: it depends on the profits
Adding the items in order, sooner or later the weight exceeds $c$
Because the least efficient item weighs more than $c$
Explanation. If all items fitted together one would have $\sum_jw_j\le c$, against the assumption; the first item making the weight exceed $c$ is the critical item.
The greedy algorithm $GR$ for the knapsack scans the items by non-increasing efficiency and takes every item fitting in the residual capacity. With $c=9$ and sorted items $(p_j,w_j)=(8,4),(6,3),(5,5),(2,2)$, what is $GR$?
$16$
$14$
$19$
$13$
Explanation. It takes $(8,4)$ and $(6,3)$ (weight $7$), skips $(5,5)$, takes $(2,2)$: $16$. $14$ stops at the critical item.
Ext-Greedy for the knapsack returns the best between the greedy solution $GR$ and the best single item. With $c=10$ and items $(p_j,w_j)=(2,1)$ and $(10,10)$, what are $GR$ and Ext-Greedy?
$GR=2$, Ext-Greedy $=12$
$GR=12$, Ext-Greedy $=12$
$GR=2$, Ext-Greedy $=10$
$GR=10$, Ext-Greedy $=10$
Explanation. $GR$ takes the most efficient item $(2,1)$ and then $(10,10)$ does not fit; the best single item is worth $10$, which is optimal.
The algorithm $H^2$ for the knapsack tries every pair of items $(i,k)$ as «the two most profitable items of an optimal solution» and completes with Ext-Greedy on the fitting items with $p_j\le\min\{p_i,p_k\}$. Why only those items?
They are consistent with the guess on $i$ and $k$
Because the other items are always heavier
To make the residual greedy solution optimal
Because the most profitable items never fit
Explanation. If $i,k$ really are the two most profitable items of the optimum, the other items of the optimum have profit at most $\min\{p_i,p_k\}$: restricting the instance does not lose that solution.
The algorithm $H^{\ell}$ for the knapsack guesses the $\ell$ most profitable items and completes every guess with Ext-Greedy in time $O(n)$; it runs in $O(n^{\ell+1})$. How much time does it take with $\ell=3$?
$O(n^3)$
$O(3n)$
$O(2^n)$
$O(n^4)$
Explanation. The sets of $3$ items are $O(n^3)$, each completed in $O(n)$: $O(n^4)$. Polynomial for every fixed $\ell$.
The algorithm $H^{\ell}$ for the knapsack examines $O(n^{\ell})$ sets of $\ell$ items, one at a time, completing each with Ext-Greedy. How much memory does it need, besides the data?
$O(nc)$
$O(2^n)$
$O(n)$
$O(n^{\ell})$
Explanation. Only the current set, the residual solution and the best value are kept: space $O(n)$. The guesses need not be stored all together.
Basic-FPTAS for the knapsack scales the profits with $K=\varepsilon\,lb/n$ ($lb$ = value of Ext-Greedy) and uses $p'_j=\lfloor p_j/K\rfloor$. With $\varepsilon=0.1$, $lb=200$ and $n=10$, what are $K$ and the scaled profit of an item with $p_j=37$?
$K=0.5$, $p'_j=74$
$K=2$, $p'_j=18$
$K=2$, $p'_j=18.5$
$K=20$, $p'_j=1$
Explanation. $K=0.1\cdot200/10=2$ and $\lfloor37/2\rfloor=18$: the scaled profits are integer, so that the DP on profits can be used.
Basic-FPTAS for the knapsack solves to optimality the instance with scaled profits $\lfloor p_j/K\rfloor$, leaving weights and capacity unchanged, and returns that solution. Why is it feasible for the original instance?
Weights and capacity do not change: the constraints are the same
Because the scaled profits are smaller than the original ones
Because the weights are scaled by the same factor too
It is not always: it must be repaired with greedy
Explanation. Scaling touches only the objective; the feasible solutions of the two instances coincide, and only their value changes.
For the knapsack (maximization) the guarantees are written as $z(I)/\mathscr{A}(I)\le\alpha$. Which fraction of the optimum does an algorithm with $\alpha=\frac43$ guarantee?
At least $\frac43$ of $z(I)$
At most $\frac34$ of $z(I)$
At least $\frac13$ of $z(I)$
At least $\frac34$ of $z(I)$
Explanation. $z/\mathscr{A}\le\frac43$ is equivalent to $\mathscr{A}\ge\frac34z$. A value larger than $z$ is impossible in a maximization problem.
Knapsack with large $c$ and two items: $(p,w)=(2,1)$ and $(c,c)$. Which ratio $z/GR$ does greedy $GR$ (by efficiency, takes what fits) obtain, and what does it show?
$c$: because $GR$ is worth only $1$
$c/2$: the ratio of $GR$ is unbounded
$2$: it is exactly the worst case of $GR$
$1$: here $GR$ finds the optimum
Explanation. $GR$ takes $(2,1)$, more efficient, and then $(c,c)$ does not fit: $GR=2$, $z=c$. For $c\to\infty$ the ratio grows without bound.
The family $H^{\varepsilon}$ (i.e., $H^{\ell}$ with $\ell(\varepsilon)=\lceil1/\varepsilon\rceil-2$) is a PTAS for the knapsack, with time $O(n^{\ell+1})$. With $\varepsilon=0.1$, what are $\ell$ and the exponent of the time?
$\ell=8$, time $O(n^2/\varepsilon)$
$\ell=1$, time $O(n^2)$
$\ell=8$, time $O(n^9)$
$\ell=10$, time $O(n^{11})$
Explanation. $\lceil10\rceil-2=8$, hence $O(n^9)$: polynomial for fixed $\varepsilon$, but the exponent grows with $1/\varepsilon$; that is why it is not an FPTAS.
Theorem: if a polynomial algorithm $\mathscr{A}$ for the knapsack had absolute guarantee $k$ ($z-\mathscr{A}\le k$), it would solve the problem to optimality. What is the idea of the proof?
Increase the capacity by $k$
Multiply the profits by $k+1$
Divide the profits by $k$ and round
Remove $k$ items from the instance
Explanation. On the instance with profits $(k+1)p_j$ two different values differ by at least $k+1>k$: the solution of $\mathscr{A}$ is optimal, also for the original instance.
The 0/1 knapsack is NP-hard. If $P\neq NP$, which kind of guarantee does it admit in polynomial time?
Only relative, up to an FPTAS
Only absolute, with constant error $k$
Both, relative and absolute
No guarantee of any kind
Explanation. A constant absolute guarantee would give the optimum in polynomial time; relative guarantees instead exist (Ext-Greedy, $H^{\ell}$, FPTAS).
In bin packing (BPP), Next Fit (NF), Worst Fit (WF), First Fit (FF) and Best Fit (BF) pack the items one at a time in the given order. What are their worst-case performance ratios $r(\cdot)$?
$r(NF)=r(WF)=2$ and $r(FF)=r(BF)=\frac{17}{10}$
$r(NF)=2$ and $r(WF)=r(FF)=r(BF)=\frac{17}{10}$
$r(NF)=r(WF)=r(FF)=r(BF)=2$
$r(NF)=\frac{17}{10}$ and $r(FF)=r(BF)=\frac32$
Explanation. All Any Fit algorithms have the half-full property, hence they are $2$-approximation algorithms; WF asymptotically attains $2$ as NF does, while FF and BF have $\frac{17}{10}$.
In bin packing (capacity $c$, weights $w_i$, optimum $z(I)$), a solution with $k$ bins has the half-full property if at most one bin has total weight at most $c/2$. Which facts are needed to prove that an algorithm with this property is a $2$-approximation?
The property gives $\sum_i w_i>(k-1)\frac c2$; the LP relaxation equals $\sum_i w_i/c$ and its dual has an integer solution
Every item weighs more than $c/2$; every solution with $z(I)$ bins has $\sum_i w_i\le z(I)\,c$; $k$ is an integer
The items are sorted by non-increasing weight; $z(I)\ge\lceil\sum_i w_i/c\rceil$; $k$ is an integer
The property gives $\sum_i w_i>(k-1)\frac c2$; every solution with $z(I)$ bins has $\sum_i w_i\le z(I)\,c$; $k$ is an integer
Explanation. From the two inequalities $(k-1)\frac c2<z(I)\,c$, i.e., $k<2z(I)+1$, and by integrality $k\le 2z(I)$.
In bin packing, an algorithm is Any Fit if it opens a new bin only when the current item fits in none of the bins already open. Which fact is used to prove that its solutions have the half-full property (at most one bin with weight at most $c/2$)?
The items are sorted by non-increasing weight, hence the first bins are full
The number of bins is at most $\frac{17}{10}z(I)$, hence few bins are empty
The content of two bins never fits into one, whatever the bin selection rule
The rule always chooses the bin with minimum residual capacity, which fills up first
Explanation. If two bins both had weight at most $c/2$ they could be merged, but the Any Fit condition excludes it. NF is not Any Fit, but it still has guarantee $2$.
In bin packing, Next Fit (NF) keeps a single bin open and, if the item does not fit, closes it and opens a new one. An algorithm is Any Fit if it opens a new bin only when the item fits in none of the previous ones. Why is NF not Any Fit?
It may exceed the capacity of the open bin
It may open a bin for an item that would fit into a closed bin
It sorts the items by non-increasing weight before packing them
It always chooses the bin with maximum residual capacity
Explanation. An Any Fit algorithm opens a new bin only if the item fits into none of the bins opened so far; NF keeps a single open bin.
Bin packing with capacity $c=10$ and items of weight $6,5,4,3,2$ in this order. Next Fit (NF) keeps a single bin open and opens a new one when the item does not fit; First Fit (FF) puts each item into the first open bin where it fits. How many bins do they use?
NF $4$, FF $2$
NF $3$, FF $2$
NF $2$, FF $2$
NF $3$, FF $3$
Explanation. NF: $\{6\}$, $\{5,4\}$, $\{3,2\}$. FF: $\{6,4\}$, $\{5,3,2\}$: the item of weight $4$ goes back to the first bin, which NF has already closed.
Bin packing with capacity $c=10$: three open bins have residual capacities $2$, $5$ and $3$, and an item of weight $3$ arrives. Where do First Fit (first that fits), Best Fit (smallest sufficient residual) and Worst Fit (largest residual) put it?
FF in the $1$st, BF in the $1$st, WF in the $2$nd
FF in the $3$rd, BF in the $3$rd, WF in the $2$nd
FF in the $2$nd, BF in the $2$nd, WF in the $3$rd
FF in the $2$nd, BF in the $3$rd, WF in the $2$nd
Explanation. The first bin (residual $2$) is not enough. FF takes the second, BF the smallest sufficient residual ($3$, the third), WF the largest ($5$, the second). All three are Any Fit algorithms.
In bin packing a solution has the half-full property if at most one bin has total weight at most $c/2$. With $c=10$, a solution has loads $(4,4,7)$. Can it have been produced by an Any Fit algorithm (which opens a new bin only if the item fits in none of the previous ones)?
Yes, but only with Worst Fit
No, because the total load $15$ is not a multiple of $c$
No: two bins have load at most $5$, and the content of the second would have fitted into the first
Yes: every feasible solution is obtained with some order of the items
Explanation. Any Fit solutions have the half-full property: when the second lightly loaded bin was opened, its first item fitted into the other one. The loads $4$ and $4$ violate the property.
Next Fit (NF) is not an Any Fit algorithm, yet it has $NF(I)\le 2\,z(I)$ in bin packing. Which fact is used in the proof?
The content of any two bins does not fit into one
Two consecutive NF bins together weigh more than $c$
Every NF bin weighs more than $c/2$
NF sorts the items by non-increasing weight
Explanation. NF opens bin $b+1$ only because its first item did not fit into bin $b$: consecutive pairs exceed $c$, and adding up gives the guarantee $2$.
In bin packing, a solution with $k$ bins and the half-full property (at most one bin with weight at most $c/2$) satisfies $\sum_j w_j>(k-1)\frac c2$. With $\sum_j w_j=23$ and $c=10$, how many bins can an Any Fit algorithm use at most?
$5$
$6$
$4$
$3$
Explanation. $23>(k-1)\cdot 5$ gives $k-1\le 4$, i.e., $k\le 5$. The weight bound gives $z(I)\ge\lceil 2.3\rceil=3$, consistent with the guarantee $k\le 2z(I)$.
First Fit, Best Fit and Worst Fit are all Any Fit algorithms for bin packing, so they have the half-full property and ratio at most $2$. What does the fact that $r(WF)=2$ while $r(FF)=r(BF)=\frac{17}{10}$ teach?
Worst Fit is not an Any Fit algorithm
First Fit and Best Fit violate the half-full property
The guarantees depend only on the order of the items
The Any Fit condition alone gives only the guarantee $2$: the bin selection rule matters
Explanation. The half-full property holds for every Any Fit rule and gives $2$; going down to $\frac{17}{10}$ requires knowing which bin is chosen, the first or the fullest.
Next Fit (NF) for bin packing has worst-case ratio $r(NF)=2$. Which kind of instance approaches it?
Items sorted by non-increasing weight
Items all of weight $1$, with large $c$
Items alternating weight about $c/2$ and very small weight: NF closes every bin half empty
Items all of weight $c$: every algorithm uses one bin per item
Explanation. With weights $\frac c2,\epsilon,\frac c2,\epsilon,\dots$ NF puts one large and one small item into every bin, while the optimum pairs the large items and gathers the small ones in few bins.
In the chapter on bin packing approximation a solution is a partition of the items into packing patterns, $z(I)$ is the minimum number of bins and $\mathscr{A}(I)$ the number used by a heuristic. Which performance ratio is used and what is its minimum value?
$\mathscr{A}(I)/z(I)\le1$
$\mathscr{A}(I)/z(I)\ge1$
$z(I)/\mathscr{A}(I)\ge1$
$\mathscr{A}(I)-z(I)\ge1$
Explanation. Bin packing is a minimization problem: the heuristic solution uses at least $z(I)$ bins, and the ratio has the heuristic in the numerator.
A bin packing algorithm is Any Fit if it opens a new bin only when the item fits in no open bin. Which of Next Fit, First Fit, Best Fit and Worst Fit is NOT Any Fit, and why?
Next Fit: it closes the bin as soon as an item does not fit, even if the item would fit in an earlier one
First Fit: it chooses the first bin
Best Fit: it chooses the fullest bin
Worst Fit: it chooses the emptiest bin
Explanation. FF, BF and WF differ only in the choice rule among the bins where the item fits, which Any Fit leaves free; NF keeps a single bin open.
In a solution produced by an Any Fit algorithm for bin packing, any two bins have together weight greater than $c$. Why?
Because every bin is more than half full by construction of the choice rule
Because the items are sorted by weight
It is not true for Worst Fit
The first item of the bin opened later did not fit into the other one, whose load never decreased
Explanation. Only the Any Fit condition is used, not the choice rule: this is why the property, and the guarantee $\mathscr{A}(I)\le2z(I)$, also holds for WF.
Bin packing with $c=10$ and items, in order, of weight $(6,5,4,3)$. How many bins does First Fit use and with which loads?
$2$, with loads $(9,9)$
$4$, with loads $(6,5,4,3)$
$2$, with loads $(10,8)$
$3$, with loads $(6,9,3)$
Explanation. $6$ opens bin $1$; $5$ does not fit ($11$) and opens bin $2$; $4$ fits into bin $1$ ($10$); $3$ does not fit into bin $1$ and fits into bin $2$ ($8$).
Bin packing with $c=10$: the open bins have loads $(5,8,3)$ and an item of weight $2$ arrives. Into which bin does Best Fit put it (minimum residual capacity among those where it fits)?
Into a new bin
Into bin $2$, which becomes full
Into bin $1$, the first where it fits
Into bin $3$, the emptiest
Explanation. Residuals $5,2,7$: the item fits everywhere, and the minimum residual is $2$, in bin $2$. First Fit would put it into bin $1$, Worst Fit into bin $3$.
Worst Fit for bin packing puts every item into the open bin with maximum residual capacity among those where it fits. Which worst-case guarantee does it have, compared to First Fit?
Ratio $2$, tight; First Fit has asymptotic ratio $\frac{17}{10}$
Ratio $\frac{17}{10}$, as First Fit
Ratio $\frac32$
No constant guarantee
Explanation. WF is Any Fit, hence $WF(I)\le2z(I)$, and there are instances with $WF(I_n)/z(I_n)\to2$; FF and BF only reach $\frac{17}{10}$.
For Worst Fit there are instances $I_n$ with $WF(I_n)/z(I_n)\to2$. What does it mean for the class of Any Fit algorithms, which guarantee $\mathscr{A}(I)\le2z(I)$?
That no Any Fit algorithm has ratio below $2$
That Worst Fit is not Any Fit
That First Fit has ratio $2$
The bound $2$ cannot be improved for the class as a whole; better choice rules can improve it for single algorithms
Explanation. The Any Fit condition alone gives $2$; FF and BF, with better choice rules, go down to $\frac{17}{10}$.
First Fit and Best Fit for bin packing satisfy $\mathscr{A}(I)\le\frac{17}{10}z(I)$ (Dósa and Sgall; the first version, from 1974, had a $+2$), and the factor $\frac{17}{10}$ is tight. On an instance with $z(I)=100$, at most how many bins can First Fit use according to this guarantee?
$200$
$150$
$170$
$172$
Explanation. $\frac{17}{10}\cdot100=170$; $172$ is the weaker 1974 bound. The bound $2z(I)=200$ of the Any Fit condition alone is weaker still.
The Any Fit condition alone guarantees the half-full property and hence $\mathscr{A}(I)\le2z(I)$. What happens to the guarantee if the Any Fit condition is dropped, as Next Fit does?
Next Fit has guarantee $\frac{17}{10}$
Next Fit still keeps $NF(I)\le2z(I)$, because two consecutive bins together exceed $c$
Next Fit loses every constant guarantee
Next Fit becomes optimal
Explanation. For NF the property holds only for pairs of consecutive bins, but it is enough for the guarantee $2$; what the Any Fit condition adds is the property for every pair.
Bin packing with capacity $c=10$. Next Fit (NF) scans the items in the given order, keeps a single bin open and, if the item does not fit, closes it and opens a new one. With weights, in order, $(4,7,2,5,6,3)$, which vector $bin$ ($bin_i$ = bin of item $i$) does NF return?
$(1,2,2,3,4,5)$
$(1,2,2,3,4,4)$
$(1,2,1,3,4,1)$
$(1,2,2,3,3,4)$
Explanation. $4$ in bin $1$; $7$ does not fit (residual $6$): bin $2$, then $2$ (residual $1$); $5$ opens bin $3$; $6$ does not fit (residual $5$): bin $4$, where $3$ also fits. $(1,2,1,3,4,1)$ is First Fit, which goes back to earlier bins.
In bin packing ($c=10$), an algorithm returns $bin=(1,1,2,3,3,3)$ ($bin_i$ = bin of item $i$) with weights $w=(5,4,8,3,3,2)$. The load pattern $P_b$ is the set of items with $bin_i=b$. What are $P_3$ and its total weight?
$P_3=\{4,5,6\}$, weight $8$
$P_3=\{3\}$, weight $8$
$P_3=\{3,4,5\}$, weight $14$
$P_3=\{6\}$, weight $2$
Explanation. $bin_4=bin_5=bin_6=3$, hence $P_3=\{4,5,6\}$ with weight $3+3+2=8$. $\{3\}$ confuses the bin index with the item index: item $3$ is in bin $2$.
In the pseudocode of Next Fit for bin packing, $rc$ is the residual capacity of the open bin and a new bin is opened if $w[i]>rc$. What does NF do when an item arrives whose weight $w[i]$ equals $rc$ exactly?
It opens a new bin and puts it there
It puts it into the first closed bin where it fits
It discards it and moves to the next item
It puts it into the open bin, which is left with $rc=0$
Explanation. The condition for opening a bin is $w[i]>rc$, strict: with $w[i]=rc$ the item fits and fills the bin exactly. NF never goes back to closed bins.
First Fit (FF) is run on six items of weight $5,7,3,4,2,6$, scanned in this order, with bins of capacity $10$: every item goes into the first bin, in order of opening, that can take it, otherwise into a new one. What is the result?
$4$, with loads $(5,10,6,6)$
$4$, with loads $(10,7,4,6)$
$3$, with loads $(10,7,10)$
$3$, with loads $(9,10,8)$
Explanation. $5\to1$, $7\to2$, $3\to1$ (residual $5$), $4\to3$ (residuals $2$ and $3$), $2\to1$, $6\to3$ (residual $6$). $(9,10,8)$ is Best Fit, $(5,10,6,6)$ is Next Fit; $(10,7,4,6)$ forgets to check bin $3$ for the item $6$.
In bin packing an Any Fit algorithm opens a new bin only if the item fits in none of the open ones, and leaves free the choice among the bins where it fits. What does First Fit fix?
Always the last bin opened so far
The first bin (in order of opening) where it fits
The order of the items, scanned by non-increasing weight
The bin with minimum residual capacity
Explanation. FF scans the items in the given order and chooses the first suitable bin. Sorting the weights in non-increasing order is something else (First Fit Decreasing); the minimum residual is Best Fit; the last bin is the idea of Next Fit.
Bin packing with $c=10$ and weights, in order, $(5,7,3,3,4)$. Best Fit (BF) puts every item, among the open bins where it fits, into the one with minimum residual capacity (ties: the first opened), and opens a new bin only if it fits in none. Which vector $bin$ ($bin_i$ = bin of item $i$) does it return?
$(1,2,2,1,3)$
$(1,2,1,2,3)$
$(1,2,2,3,3)$
$(1,2,1,3,3)$
Explanation. The first $3$ fits in bins $1$ (residual $5$) and $2$ (residual $3$): BF chooses bin $2$, which becomes full. The second $3$ goes into bin $1$ (residual $2$), and $4$ opens bin $3$. $(1,2,1,2,3)$ is First Fit (and here also Worst Fit), $(1,2,2,3,3)$ is Next Fit.
Bin packing with $c=10$: four open bins have residual capacities $(4,2,4,7)$ and an item of weight $3$ arrives. Best Fit chooses, among the bins where the item fits, the one with minimum residual capacity, and on ties the first opened. Where does the item go?
Into bin $2$
Into bin $3$
Into bin $4$
Into bin $1$
Explanation. The item fits in bins $1$, $3$, $4$ (residuals $4,4,7$); the minimum $4$ is tied between $1$ and $3$, and the first opened wins. Bin $2$ has the smallest residual but the item does not fit; bin $4$ is the choice of Worst Fit.
Bin packing with $c=10$ and weights, in order, $(6,5,3,4,2)$. First Fit (FF) uses the first bin where the item fits; Worst Fit (WF) the one with maximum residual capacity among those where it fits; both open a bin only if the item fits in none. How many bins do they use?
Both $2$
Both $3$
FF $3$, WF $2$
FF $2$, WF $3$
Explanation. After $6$ and $5$ the residuals are $(4,5)$. FF puts $3$ into the first ($\to(1,5)$), then $4$ into the second ($\to(1,1)$) and opens a third for $2$. WF puts $3$ into the second ($\to(4,2)$), then $4$ into the first and $2$ into the second: $(10,10)$. A worse guarantee ($r(WF)=2$) does not prevent winning on a single instance.
In bin packing, Worst Fit puts every item, among the open bins where it fits, into the one with maximum residual capacity. What is the idea of this rule?
Scan the heaviest items before the others
Avoid residuals too small for future items
Fill every open bin as much as possible
Close every bin as soon as an item does not fit
Explanation. By putting the item into the emptiest bin, WF spreads the free space and avoids unusable residuals. Filling as much as possible is the opposite idea, of Best Fit; closing bins is Next Fit; the order by weight is not part of WF.
Bin packing with $c=10$ and weights, in order, $(2,9,2,9,2,9)$. Next Fit keeps a single bin open. A solution has the half-full property if at most one bin has load $\le c/2$. How many bins does NF use, and does its solution have the property?
$6$, and it does not: three bins have load $2$
$6$, and it does: two consecutive bins exceed $10$
$4$, and it does: a single bin has load $\le5$
$3$, and it does: every bin weighs $11$
Explanation. No item fits together with the previous one ($2+9=11>10$), so NF opens $6$ bins, and three have load $2\le5$. Two consecutive bins exceeding $c$ is a different property. $4$ bins are those of First Fit, $(6,9,9,9)$.
In bin packing with capacity $c$, a solution has the half-full property if at most one bin has total weight at most $c/2$. Which condition is equivalent?
For every pair of bins, together they weigh more than $c$
Every bin, without exception, weighs more than $c/2$
At most one bin is not completely filled
For every pair of bins, at least one weighs more than $c/2$
Explanation. If two bins both weighed at most $c/2$ the property would fail, and conversely. «Together more than $c$» is the stronger property of Any Fit solutions; «every bin» does not allow the exception.
In bin packing with $c=10$, a solution has two bins with loads $6$ and $1$. Does it have the half-full property (at most one bin with load $\le c/2$)? Can the two bins be merged into one?
No, it does not; and yes, they can be merged
No, it does not; and they cannot be merged
Yes, it does; and yes, they can be merged
Yes, it does; hence they cannot be merged
Explanation. Only the bin with load $1$ is $\le5$: the property holds; but $6+1=7\le10$, so they merge. The property does not prevent merging: it serves to prove the guarantee $2$.
In bin packing, for a solution with $k$ bins and the half-full property one gets $(k-1)\frac c2<\sum_iw_i\le z(I)\,c$ ($z(I)$ = optimal number of bins). How does one conclude $k\le2z(I)$?
From $\sum_iw_i\le c$, which holds for every instance
From $k-1<2z(I)$, since $k$ and $z(I)$ are integers
From $k<2z(I)$, dividing by $\frac c2$
From $z(I)\ge2$, which holds for every instance
Explanation. Dividing by $\frac c2$ gives $k-1<2z(I)$, i.e. $k<2z(I)+1$; integrality gives $k\le2z(I)$. One does not get $k<2z(I)$ directly.
In bin packing, does the proposition «if an algorithm always produces solutions with the half-full property, then $\mathscr{A}(I)\le2z(I)$» apply to an algorithm that is NOT Any Fit but always produces solutions with that property?
Yes: the proof uses only the property of the solution
No: the proof uses the Any Fit condition
Yes, but only in the limit $z(I)\to\infty$
No: the items must also be sorted by weight
Explanation. The proof counts the bins filled beyond half and uses $\sum_iw_i\le z(I)c$: it does not look at how the solution was built. The Any Fit condition only serves to guarantee the property.
In bin packing, the instance $I_n$ has $c=n$ and $n$ items (with $n$ a multiple of $4$) of alternating weight $\frac n2$ (odd indices) and $2$ (even indices). Next Fit uses $\frac n2$ bins and the optimum is $\frac n4+1$. With $n=20$, what are $NF$, $z$ and the ratio?
$NF=10$, $z=5$, ratio $2$
$NF=20$, $z=6$, ratio $\frac{10}3$
$NF=10$, $z=10$, ratio $1$
$NF=10$, $z=6$, ratio $\frac53$
Explanation. $NF=\frac{20}2=10$ and $z=\frac{20}4+1=6$: the $10$ large items two by two and all small ones ($10\cdot2=20$) in one bin. $z=5$ forgets the bin of the small items. The ratio tends to $2$ only for $n\to\infty$.
In bin packing, two consecutive bins of Next Fit together weigh more than $c$; summing over disjoint pairs gives $z(I)\ge\lfloor k/2\rfloor+1$, where $k$ is the number of NF bins and $z(I)$ the optimum. If NF uses $k=7$ bins, what is the least value of $z(I)$?
$7$
$2$
$4$
$3$
Explanation. $\lfloor7/2\rfloor+1=4$: the $3$ pairs weigh more than $3c$, so more than $3$ bins are needed. $3$ forgets the $+1$; indeed $k\le2z(I)-1=7$.
In bin packing, the instance $I_n$ has $c=n$ and alternating weights $\frac n2,2,\frac n2,2,\dots$; Worst Fit (bin with maximum residual among those where the item fits) uses $\frac n2$ bins on it. Why does WF never put two items of weight $\frac n2$ into the same bin?
Because the small items all end up in the first opened bin
Every small item goes into the new bin, left with residual $\frac n2-2$
Because two items of weight $\frac n2$ together exceed the capacity $c=n$
Because Worst Fit does not satisfy the Any Fit condition
Explanation. The newly opened bin has the maximum residual $\frac n2$, so it receives the small item and drops to $\frac n2-2<\frac n2$. Two large items would fit together ($\frac n2+\frac n2=n$): it is the WF rule that prevents it.
In bin packing Next Fit and Worst Fit have the same worst-case ratio, $r(NF)=r(WF)=2$. Are they therefore equivalent?
No: only NF can leave many bins half full or less
Yes: the same ratio means the same solutions
No: WF uses fewer bins than NF on every instance
Yes: both keep a single bin open at a time
Explanation. WF is Any Fit, hence it has the half-full property; NF can leave many bins with load $\le c/2$. The worst-case ratio looks only at the worst instance; «always fewer» is too strong.
For First Fit and Best Fit in bin packing, Johnson, Demers, Ullman, Garey and Graham (1974) proved $\mathscr{A}(I)\le\frac{17}{10}z(I)+2$; Dósa and Sgall (2013, 2014) proved $\mathscr{A}(I)\le\frac{17}{10}z(I)$. What changes between the two?
The factor went down from $2$ to $\frac{17}{10}$
The result now also holds for Worst Fit
The result now holds only with sorted items
The additive constant $+2$ was removed
Explanation. The factor $\frac{17}{10}$ was already there in 1974; the second result removes the $+2$, so it also holds for small $z(I)$. Worst Fit has $r(WF)=2$.
In bin packing an Any Fit algorithm opens a new bin only if the item fits in none of the open ones. It is known that no Any Fit algorithm has worst-case ratio below $\frac{17}{10}$, and every Any Fit has ratio at most $2$. A new Any Fit chooses the bin at random: what is known about its ratio?
It is at most $\frac{17}{10}$, like First Fit
Nothing: the Any Fit condition gives no guarantee
It lies between $\frac{17}{10}$ and $2$
It is exactly $2$, like Worst Fit
Explanation. The Any Fit condition gives the half-full property, hence at most $2$; Johnson's lower bound $\frac{17}{10}$ holds for the whole class. The extremes are attained by FF/BF and by WF.
In bin packing First Fit and Best Fit have worst-case ratio $\frac{17}{10}$, Worst Fit $2$; all three scan the items in the given order and are Any Fit (they open a bin only if the item fits nowhere else). What explains the whole gap between $\frac{17}{10}$ and $2$?
The additive constant $+2$ of the First Fit bound
The rule for choosing among the bins where the item fits
The order in which the items are scanned
The number of bins kept open at the same time
Explanation. The three algorithms have the same order and keep all bins open; they differ only in the choice rule (first, minimum residual, maximum residual).
In the vertex coloring problem (VCP) on a graph $G$ with $n$ vertices the number of colors is minimized. If $P\neq NP$, which statement on the approximation of the VCP is correct?
It has a $(\Delta(G)+1)$-approximation for every graph, $DSATUR$
It has no polynomial $\alpha$-approximation for any constant $\alpha\ge 1$
It has a polynomial $\frac43$-approximation, but none below $\frac43$
It has a polynomial $2$-approximation, the greedy coloring
Explanation. The $\frac43$ theorem excludes the ratios below $\frac43$; Zuckerman's result also excludes $n^{1-\varepsilon}$, hence any constant. The bound $GC(I)\le\Delta(G)+1$ does not compare with $\chi(G)$.
In vertex coloring, let $\chi(G)$ be the chromatic number. The proof that no polynomial algorithm $\mathscr{A}$ has ratio $\mathscr{A}(I)/\chi(G)$ smaller than $\frac43$ on every graph (if $P\neq NP$) uses:
that deciding whether $\chi(G)\le 3$ is NP-complete, and that the number of colors is an integer
that deciding whether $\chi(G)\le 2$ is NP-complete, and that the number of colors is an integer
that deciding whether $\chi(G)\le 4$ is NP-complete, and that planar graphs have $\chi(G)\le 4$
that the greedy coloring uses at most $\Delta(G)+1$ colors, and that the number of colors is an integer
Explanation. With ratio $<\frac43$, a graph with $\chi\le 3$ would get at most $3$ colors and one with $\chi\ge 4$ at least $4$: 3-colorability would be decided in polynomial time. With $2$ colors the argument says nothing, because that test is easy.
In an interval graph every vertex $v$ is an interval $[a_v,b_v]$ of the line, and two vertices are adjacent if the intervals intersect. With which vertex order is the greedy coloring (smallest free color) optimal?
By non-increasing right endpoint $b_v$
By non-increasing length $b_v-a_v$
With any vertex order
By non-decreasing left endpoint $a_v$
Explanation. With the intervals sorted by left endpoint, when an interval receives color $q$ there are $q$ intervals intersecting at $a_v$: the coloring uses $\omega(G)$ colors, hence it is optimal.
A graph $G$ with $n$ vertices and $m$ edges is bipartite if and only if its chromatic number is $\chi(G)\le 2$. How much does it cost to decide whether $G$ is bipartite and, if so, to find a coloring with $2$ colors?
$O(2^n)$: the problem is NP-complete
$O(nm)$, with a shortest path from every vertex
$O(n+m)$, with a breadth-first search
$O(n^3)$, with linear programming
Explanation. A breadth-first search colors alternating two colors and finds an odd cycle if the graph is not bipartite. Already with $3$ colors the problem is NP-complete.
The proof that no polynomial algorithm for coloring has ratio $\mathscr{A}(I)/\chi(G)<\frac43$ on every graph (if $P\neq NP$) uses a hypothetical algorithm with ratio $<\frac43$. What would it do on a graph with $\chi(G)=3$?
It would use $2$ colors, contradicting $\chi(G)=3$
It would not terminate, because the problem is NP-hard
It would use fewer than $4$ colors, i.e., $3$: it would decide in polynomial time whether $\chi(G)\le 3$
It would use exactly $4$ colors, which says nothing
Explanation. With ratio $<\frac43$ and $\chi(G)=3$ the number of colors is $<4$, hence $3$; if $\chi(G)\ge 4$ it is at least $4$. 3-colorability, NP-complete, would be decided: only the integrality of $\chi$ is used.
The same argument excluding ratios below $\frac43$ for coloring (distinguishing $3$ colors from $4$) does not exclude ratios below $\frac32$ by distinguishing $2$ colors from $3$. Why?
Because with $2$ colors the greedy coloring is always optimal
Deciding whether $\chi(G)\le 2$ is polynomial (bipartite graphs), so no contradiction arises
Because no graph has $\chi(G)=2$
Because $\frac32>\frac43$
Explanation. The argument needs an NP-complete decision problem; 2-colorability is decided by breadth-first search in $O(n+m)$.
For vertex coloring, giving every vertex a different color is always feasible. Which ratio does this trivial algorithm guarantee, and what does Zuckerman's theorem say (if $P\neq NP$)?
Ratio at most $n$; no polynomial algorithm guarantees $n^{1-\varepsilon}$ for any $\varepsilon>0$
Ratio at most $2$; no polynomial algorithm guarantees less than $2$
Ratio at most $\Delta+1$; no polynomial algorithm guarantees less than $\frac43$
Ratio at most $\log n$; an algorithm with constant ratio exists
Explanation. $n$ colors against $\chi(G)\ge 1$ give ratio at most $n$. The theorem says one cannot do substantially better: in particular the problem has no constant ratio.
Every planar graph with $n\ge 3$ vertices has at most $3n-6$ edges and hence a vertex of degree at most $5$. How many edges does a planar graph with $n=10$ vertices have at most?
$30$
$45$
$27$
$24$
Explanation. $3\cdot 10-6=24$. The sum of the degrees is at most $48<6n$, so some vertex has degree at most $5$: it is the key step of the five color theorem.
On planar graphs, the algorithm $PL$ colors with at most $5$ colors in polynomial time (Heawood's theorem). Which guarantee does it have with respect to the chromatic number $\chi(G)$, if the graph has at least one edge?
None: planar graphs are as hard as all others
Additive: $PL(I)-\chi(G)\le 0$, i.e., $PL$ is exact
Additive: $PL(I)-\chi(G)\le 2$, recognizing separately the graphs with $\chi(G)\le 2$
Relative: $PL(I)/\chi(G)\le\frac43$
Explanation. With at least one edge $\chi(G)\ge 2$; bipartite graphs are recognized and colored in $O(n+m)$, and on the others $\chi(G)\ge 3$, hence $5-\chi(G)\le 2$. With the four color theorem the error drops to $1$.
The greedy coloring uses at most $\Delta(G)+1$ colors, with $\Delta(G)$ the maximum degree. On graphs of maximum degree at most $3$ with at least one edge, which ratio with respect to $\chi(G)$ does it guarantee?
Exactly $1$: on these graphs it is optimal
At most $2$, because it uses at most $4$ colors and $\chi(G)\ge 2$
At most $4$, because it uses at most $4$ colors and $\chi(G)\ge 1$
At most $\frac43$, because $\chi(G)\ge 3$
Explanation. $\frac{\Delta+1}{\chi(G)}\le\frac42=2$: on bounded-degree graphs the greedy coloring has a constant ratio, while on general graphs no polynomial algorithm has one.
Interval graph with vertices $[1,4]$, $[2,5]$, $[3,6]$, $[7,8]$ (two vertices adjacent if the intervals intersect). The greedy coloring with the vertices by non-decreasing left endpoint uses $\omega(G)$ colors. How many colors are needed?
$3$
$4$
$2$
$1$
Explanation. The first three intervals overlap at the point $3.5$ and form a clique, so $\omega=3$; $[7,8]$ intersects none and reuses color $1$. The greedy gives $3=\chi(G)$.
Zuckerman's theorem excludes, if $P\neq NP$, the ratios $n^{1-\varepsilon}$ for coloring. Why does it also exclude every constant ratio $\alpha$?
Because every constant is below $\frac43$
Because constant ratios hold only on planar graphs
It does not: $\alpha$-approximations with large $\alpha$ exist
On graphs with large enough $n$, $\alpha<n^{1-\varepsilon}$: an $\alpha$-approximation would have ratio below the forbidden threshold
Explanation. For fixed $\varepsilon$, when $n>\alpha^{1/(1-\varepsilon)}$ we have $\alpha<n^{1-\varepsilon}$; the small graphs, finitely many, are solved optimally in constant time.
In the chapter on the limits of coloring approximation, $\mathscr{A}(I)$ is the number of colors of an algorithm and $\chi(G)$ the chromatic number. Which ratio is studied?
$\omega(G)/\mathscr{A}(I)$
$\mathscr{A}(I)/\chi(G)\ge1$
$\chi(G)/\mathscr{A}(I)\ge1$
$\mathscr{A}(I)-\chi(G)$, always $\le1$
Explanation. Coloring is a minimization problem: the algorithm uses at least $\chi(G)$ colors, and the ratio has the algorithm in the numerator.
The VCP is not approximable in general, but on some graph classes it is solved exactly in polynomial time. Which of these is one of those classes, and with which method?
Complete graphs: $2$ colors are needed
Graphs with a triangle: $3$ colors suffice
All graphs with $n\le100$
Bipartite graphs: a breadth-first search finds a $2$-coloring or an odd cycle
Explanation. A graph with at least one edge is $2$-colorable if and only if it has no odd cycle, and the search decides it in linear time. Complete graphs need $n$ colors.
Vertex coloring (VCP, minimum number of colors $\chi(G)$) is not approximable in general. On which of the classes bipartite, bounded maximum degree, planar, interval graphs is it solved exactly in polynomial time, and on which is there only a guarantee?
Exact on bounded degree and interval; guarantee on bipartite and planar
Exact on bipartite and interval; guarantee on bounded degree and planar
Exact on all four classes
Exact on bipartite and planar; guarantee on interval and bounded degree
Explanation. Bipartite: breadth-first search; interval: greedy by left endpoint, optimal. Bounded degree: $\Delta+1$ colors; planar: additive error at most $2$ (or $1$ with four colors). Deciding $\chi\le3$ stays NP-complete on planar graphs.
If $P\neq NP$ no polynomial algorithm for vertex coloring has ratio $\mathscr{A}(I)/\chi(G)<\frac43$ on all graphs. Why does this not prevent an exact polynomial algorithm on bipartite graphs?
The theorem is about all graphs; the hard ones are not bipartite
Because on bipartite graphs the chromatic number is $\chi(G)=1$
Because the theorem holds only under $P=NP$
Because on bipartite graphs coloring becomes a maximization problem
Explanation. A bound on the worst case over all graphs does not hold on a restricted class: the reductions use graphs with $\chi\ge3$. A bipartite graph with an edge has $\chi=2$.
To decide whether $\chi(G)\le2$ one runs a breadth-first search from vertex $1$ and colors every vertex by the parity of its level $\ell(v)$. Graph with edges $\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,5\},\{4,6\},\{5,6\}$: which edge joins two levels of equal parity, and what does it certify?
$\{4,6\}$: a closed walk of length $6$, hence $\chi\ge3$
None: the graph is bipartite and $\chi=2$
$\{5,6\}$: a closed walk of length $4$, hence $\chi\ge3$
$\{4,5\}$: a closed walk of length $5$, hence $\chi\ge3$
Explanation. Levels: $1\to0$; $2,3\to1$; $4,5\to2$; $6\to3$. Only $\{4,5\}$ joins two even levels: with the tree paths it gives $\ell(4)+\ell(5)+1=5$, the cycle $1,2,4,5,3$. The edges $\{4,6\}$ and $\{5,6\}$ join levels of different parity.
A graph $G$ is bipartite if $\chi(G)\le2$, i.e. if its vertices split into two stable sets; by König this happens if and only if $G$ has no cycles of odd length. What is $\chi(G)$ for a graph with at least one edge and no odd cycles?
Exactly $3$
It depends on the maximum degree $\Delta(G)$
Exactly $2$
$1$ or $2$, depending on the graph
Explanation. Without odd cycles $\chi\le2$; an edge requires two colors, hence $\chi=2$. $\chi=1$ holds only for graphs without edges.
The greedy coloring $GC$ scans the vertices in a given order and gives each one the smallest color not used by its already colored neighbors; it uses at most $\Delta(G)+1$ colors ($\Delta$ = maximum degree). On the star with one center and $9$ leaves, how many colors does $GC$ use and what is $\Delta+1$?
$2$ colors with every order; $\Delta+1=9$
$2$ colors with every order; $\Delta+1=10$
$10$ colors with every order; $\Delta+1=10$
From $2$ to $10$ colors depending on the order; $\Delta+1=10$
Explanation. The leaves are pairwise non-adjacent: they all take the same color and the center the other one, in any order. The bound $\Delta+1$ does not compare $GC$ with $\chi$: here it is $10$ against $\chi=2$.
Greedy coloring uses at most $\Delta(G)+1$ colors on every graph ($\Delta$ = maximum degree). On which connected graphs is the bound attained with any order, and what does Brooks' theorem say about the others?
Complete graphs and odd cycles; for the others $\chi(G)\le\Delta(G)$
Trees and even cycles; for the others $\chi(G)\le\Delta(G)-1$
Planar graphs; for the others $\chi(G)\le4$
Bipartite graphs; for the others $\chi(G)=\Delta(G)+1$
Explanation. $K_n$ has $\chi=n=\Delta+1$ and an odd cycle has $\chi=3=\Delta+1$. Brooks (1941): a connected graph that is neither complete nor an odd cycle has $\chi\le\Delta$, and such a coloring is found in linear time.
On planar graphs the four-color algorithm gives a coloring with additive error $\mathscr{A}(I)-\chi(G)\le1$. Deciding whether a planar graph has $\chi(G)\le3$ is NP-complete. What follows, if $P\neq NP$?
On planar graphs there is an exact algorithm, but not polynomial in $n$
The minimum possible additive error on planar graphs is $2$
On planar graphs no algorithm has a constant ratio
The error $1$ cannot drop to $0$ and $\frac43$ is the best ratio on planar graphs
Explanation. An exact algorithm would decide $\chi\le3$; and a ratio $<\frac43$ would distinguish $3$ colors from $4$. The four-color theorem still gives the ratio $\frac43$.
Heawood's theorem (every planar graph can be colored with $5$ colors) is proved by induction: remove a vertex $v$, color $G-v$ and put $v$ back. Why is $v$ chosen of degree at most $5$?
Because the graph $G-v$ then becomes bipartite
Because every planar graph has maximum degree at most $5$
Its neighbors use at most $5$ colors; if all, a swap frees one
Because the vertices of degree at most $5$ form a stable set
Explanation. It exists by the lemma $m\le3n-6$. With at most $4$ colors among the neighbors the fifth is free; with $5$, swapping two colors in a component (Kempe chain) frees one. The maximum degree of a planar graph can be large (a star).
In an interval graph every vertex $v$ is a closed interval $[a_v,b_v]$ and two vertices are adjacent if the intervals intersect. Greedy coloring (each vertex gets the smallest color not used by its already colored neighbors) is optimal if it scans the vertices in which order?
By non-increasing number of intersections (degree)
By non-decreasing left endpoint $a_v$
In any order: on interval graphs it is always optimal
By non-increasing length $b_v-a_v$
Explanation. With the order by $a_v$, the already colored neighbors of $v$ all contain the point $a_v$: with $v$ they form a clique, so the colors are at most $\omega(G)$. With other orders greedy can use one more color.
Interval graph with $[1,4],[2,6],[3,5],[5,8],[7,10],[9,12]$ (vertices $1,\dots,6$, adjacent if the intervals intersect). Greedy coloring uses $3$ colors in the order $1,2,3,4,5,6$ and $4$ colors in the order $1,2,3,5,4,6$. What does the example show?
Optimality is guaranteed only with the left-endpoint order
The chromatic number of this graph is $\chi(G)=4$
The given graph is not an interval graph
Greedy coloring is never optimal on these graphs
Explanation. $\{1,2,3\}$ contains the point $3$, hence $\omega=\chi=3$: the left-endpoint order is optimal, the other uses one more color (vertex $4$ has neighbors $2,3,5$ with colors $1,2,3$).
Which NP-complete decision problem is used to prove that no polynomial algorithm for the VCP always has ratio below $\frac43$ (if $P\neq NP$)?
Deciding whether $\chi(G)\le3$
Deciding whether $\chi(G)\le2$
Deciding whether $G$ is planar
Deciding whether $\omega(G)\le2$
Explanation. With ratio $<\frac43$, on a graph with $\chi(G)=3$ the algorithm would use at most $3$ colors and on $\chi(G)\ge4$ at least $4$: it would decide $3$-colorability.
Zuckerman's result (2007) states that, if $P\neq NP$, for every $\varepsilon>0$ no polynomial algorithm for the VCP always has ratio at most which quantity?
$1+\varepsilon$
$\log n$
$\frac43-\varepsilon$
$n^{1-\varepsilon}$
Explanation. The trivial ratio is $n$ (one color per vertex); Zuckerman shows that one cannot do much better: not even $n^{1-\varepsilon}$.
With which complexity can one decide whether $\chi(G)\le2$ (and find a $2$-coloring if it exists)?
It is not known in polynomial time
$O(n+m)$, with a breadth-first search
$O(2^n)$, trying all partitions
$O(n^3)$, with an ILP model
Explanation. Breadth-first search colors the levels alternating the two colors; an edge between two vertices of the same color proves that $G$ is not bipartite.
On an interval graph, with which order of the vertices is the greedy coloring optimal?
By decreasing degree of the vertices
With any order of the vertices
By non-decreasing left endpoint $a_v$
By decreasing right endpoint $b_v$
Explanation. With the order by $a_v$, when $v$ is colored all its colored neighbours contain the point $a_v$: together with $v$ they form a clique, so $\omega(G)$ colors suffice.
Which guarantee does $PL$ have on planar graphs if the five color algorithm is replaced by the four color one?
It becomes exact
Ratio at most $\frac43$, not additive
Additive error at most $1$
Additive error at most $2$
Explanation. On non-bipartite graphs $\chi(G)\ge3$ and at most $4$ colors are used: error $\le1$. It is still not exact, since deciding $\chi(G)\le3$ is hard.
In the strong product $G\boxtimes H$ the vertices are the pairs $(u,x)$, and two distinct pairs are adjacent if each component is equal or adjacent in its own graph. With $\omega$ the cardinality of a maximum clique, which statement is correct?
Explanation. The product of two cliques is a clique of the strong product, and a clique of the product has at most $|p(K)|\cdot\max_u|K_u|$ vertices: the clique number multiplies.
In the maximum clique problem (MCP), with $\omega(G)$ the cardinality of a maximum clique and $G\boxtimes G$ the strong product of $G$ with itself, the theorem «a constant $\alpha$-approximation for the MCP would give a $\beta$-approximation for every $\beta>1$» is proved using:
$\omega(G\boxtimes G)=\omega(G)^2$; from a clique $K$ of the product one extracts a clique of $G$ with at least $\sqrt{|K|}$ vertices; $\log n$ products
$\omega(G)=\alpha(\overline{G})$; from a stable set of $\overline{G}$ one extracts a clique of $G$; the half-full property
$\omega(G\boxtimes G)=\omega(G)^2$; from a clique $K$ of the product one extracts a clique of $G$ with at least $\sqrt{|K|}$ vertices; a constant number of products
$\omega(G\boxtimes G)=2\,\omega(G)$; from a clique $K$ of the product one extracts a clique of $G$ with at least $|K|/2$ vertices; a constant number of products
Explanation. Applying the algorithm to $G\boxtimes G$ gives ratio $\sqrt\alpha$ on $G$; repeating a constant number of times brings the ratio below any $\beta>1$. A number of products growing with $n$ would not be polynomial.
For the maximum clique problem (MCP) and the maximum stable set problem (MSSP) on a graph $G$ with $n$ vertices, with $\omega(G)$ the cardinality of a maximum clique, which statement on planar graphs is correct?
$\omega(G)\le 5$ and the MCP is solved in $O(n^5)$, while the MSSP stays NP-hard
$\omega(G)\le 4$ and the MCP is solved in $O(n^4)$, while the MSSP stays NP-hard
$\omega(G)\le 4$ and the MCP is solved in $O(n^4)$; so is the MSSP, through the complement
$\omega(G)\le 4$, but the MCP stays NP-hard like the MSSP
Explanation. A clique of a planar graph has at most $4$ vertices, so it is enough to enumerate the subsets of at most $4$ vertices. The complement of a planar graph is not planar: the easy case does not transfer to the MSSP.
A graph has $n=24$ vertices and maximum degree $\Delta(G)=5$. A stable set is maximal if no vertex can be added to it. At least how many vertices does every maximal stable set have?
$4$
$5$
$6$
$20$
Explanation. A maximal stable set $S$ has $|S|\ge\frac{n}{\Delta(G)+1}=\frac{24}{6}=4$: every vertex is in $S$ or adjacent to a vertex of $S$, and every vertex of $S$ covers at most $\Delta+1$ vertices.
In the strong product $G\boxtimes H$ the vertices are the pairs $(u,x)$ with $u$ a vertex of $G$ and $x$ of $H$. How many vertices does $G\boxtimes G$ have if $G$ has $5$ vertices, and what is its maximum clique if $\omega(G)=2$?
$25$ vertices, $\omega(G\boxtimes G)=4$
$10$ vertices, $\omega(G\boxtimes G)=4$
$25$ vertices, $\omega(G\boxtimes G)=2$
$25$ vertices, $\omega(G\boxtimes G)=8$
Explanation. The vertices are $5\cdot 5=25$, and $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$: $2\cdot 2=4$. The product is built in polynomial time.
From a clique $K$ of the strong product $G\boxtimes G$ a clique of $G$ is obtained: either the projection $p(K)$ (the first components) or the largest fibre (the second components with the same first one). If $|K|=16$, how many vertices does the obtained clique of $G$ have at least?
$8$
$16$
$2$
$4$
Explanation. $|K|\le|p(K)|\cdot\max_u|K_u|$, so the larger of the two factors is at least $\sqrt{|K|}=4$. It is the constructive step of the amplification.
In the maximum clique problem, an algorithm with ratio $\omega(G)/\mathscr{A}(I)\le\alpha$ applied to $G\boxtimes G$ gives a clique $K$ of the product, from which a clique of $G$ with at least $\sqrt{|K|}$ vertices is obtained. Which ratio follows on $G$ with $\alpha=4$?
$16$
$\frac43$
$2$
$4$
Explanation. $|K|\ge\omega(G)^2/\alpha$, so the obtained clique has at least $\omega(G)/\sqrt\alpha$ vertices: ratio $\sqrt 4=2$. Repeating the products the ratio drops below every constant larger than $1$.
In the maximum clique problem, a single vertex is always a clique. Which ratio $\omega(G)/\mathscr{A}(I)$ does the algorithm returning one vertex guarantee, and what does the Håstad–Zuckerman theorem say (if $P\neq NP$)?
At most $\sqrt n$; a PTAS exists
At most $n$; no polynomial algorithm guarantees $n^{1-\varepsilon}$ for any $\varepsilon>0$
At most $2$; no polynomial algorithm guarantees less than $2$
At most $\Delta+1$; a polynomial algorithm with ratio $\frac43$ exists
Explanation. $\omega(G)\le n$, so one vertex gives ratio at most $n$; the theorem says one cannot do substantially better, and in particular excludes every constant ratio.
In the maximum clique problem on graphs of maximum degree $\Delta$, a maximum clique is found exactly in $O(n\,2^{\Delta}\Delta^2)$ time, examining the subsets of the neighbours of every vertex. When is this time polynomial in $n$?
For every fixed $\Delta$, and even when $\Delta\le\log_2 n$
Only for $\Delta\le 3$
Never: $2^{\Delta}$ is always exponential
Only on planar graphs
Explanation. With $\Delta\le\log_2 n$ we have $2^{\Delta}\le n$, and the time is $O(n^2\log^2 n)$. A clique contains a vertex and some of its neighbours, so examining the $2^{\Delta}$ subsets of the neighbourhood is enough.
For the maximum stable set on a graph with maximum degree $\Delta(G)$, the greedy adding vertices while possible finds a maximal stable set $S$ with $|S|\ge\frac{n}{\Delta(G)+1}$. Which ratio $\alpha(G)/|S|$ does it guarantee with $\Delta(G)=3$?
At most $3$
At most $\frac43$
No constant ratio
At most $4$
Explanation. $\alpha(G)\le n$ and $|S|\ge\frac n4$ give $\alpha(G)/|S|\le 4=\Delta+1$. Every added vertex excludes at most $\Delta$ neighbours.
The maximum clique on $G$ is the maximum stable set on the complement $\overline G$, so the two problems have the same approximation limits on general graphs. Why are the easy special cases of the clique (planar graphs, bounded degree) not easy for the stable set?
Because the complement of a planar graph is still planar
Because on planar graphs $\alpha(G)=\omega(G)$
The complement of a planar or bounded-degree graph is dense: on the original class the stable set stays NP-hard
Because the maximum stable set is always polynomial
Explanation. Passing to the complement changes the class of graphs. On planar graphs the maximum stable set stays NP-hard, but it is approximable (it even has a PTAS).
In the maximum clique problem on a planar graph with $n$ vertices, why is it enough to examine the subsets of at most $4$ vertices?
Because planar graphs have at most $4n$ edges
Every planar graph has $\omega(G)\le 4$ ($K_5$ is not planar): $O(n^4)$ subsets are checked
Because every planar graph has maximum degree at most $4$
Because every planar graph is bipartite
Explanation. A clique of $5$ vertices would be a $K_5$, which is not planar; the subsets of at most $4$ vertices are $O(n^4)$ and each is checked in constant time.
In the chapter on the limits of maximum clique approximation, $\mathscr{A}(I)$ is the number of vertices of the clique returned by an algorithm and $\omega(G)$ the clique number. Which relations hold?
$\mathscr{A}(I)=\omega(G)$
$\mathscr{A}(I)\le\omega(G)$ and $\omega(G)/\mathscr{A}(I)\ge1$
$\mathscr{A}(I)\ge\omega(G)$
$\mathscr{A}(I)/\omega(G)\ge1$
Explanation. Maximum clique is a maximization problem: the optimum goes in the numerator so that the ratio is at least $1$.
The graph $G$ is the cycle $1,2,\dots,7,1$ with the chord $\{1,3\}$, with $\omega(G)=3$. The strong product $G\boxtimes G$ has $49$ vertices. What is $\omega(G\boxtimes G)$, and by which clique is it attained?
$9$, by $\{1,2,3\}\times\{1,2,3\}$
$6$, by $\{1,2,3\}\times\{1,2\}$
$3$, by $\{1,2,3\}\times\{1\}$
$49$, by all vertices
Explanation. In the strong product $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$: the product of two cliques is a clique. It is the tool that amplifies a constant approximation ratio.
In maximum clique, an $\alpha$-approximation algorithm ($\omega(G)/\mathscr{A}(I)\le\alpha$) applied to the strong product $G\boxtimes G$ gives a $\sqrt\alpha$-approximation; repeating $t$ times gives the ratio $\alpha^{1/2^t}$ on a graph with $n^{2^t}$ vertices. With $\alpha=16$, what is the minimum $t$ reaching ratio $2$?
$t=2$, on a graph with $2n^2$ vertices
$t=2$, on a graph with $n^4$ vertices
$t=1$, on a graph with $n^2$ vertices
$t=3$, on a graph with $n^8$ vertices
Explanation. $16^{1/2}=4$, $16^{1/4}=2$: $2$ steps are needed, and the graph has $n^{2^2}=n^4$ vertices. With $t=1$ the ratio is $4$; $t=3$ suffices but is not the minimum.
For maximum clique ($\omega(G)$ = maximum cardinality of a clique, $n$ vertices), the theorem of Håstad (1999) and Zuckerman (2007) excludes the ratio $\omega(G)/\mathscr{A}(I)\le n^{1-\varepsilon}$ for every $\varepsilon>0$. What distinguishes the two contributions?
The assumption: $NP\neq ZPP$ for Håstad, $P\neq NP$ for Zuckerman
The bound: $n^{1/2}$ for Håstad, $n^{1-\varepsilon}$ for Zuckerman
The problem: clique for Håstad, stable set for Zuckerman
The class: planar graphs for Håstad, all graphs for Zuckerman
Explanation. The bound $n^{1-\varepsilon}$ is the same; Håstad obtains it assuming that NP problems cannot be solved in randomized polynomial time, Zuckerman under $P\neq NP$ alone.
For maximum clique the following hold, if $P\neq NP$: (i) no polynomial algorithm has ratio $\omega(G)/\mathscr{A}(I)\le n^{1-\varepsilon}$ (Håstad, Zuckerman); (ii) a constant ratio would give every constant ratio (strong product). What follows?
The problem has a PTAS but not an FPTAS
The problem has ratio $2$ but not a PTAS
The problem has ratio $n^{1/2}$ but not a constant one
The problem has neither a constant ratio nor a PTAS
Explanation. (i) excludes every constant (for $n>\alpha^2$ one would have $\alpha<n^{1/2}$); a PTAS would in particular give a constant ratio. Also $n^{1/2}=n^{1-1/2}$ is excluded by (i).
Every planar graph with $n\ge3$ vertices has at most $3n-6$ edges. In maximum clique, why does this imply that a planar graph contains no clique with $5$ vertices?
$K_5$ has $5$ vertices of degree $4$, more than $3$
$K_5$ has more than $3\cdot5=15$ edges
$K_5$ has $10$ edges, more than $3\cdot5-6=9$
$K_5$ has no vertex of degree at most $5$
Explanation. A subgraph of a planar graph is planar, and $K_5$ violates the bound: $10>9$. Its vertices have degree $4\le5$, and $10<15$.
In maximum clique on a graph with $n$ vertices and maximum degree $\Delta$, enumerating the subsets of $N(v)$ for every vertex $v$ takes time $O(n\,2^{\Delta}\Delta^2)$. When is this time polynomial in $n$?
For every graph with $\Delta\le\sqrt n$
For fixed $\Delta$, and also for $\Delta\le\log_2n$
Only for graphs with $\Delta\le3$, like cubic ones
Never: the factor $2^{\Delta}$ stays exponential
Explanation. With $\Delta\le\log_2n$ one has $2^\Delta\le n$, and the time is $O(n^2\log^2n)$. With $\Delta=\sqrt n$ the factor $2^{\sqrt n}$ is not polynomial.
In maximum clique on bounded-degree graphs, for every vertex $v$ one examines all $2^{\deg(v)}$ subsets $S$ of $N(v)$ (neighbors of $v$) and keeps the largest $\{v\}\cup S$ that is a clique. On a graph with degrees $3,2,2,3,1,1$, how many subsets are examined in total?
$28$
$64$
$12$
$18$
Explanation. $2^3+2^2+2^2+2^3+2^1+2^1=8+4+4+8+2+2=28$. $64=2^6$ are the subsets of all vertices, $12$ the sum of the degrees.
In the strong product $G\boxtimes G$, for a clique $K$ the projection $p(K)$ (first components) and every fiber $K_u$ (second components with first component $u$) are cliques of $G$. An algorithm returns $K=\{1,2,3\}\times\{4,5\}$, with $|K|=6$. Which clique of $G$ is obtained, and why is it enough?
The fiber $\{4,5\}$: it has $2\ge\sqrt6$ vertices
$K$ itself: it is already a clique of $G$
$\{1,2,3,4,5\}$: it joins projection and fiber
$p(K)=\{1,2,3\}$: it has $3\ge\sqrt6$ vertices
Explanation. The largest among projection and fibers has at least $\sqrt{|K|}$ vertices, because the product of the two sizes is at least $|K|$: here $3\ge\sqrt6\approx2.45$, while $2<\sqrt6$. $K$ is made of pairs, not of vertices of $G$.
In the strong product $G\boxtimes H$, when are two distinct vertices $(u,x)$ and $(v,y)$ adjacent?
If $\{u,v\}\in E$ and also $\{x,y\}\in F$, no other case
If $u=v$ or $x=y$, whatever the edges are
If $\{u,v\}\in E$ or $\{x,y\}\in F$, even alone
If $u=v$ or $\{u,v\}\in E$, and $x=y$ or $\{x,y\}\in F$
Explanation. In each coordinate the two vertices must coincide or be adjacent; the second option is the tensor product, which loses the «straight» edges.
An algorithm with ratio $\alpha=4$ for the MCP, applied to $G^{\boxtimes 2}$ and brought back to $G$, which ratio does it guarantee on $G$?
$16$
$8$
$\sqrt4=2$
$4$
Explanation. On the strong square one finds a clique of size $\ge\omega(G)^2/4$, hence a clique of $G$ of size $\ge\omega(G)/\sqrt4$: the ratio becomes $\alpha^{1/k}$.
The trivial ratio $n$ for the MCP is obtained by returning what?
The vertex of minimum degree with its neighbours
A single vertex
All the vertices
A maximal stable set
Explanation. A vertex is always a clique and $\omega(G)\le n$: ratio at most $n$. Håstad and Zuckerman show that $n^{1-\varepsilon}$ cannot be reached.
For which kind of stable set $S$ does the bound $|S|\ge\frac{n}{\Delta(G)+1}$ hold?
For every stable set
Only for a maximum stable set
Only for a stable set found by breadth-first search
For every maximal stable set
Explanation. Maximality is needed: every vertex outside $S$ has a neighbour in $S$. An arbitrary stable set, for instance the empty one, does not satisfy the bound.
For the TSP (shortest tour visiting all cities), $DT$ is the double tree algorithm and $CH$ Christofides' algorithm; the TSP is metric if the triangle inequality holds. If $P\neq NP$, which statement is correct?
The general TSP has no constant approximation; on the metric TSP $DT$ has ratio $2$ and $CH$ ratio $\frac32$
The general TSP has no constant approximation; on the metric TSP $DT$ has ratio $\frac32$ and $CH$ ratio $2$
The general TSP has a $2$-approximation, $DT$; on the metric TSP $CH$ has ratio $\frac32$
The general TSP has no constant approximation; on the metric TSP the nearest neighbour has ratio $\frac32$
Explanation. A constant guarantee on the general TSP would decide the Hamiltonian cycle problem; with the triangle inequality $DT$ and $CH$ have ratios $2$ and $\frac32$, both tight.
In the metric TSP, the double tree algorithm $DT$ doubles a minimum spanning tree $T$ (of length $d(T)$), follows an Eulerian circuit of it and skips the cities already visited. With $z(I)$ the length of the optimal tour, which facts are needed to prove $DT(I)\le 2\,z(I)$?
$d(T)\le z(I)$; the minimum perfect matching on the odd-degree cities costs at most $z(I)/2$; shortcuts do not lengthen the walk
$d(T)\le z(I)/2$; the Eulerian circuit of the doubled tree has length $2d(T)$; distances are symmetric
The nearest neighbour tour has length at most $2z(I)$; every city has even degree; distances are symmetric
$d(T)\le z(I)$; the Eulerian circuit of the doubled tree has length $2d(T)$; shortcuts do not lengthen the walk
Explanation. Removing an edge from the optimal tour gives a spanning tree, hence $d(T)\le z(I)$; shortcutting uses the triangle inequality. The matching is needed for $CH$.
In the metric TSP, Christofides' algorithm $CH$ adds to a minimum spanning tree $T$ a minimum perfect matching $M$ on the odd-degree cities of $T$, follows an Eulerian circuit of $T\cup M$ and skips the cities already visited. Which facts are needed to prove $CH(I)\le\frac32\,z(I)$?
$d(T)\le z(I)$; $d(M)\le d(T)$; the odd-degree cities of $T$ are odd in number
$d(T)\le z(I)$; the doubled tree circuit has length $2d(T)$; distances are symmetric
$d(T)\le z(I)$; $d(M)\le z(I)/2$; shortcuts do not lengthen the Eulerian circuit of $T\cup M$
$d(T)\le z(I)/2$; $d(M)\le z(I)$; shortcuts do not lengthen the Eulerian circuit of $T\cup M$
Explanation. The Eulerian circuit of $T\cup M$ has length $d(T)+d(M)\le z(I)+\frac{z(I)}2$; the odd-degree cities of a tree are even in number, so the perfect matching exists.
The proof that the general TSP has no polynomial $\alpha$-approximation (if $P\neq NP$) starts from a graph $G$ asking whether a Hamiltonian cycle exists. Which TSP instance is built?
Distance $2$ on the edges and $1$ on non-adjacent pairs
Distance $1$ on the edges of $G$ and $\alpha n+1$ on non-adjacent pairs: an $\alpha$-approximation would separate tours of length $n$ from the others
Distance $1$ on all pairs: every tour is optimal
Euclidean distances between the vertices of $G$ drawn in the plane
Explanation. If $G$ is Hamiltonian the optimum is $n$ and the algorithm returns at most $\alpha n$, hence only edges of $G$; otherwise every tour uses a non-adjacent pair and exceeds $\alpha n$. An NP-complete problem would be decided.
A TSP instance is metric if $d_{ij}\le d_{ik}+d_{kj}$ for all triples. Which of the following families of instances is always metric?
Cities in the plane with Euclidean distances
Instances with arbitrary integer distances
Instances with $d_{ij}\in\{1,2\}$ and $d_{ij}\ne d_{ji}$
Instances with distances drawn at random in $[1,100]$
Explanation. The Euclidean distance satisfies the triangle inequality. Symmetric distances $1$ and $2$ are metric, but here they are asymmetric; random distances can violate it.
The general TSP has no constant approximation (if $P\neq NP$), the metric TSP does. What is known about the complexity of the metric TSP?
It is polynomial, because the triangle inequality allows shortcuts
It is polynomial on Euclidean instances, NP-hard on the others
It has no constant approximation either
It stays NP-hard, but admits algorithms with constant ratio such as $2$ or $\frac32$
Explanation. The metric does not make the problem easy, but it allows turning closed walks into tours without making them longer: it is the basis of the double tree and Christofides.
In the metric TSP, the double tree algorithm $DT$ computes a minimum spanning tree $T$, doubles its edges, follows an Eulerian circuit and skips the cities already visited. If $d(T)=7$, what is known about the $DT$ tour and the optimal tour $z(I)$?
$DT(I)\le 7$ and $z(I)\ge 14$
$DT(I)\le\frac{21}{2}$ and $z(I)\ge 7$
$DT(I)\le 14$ and $z(I)\ge 7$
$DT(I)=14$ and $z(I)=7$
Explanation. The Eulerian circuit of the doubled tree has length $2d(T)=14$ and shortcuts do not lengthen it; removing an edge from the optimal tour gives a tree, so $d(T)\le z(I)$.
In the Christofides algorithm for the metric TSP, a minimum perfect matching on the cities of odd degree in the minimum spanning tree $T$ is added to $T$. In a star with a centre and $3$ leaves (degree of the centre $3$, of the leaves $1$), how many such cities are there?
$0$
$4$
$3$
$1$
Explanation. The centre has degree $3$ and the three leaves degree $1$: all four are odd. In every graph the number of odd-degree vertices is even, so the perfect matching exists.
For every TSP instance, metric or not, the length $d(T)$ of a minimum spanning tree is at most the length $z(I)$ of the optimal tour. Which argument proves it?
Removing an edge from the optimal tour gives a path through all cities, i.e., a spanning tree, of length at most $z(I)$
The triangle inequality allows shortening the tree
The optimal tour always contains the minimum spanning tree
Doubling the tree gives the optimal tour
Explanation. The path is a spanning tree, and $T$ is the shortest spanning tree; distances are positive, so removing an edge does not lengthen. The metric is not needed.
In the metric TSP, let $O$ be an even set of cities and $M$ a minimum perfect matching of $O$. Why is $d(M)\le z(I)/2$?
Because $M$ has half the edges of the optimal tour
Because every edge of $M$ is shorter than every edge of the tour
Because $M$ is contained in the minimum spanning tree
The optimal tour, shortcut to the cities of $O$ only, splits into two perfect matchings of $O$ with alternate edges; the shorter one has length at most $z(I)/2$
Explanation. By the triangle inequality the tour restricted to $O$ is not longer than $z(I)$; its edges, taken alternately, form two perfect matchings, and the cheaper one is at most half.
In the metric TSP, the Christofides algorithm uses a minimum spanning tree $T$ with $d(T)=10$ and a minimum perfect matching $M$ with $d(M)=4$, and returns a tour of length $CH(I)=14$. What is known about the optimal tour $z(I)$?
$\frac{28}{3}\le z(I)\le 10$
$z(I)\ge 14$
$10\le z(I)\le 14$
$z(I)=14$
Explanation. The $CH$ tour is feasible, so $z(I)\le 14$; $d(T)\le z(I)$ gives $z(I)\ge 10$ (stronger than $14/\frac32\approx 9.33$ and than $2d(M)=8$).
In the metric TSP there are instances $I_n$, with $n\ge 5$ odd, on which the double tree $DT$ has ratio exactly $\frac{2n}{n+2}$. What is it with $n=7$, and what does it tend to?
$2$ for every $n$
$\frac{14}{9}$, and it tends to $2$
$\frac{14}{9}$, and it tends to $\frac32$
$\frac{7}{9}$, and it tends to $1$
Explanation. $\frac{2\cdot 7}{7+2}=\frac{14}{9}\approx 1.56$; as $n\to+\infty$ the ratio tends to $2$, so the guarantee $2$ of $DT$ cannot be improved.
In the metric TSP a closed walk $W$ visiting every city at least once is turned into a tour $\sigma$ by skipping the cities already visited (shortcuts). Why does $L(\sigma)$ not exceed the length of $W$?
By the triangle inequality every shortcut $d_{u_0u_q}$ is at most the length of the stretch of $W$ it replaces
Because $\sigma$ has fewer cities than $W$
Because the distances are all equal
It holds for every TSP instance, even non-metric
Explanation. $d_{u_0u_q}\le d_{u_0u_1}+d_{u_1u_q}\le\dots$; without the triangle inequality a shortcut may lengthen the tour. It is the key step of the double tree and of Christofides.
In the metric TSP, the double tree algorithm and Christofides' algorithm both start from a minimum spanning tree $T$. How do they make the multigraph Eulerian?
Both double the edges of $T$
Double tree: adds a matching; Christofides: doubles $T$
Neither uses an Eulerian multigraph
Double tree: it doubles the edges of $T$; Christofides: it adds a minimum-cost perfect matching on the odd-degree cities of $T$
Explanation. Doubling costs $2d(T)\le2z$; the matching costs at most $z/2$, which gives the guarantees $2$ and $\frac32$. In both cases the Eulerian walk is shortened by shortcuts.
For Christofides' algorithm there are metric instances $I_n$ ($n$ odd) with $CH(I_n)/z(I_n)\to\frac32$. In the construction the MST is the path $1,2,\dots,n$, the odd-degree cities are only $1$ and $n$, and the matching is the long edge $\{1,n\}$. What does it show?
That the double tree is better than Christofides
That shortcuts may lengthen the tour
That the guarantee $\frac32$ of Christofides is tight: the matching may cost almost half the optimal tour
That Christofides is always optimal
Explanation. The cycle $1,\dots,n,1$ costs about $\frac32 z(I_n)$, while the optimal tour advances two cities at a time. No better ratio holds for all instances.
The guarantee $CH(I)\le\frac32z(I)$ of Christofides uses the triangle inequality. What happens for the general TSP, without this assumption?
The general TSP becomes polynomial
No polynomial algorithm has a constant ratio, if P $\ne$ NP
Christofides stays a $\frac32$-approximation
Christofides becomes a $2$-approximation
Explanation. Without the triangle inequality shortcuts may cost a lot, and a constant guarantee would allow deciding the existence of a Hamiltonian cycle.
To show that the TSP has no polynomial $\alpha$-approximation, from a graph $G$ with $n$ vertices one builds an instance with $d_{ij}=1$ if $\{i,j\}$ is an edge of $G$ and $d_{ij}=\lceil\alpha n\rceil+1$ otherwise. With $\alpha=2$ and $n=10$, how long is every tour at least if $G$ has no Hamiltonian cycle?
$21$
$20$
$29$
$30$
Explanation. Every tour uses at least one non-adjacent pair ($21$) and $9$ other edges of length at least $1$: $9+21=30>\alpha n=20$. If $G$ is Hamiltonian, $z=10$ and the algorithm would give at most $20$.
The proof that the general TSP has no constant ratio (if $P\neq NP$) uses distances $1$ on the edges of a graph $G$ and $\lceil\alpha n\rceil+1$ on the other pairs. Why does it say nothing about the metric TSP (triangle inequality $d_{ij}\le d_{ik}+d_{kj}$)?
Because Hamiltonian cycle is easy on metric graphs
Because in the metric TSP distances can be $0$
The instances built violate the triangle inequality
Because the metric TSP is solved in polynomial time
Explanation. If $\{i,k\},\{k,j\}\in E$ and $\{i,j\}\notin E$, then $d_{ij}=\lceil\alpha n\rceil+1>2=d_{ik}+d_{kj}$. The proof needs such large distances; the metric TSP stays NP-hard.
A TSP instance is metric if $d_{ij}\le d_{ik}+d_{kj}$ for every triple of distinct cities. In the reference instance $d_{15}=9$, $d_{12}=5$ and $d_{25}=4$. Does the triple $(1,2,5)$ violate the condition?
No: the condition concerns only nearby cities
No: $9\le5+4$ holds, equality being allowed
Yes: $d_{15}$ is not strictly smaller than $d_{12}+d_{25}$
Yes: $d_{15}$ is the largest distance of the instance
Explanation. The triangle inequality is $\le$, not $<$: $9=5+4$ satisfies it. Going from $1$ to $5$ through $2$ costs no less than the direct link, and shortcuts remain no longer.
In the metric TSP (distances satisfying the triangle inequality) the double tree and the Christofides algorithms have a constant ratio. What role does the triangle inequality play in their guarantees?
Shortcuts (skipping already visited cities) do not lengthen the walk
It makes the TSP solvable in polynomial time
It guarantees that the minimum spanning tree is already a tour
It guarantees that the optimal tour has length at most $2n$
Explanation. Skipping the inner cities of a stretch replaces the stretch by a single edge, not longer by the triangle inequality. The metric TSP stays NP-hard.
Metric TSP with $4$ cities: $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$. Kruskal's algorithm scans the edges by non-decreasing distance (ties by index pair) and takes those that close no cycle. Which minimum spanning tree $T$ does it find?
$\{1,2\},\{3,4\},\{1,4\}$, with $d(T)=8$
$\{1,2\},\{1,3\},\{2,3\}$, with $d(T)=8$
$\{1,2\},\{3,4\}$, with $d(T)=4$
$\{1,2\},\{3,4\},\{1,3\}$, with $d(T)=7$
Explanation. It takes $\{1,2\}$ and $\{3,4\}$ ($2$), then $\{1,3\}$ ($3$, before $\{2,3\}$ by the tie rule), which connects everything. $\{1,2\},\{1,3\},\{2,3\}$ is a cycle; two edges do not span $4$ cities.
In the metric TSP, the double tree and Christofides turn a closed walk $W$ into a tour by shortcuts: follow $W$ and keep every city only at its first occurrence. From $W=(1,2,1,3,4,3,1)$ which tour is obtained?
$(1,3,4,2)$
$(1,2,1,3,4)$
$(1,2,3,4)$
$(1,2,4,3)$
Explanation. The first occurrences, in order, are $1,2,3,4$; the repetitions of $1$ and $3$ are skipped and the tour returns to $1$. $(1,2,1,3,4)$ is not a tour: it repeats city $1$.
Metric TSP with $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$ and minimum spanning tree $T=\{\{1,2\},\{1,3\},\{3,4\}\}$. The double tree visits $T$ depth-first from city $1$ (children in increasing order) and keeps the cities in order of first visit. Which tour does it give, and how long is it?
$(1,2,4,3)$, of length $12$
$(1,2,3,4)$, of length $11$
$(1,2,3,4)$, of length $14$
$(1,3,4,2)$, of length $12$
Explanation. Visit: $1,2,1,3,4,3,1$ (length $2d(T)=14$); the first occurrences give $(1,2,3,4)$: $2+3+2+4=11\le14$. $14$ is the circuit without shortcuts.
In the double tree for the metric TSP the edges of the minimum spanning tree are doubled and an Eulerian circuit is followed with Fleury's rule (avoid a bridge of the unused edges, if there is an alternative). Why is the circuit a depth-first visit of the tree?
The last copy of the edge to the parent is a bridge, used last
Because Kruskal's algorithm always returns a path
Because in the doubled tree every city has degree $2$
Because Fleury always chooses the farthest neighbor
Explanation. As long as a child remains to be visited, going back to the parent would cross a bridge: Fleury goes down into the children first. The tour is therefore the preorder of the tree.
Metric TSP with $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$, minimum tree $T=\{\{1,2\},\{1,3\},\{3,4\}\}$. Christofides adds a minimum perfect matching $M$ on the cities of odd degree in $T$ and follows an Eulerian circuit from $1$ (neighbor of minimum index). Which tour does it give?
$(1,2,3,4)$, of length $11$
$(1,3,4,2)$, of length $15$
$(1,2,1,3,4)$, of length $14$
$(1,2,4,3)$, of length $12$
Explanation. Odd degrees: $2$ and $4$, hence $M=\{\{2,4\}\}$ ($5$). $T\cup M$ is the cycle $1,2,4,3,1$, of length $7+5=12$, with no shortcut. The optimal tour $(1,2,3,4)$ has length $11$: here Christofides does not find it, the double tree does.
In the Christofides algorithm for the metric TSP, $O$ is the set of cities of odd degree in the minimum spanning tree $T$, and a perfect matching of $O$ is sought. Why is $|O|$ always even?
Because the leaves of a tree are always even in number
Because the blossom algorithm requires it
The degrees of a graph sum to twice the number of edges
Because $T$ has $n-1$ edges and $n$ is odd
Explanation. The degree sum is even, so the cities of odd degree are even in number; in the complete graph a perfect matching of $O$ exists. A tree can have an odd number of leaves (star with $3$ leaves).
In a metric TSP instance the minimum spanning tree weighs $d(T)=20$ and a minimum perfect matching of an even set of cities weighs $d(M)=9$. The bounds $d(T)\le z(I)$ and $d(M)\le z(I)/2$ hold ($z(I)$ = length of the optimal tour). Which lower bound on $z(I)$ follows?
$z(I)\ge14.5$
$z(I)\ge20$
$z(I)\ge29$
$z(I)\ge18$
Explanation. The two bounds give $z\ge20$ and $z\ge18$: the stronger one, $20$, holds. Adding them ($29$) is a mistake: $T$ and $M$ are not disjoint parts of a tour.
For the double tree in the metric TSP there are instances $I_n$ ($n$ odd): city $1$ is at distance $a=n$ from all, two leaves are at distance $b=n+1$ if consecutive on a path $P$ and $2a$ otherwise. Why is $DT(I_n)=2(n-1)a$?
The MST is the star; leaves consecutive in preorder are not joined by $P$
Because the minimum tree is the path $P$, traversed twice
Because the shortcuts save $b-a$ at every single step
Because the optimum has length $(n-1)a$ and $DT$ doubles it
Explanation. Every edge weighs at least $a$ and only those from the center equal $a$: the MST is the star. The preorder is $(1,2,\dots,n)$ and consecutive indices are never consecutive on $P$: $a+(n-2)2a+a$. The optimum is $(n+2)(n-1)$.
In scheduling $P\,||\,C_{\max}$ ($m$ machines, durations $t_j$, optimal makespan $z(I)$), $LIST$ assigns every job of the list to the least loaded machine. Let $\ell$ be a job finishing last, with start $S_\ell$. Which facts are needed to prove $LIST(I)\le\left(2-\frac1m\right)z(I)$?
Explanation. $LIST(I)=S_\ell+t_\ell\le\frac1m\sum_j t_j+\left(1-\frac1m\right)t_\ell\le\left(2-\frac1m\right)z(I)$. Sorting is needed only for the better guarantee of $LPT$.
In scheduling $P\,||\,C_{\max}$, $LPT$ sorts the jobs by non-increasing duration and assigns each to the least loaded machine; its guarantee is $\frac43-\frac1{3m}$. What is it with $m=2$ machines?
$\frac43$
$\frac54$
$\frac76$
$\frac32$
Explanation. $\frac43-\frac1{3m}=\frac43-\frac16=\frac76$. With any list $LIST$ guarantees $2-\frac12=\frac32$.
In scheduling $P\,||\,C_{\max}$ with $m$ machines, $LIST$ (any list, least loaded machine) guarantees $2-\frac1m$ and $LPT$ (list by non-increasing duration) guarantees $\frac43-\frac1{3m}$. Which statement is correct?
Neither is reached: the ratios are only approached as $n$ grows
Both are tight: for every $m\ge 2$ some instances reach exactly the two ratios
Both are tight only for $m=2$; for $m\ge 3$ the ratios are lower
The guarantee of $LIST$ is tight, that of $LPT$ is not: its true ratio is lower
Explanation. Graham's instance families reach exactly the two ratios for every $m\ge 2$ (for $LPT$: $2m+1$ jobs, two of every duration from $2m-1$ down to $m$ plus one of duration $m$).
Scheduling $P\,||\,C_{\max}$ with $m=3$ machines. $LIST$ assigns every job, in list order, to the least loaded machine (ties: smallest index); $LPT$ does the same with the list sorted by non-increasing time. With the list $t=(2,3,4,6,2,2)$, what are the makespans of $LIST$ and $LPT$?
$8$ and $8$
$9$ and $7$
$8$ and $7$
$7$ and $7$
Explanation. $LIST$: $2,3,4$ on the three machines, $6$ on the first ($8$), then $2$ on the second ($5$) and $2$ on the third ($6$): makespan $8$. $LPT$ with $(6,4,3,2,2,2)$ gives loads $(6,6,7)$, and $\lceil 19/3\rceil=7$ proves it optimal.
In scheduling $P\,||\,C_{\max}$, $LIST$ assigns the jobs in the order of a given list and $LPT$ first sorts them by non-increasing time. Which practical difference is there between the two algorithms?
$LPT$ is exponential, $LIST$ polynomial
$LIST$ can work online, assigning jobs as they arrive; $LPT$ must know all the jobs to sort them
$LIST$ requires knowing all the jobs, $LPT$ does not
$LPT$ uses the most loaded machine, $LIST$ the least loaded
Explanation. Both use the least-loaded-machine rule; sorting costs $O(n\log n)$ and needs all the data, but lowers the guarantee from $2-\frac1m$ to $\frac43-\frac1{3m}$.
In scheduling $P\,||\,C_{\max}$ with $m$ machines, let $\ell$ be a job ending last in the $LIST$ schedule, with start $S_\ell$. Why is $S_\ell\le\frac1m\sum_{j\ne\ell}t_j$?
$\ell$ goes on the least loaded machine, whose load is at most the average load, which contains only jobs other than $\ell$
Because $\ell$ is the longest job
Because the jobs are sorted by non-increasing time
Because $S_\ell$ is always zero
Explanation. When $\ell$ is assigned, the chosen machine has the minimum load, and the minimum is at most the average of the loads at that time, which add up jobs other than $\ell$. No order of the list is needed.
In scheduling $P\,||\,C_{\max}$ with $m=3$ machines, $LIST$ produces a schedule in which job $\ell$, of time $t_\ell=4$, ends last; the other jobs have total time $15$. Which upper bound on the makespan of $LIST$ follows?
$19$
$5$
$\frac{19}{3}$
$9$
Explanation. $S_\ell\le\frac{15}{3}=5$, hence $LIST(I)=S_\ell+t_\ell\le 9$. With $z(I)\ge\frac{19}{3}$ and $z(I)\ge 4$ the guarantee $2-\frac1m$ follows.
In scheduling $P\,||\,C_{\max}$ with $m=3$ machines, the list contains $m(m-1)=6$ jobs of time $1$ followed by a job of time $m=3$. What are the makespan of $LIST$ and the optimal one?
$5$ and $4$: ratio $\frac54$
$6$ and $3$: ratio $2$
$5$ and $3$: ratio $\frac53=2-\frac13$
$3$ and $3$: $LIST$ is optimal
Explanation. $LIST$ spreads the short jobs, $2$ per machine, then the long job ends at $2+3=5$. The optimum puts the long job alone and $3$ short jobs on each of the others: $3$. The guarantee is attained.
Scheduling $P\,||\,C_{\max}$ with $m=3$ machines and times $t=(5,5,4,4,3,3,3)$. $LPT$ assigns the jobs in this order to the least loaded machine (ties: smallest index). What are the makespan of $LPT$ and the optimal one?
$12$ and $9$
$11$ and $9$: ratio $\frac{11}{9}=\frac43-\frac19$
$9$ and $9$: $LPT$ is optimal
$11$ and $10$
Explanation. $LPT$: $5,5,4$ on the three machines, $4\to M_3$ ($8$), $3\to M_1$ ($8$), $3\to M_2$ ($8$), the last $3\to M_1$ ($11$). The optimum is $\{5,4\},\{5,4\},\{3,3,3\}$ with makespan $9$.
In scheduling $P\,||\,C_{\max}$, the lower bound $\mathrm{LB}=\max\{\max_jt_j,\ \frac1m\sum_jt_j\}$ holds for the optimal makespan. How is the makespan of $LIST$ related to $\mathrm{LB}$?
Explanation. The last job starts within the average of the others and lasts at most $\max_jt_j$; both terms are at most $\mathrm{LB}$. A finer estimate gives $2-\frac1m$.
In scheduling $P\,||\,C_{\max}$ with $m=2$ machines and times $t=(1,1,2)$ in this order, what are the makespans of $LIST$ (given list, least loaded machine, ties smallest index) and $LPT$?
$LIST$ $3$, $LPT$ $3$
$LIST$ $4$, $LPT$ $2$
$LIST$ $3$, $LPT$ $2$
$LIST$ $2$, $LPT$ $2$
Explanation. $LIST$: $1\to M_1$, $1\to M_2$, $2\to M_1$: loads $(3,1)$. $LPT$: $2\to M_1$, $1\to M_2$, $1\to M_2$: loads $(2,2)$, optimal. Placing long jobs first avoids leaving them last.
In the chapter on the approximation of $P\,||\,C_{\max}$, $z(I)$ is the optimal makespan and $\mathscr{A}(I)$ that of a heuristic. Which two lower bounds on $z(I)$ are used in the proofs of the guarantees?
$z(I)\ge m$ and $z(I)\ge n$
$z(I)\ge\mathscr{A}(I)$
$z(I)\ge\max_jt_j$ and $z(I)\ge\frac1m\sum_jt_j$
$z(I)\ge\min_jt_j$ and $z(I)\ge\sum_jt_j$
Explanation. The longest job is on some machine, and the maximum load is at least the average load. Combined with the last assigned job they give the guarantee $2-\frac1m$ of $LIST$.
The guarantee of $LPT$ for $P\,||\,C_{\max}$ is $\frac43-\frac1{3m}$, better than the $2-\frac1m$ of $LIST$. Which assumption on the order of the jobs makes it possible?
The machines have different speeds
The jobs are examined by non-increasing duration, so the last assigned job is short compared to the optimum
The jobs are examined in random order
The jobs all have the same duration
Explanation. If the job determining the makespan is the shortest, either $z(I)$ is small and the solution is optimal, or the job weighs at most $z(I)/3$. With an arbitrary order the last job may be the longest.
List scheduling ($LIST$) for $P\,||\,C_{\max}$ assigns the jobs, in list order, to the machine of minimum load (ties: smallest index). With $m=2$ and the list of times $(2,3,4,5)$, which makespan does it obtain?
$8$
$7$
$9$
$14$
Explanation. $2\to M_1$, $3\to M_2$, $4\to M_1$ (load $6$), $5\to M_2$ (load $8$): makespan $8$. The optimum $\{2,5\},\{3,4\}$ is $7$.
In $LIST$ for $P\,||\,C_{\max}$, job $j$ starts at time $S_j$ equal to the load of its machine at assignment. Why, when the last job starts, are all machines busy at least until $S_j$?
Because the list is sorted by decreasing times
Because the machines are empty at the start
Because the longest job is always the last one
The job goes to the machine of minimum load
Explanation. $S_j$ is the minimum of the loads: the other machines finish no earlier. It is the observation on which the guarantee of $LIST$ is built.
The LPT rule for $P\,||\,C_{\max}$ is $LIST$ with the list sorted by non-increasing times. With $m=2$ and times $\{2,3,4,5\}$, which makespan does it obtain?
$6$
$9$
$7$
$8$
Explanation. Order $5,4,3,2$: $5\to M_1$, $4\to M_2$, $3\to M_2$ (load $7$), $2\to M_1$ (load $7$): makespan $7$, the optimum. The increasing list gave $8$.
In a $LIST$ schedule for $P\,||\,C_{\max}$, the job $\ell$ finishing last starts at $S_\ell\le\frac1m\sum_{j\neq\ell}t_j$. With $m=3$, $\sum_jt_j=27$ and $t_\ell=3$, which bound is obtained on $S_\ell$ and on the makespan?
$S_\ell\le24$, makespan $\le27$
$S_\ell\le8$, makespan $\le11$
$S_\ell\le9$, makespan $\le12$
$S_\ell\le8$, makespan $\le8$
Explanation. $S_\ell\le(27-3)/3=8$ and the makespan is $S_\ell+t_\ell\le11$. $9=27/3$ forgets to remove job $\ell$.
From $S_\ell\le\frac1m\sum_{j\neq\ell}t_j$ ($\ell$ the job finishing last in $LIST$) one gets $LIST(I)\le\frac1m\sum_jt_j+(1-\frac1m)t_\ell$. Which two facts then give $LIST(I)\le(2-\frac1m)z(I)$?
$\frac1m\sum_jt_j\le z(I)$ and $t_\ell\le z(I)$
$t_\ell\le\frac1m\sum_jt_j$ and $z(I)\le\sum_jt_j$
$LIST$ is optimal for $m=1$ and $t_\ell\le1$
$S_\ell\le z(I)$ and $m\ge2$
Explanation. They are the two terms of the lower bound $\max\{\max_jt_j,\sum_jt_j/m\}\le z(I)$: adding $z+(1-\frac1m)z$ gives $2-\frac1m$.
Why does $LPT$ have a better guarantee than $LIST$?
Because $LPT$ is exact
Because $LPT$ uses more machines
Because $LPT$ ignores short jobs
The last job is short
Explanation. With jobs by decreasing duration, if the critical job is long the optimum puts few jobs per machine and $LPT$ is optimal; otherwise it is short.
The tight instances of $LPT$ have $2m+1$ jobs. How many jobs do they have with $m=3$?
$7$
$6$
$9$
$4$
Explanation. $2\cdot3+1=7$: two for each duration from $2m-1$ to $m+1$ and three of duration $m$.
Generated questions (16)
Each generator builds a new instance, with different numbers, at every start: a few examples here.
1. Principles of approximation algorithms (2)
Example 1 · aa-g-approx-interval · level facile · notes
An algorithm $\mathscr{A}$ is an $\alpha$-approximation, with $\alpha=\frac{4}{3}$, for a maximization problem: $z(I)\le\alpha\,\mathscr{A}(I)$ for every instance $I$, where $z(I)$ is the optimal value. On an instance $I$ it returns $\mathscr{A}(I)=96$. What can be concluded on the optimal value $z(I)$?
$72\le z(I)\le 128$
$72\le z(I)\le 96$
$96\le z(I)\le 128$
$z(I)=128$
Explanation. For a maximization problem $z(I)/\mathscr{A}(I)\le\alpha$ and $\mathscr{A}(I)\le z(I)$, hence $\mathscr{A}(I)\le z(I)\le\alpha\,\mathscr{A}(I)$.
Example 2 · aa-g-approx-interval · level facile · notes
An algorithm $\mathscr{A}$ is an $\alpha$-approximation, with $\alpha=2$, for a maximization problem: $z(I)\le\alpha\,\mathscr{A}(I)$ for every instance $I$, where $z(I)$ is the optimal value. On an instance $I$ it returns $\mathscr{A}(I)=8$. What can be concluded on the optimal value $z(I)$?
$z(I)=16$
$4\le z(I)\le 16$
$4\le z(I)\le 8$
$8\le z(I)\le 16$
Explanation. For a maximization problem $z(I)/\mathscr{A}(I)\le\alpha$ and $\mathscr{A}(I)\le z(I)$, hence $\mathscr{A}(I)\le z(I)\le\alpha\,\mathscr{A}(I)$.
Example 1 · aa-g-approx-error · level facile · notes
For a maximization problem an algorithm finds a solution of value $\mathscr{A}(I)=15$ and the optimal value is $z(I)=27$. The performance ratio is $z(I)/\mathscr{A}(I)$ and the relative error $|\mathscr{A}(I)-z(I)|/z(I)$. What are they, in this order?
$\frac{9}{5}$ and $\frac{4}{5}$
$\frac{5}{9}$ and $\frac{4}{9}$
$\frac{9}{5}$ and $\frac{4}{9}$
$\frac{4}{9}$ and $\frac{9}{5}$
Explanation. Ratio $\frac{9}{5}\ge 1$ and error $\frac{4}{9}$; the error is divided by the optimal value, not by the value found.
Example 2 · aa-g-approx-error · level facile · notes
For a minimization problem an algorithm finds a solution of value $\mathscr{A}(I)=41$ and the optimal value is $z(I)=36$. The performance ratio is $\mathscr{A}(I)/z(I)$ and the relative error $|\mathscr{A}(I)-z(I)|/z(I)$. What are they, in this order?
$\frac{5}{36}$ and $\frac{41}{36}$
$\frac{41}{36}$ and $\frac{5}{41}$
$\frac{36}{41}$ and $\frac{5}{36}$
$\frac{41}{36}$ and $\frac{5}{36}$
Explanation. Ratio $\frac{41}{36}\ge 1$ and error $\frac{5}{36}$; the error is divided by the optimal value, not by the value found.
2. Approximation algorithms for the knapsack problem (3)
Example 1 · aa-g-kp-extgreedy · level facile · notes
0-1 knapsack problem (KP: choose a subset of items of maximum profit with total weight at most $c$) with capacity $c=12$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 8 & 12 & 19 & 15 & 18\\ w_j & 1 & 7 & 9 & 7 & 5\end{array}$. The Ext-Greedy algorithm returns the better of the greedy solution by non-increasing efficiency $p_j/w_j$ (ties: smaller index) and the best single item. What is $GR^e(I)$?
$33$
$27$
$26$
$20$
Explanation. $GR$ (by non-increasing efficiency) has value $26$; the best single item has profit $19$; $GR^e(I)=\max\{26,19\}=26$. The optimal value is $z(I)=33$.
Example 2 · aa-g-kp-extgreedy · level facile · notes
0-1 knapsack problem (KP: choose a subset of items of maximum profit with total weight at most $c$) with capacity $c=12$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 15 & 10 & 13 & 18 & 12\\ w_j & 9 & 5 & 3 & 1 & 8\end{array}$. The Ext-Greedy algorithm returns the better of the greedy solution by non-increasing efficiency $p_j/w_j$ (ties: smaller index) and the best single item. What is $GR^e(I)$?
$33$
$43$
$41$
$28$
Explanation. $GR$ (by non-increasing efficiency) has value $41$; the best single item has profit $18$; $GR^e(I)=\max\{41,18\}=41$. The optimal value is $z(I)=43$.
0-1 knapsack problem (KP: choose a subset of items of maximum profit with total weight at most $c$) with capacity $c=9$ and $n=4$ items sorted by non-increasing efficiency: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 17 & 10 & 7 & 12\\ w_j & 2 & 4 & 3 & 6\end{array}$. The Basic-FPTAS $FP^{\varepsilon}$, with $\varepsilon=\frac{1}{2}$, scales the profits by the factor $K=\varepsilon\,GR^e(I)/n$, where $GR^e(I)$ is the Ext-Greedy value (better of the greedy by efficiency and the best single item). What are the scaled profits $p'_j=\lfloor p_j/K\rfloor$?
$p'=(1,0,0,0)$
$p'=(4,3,2,3)$
$p'=(4,2,1,2)$
$p'=(8,4,3,5)$
Explanation. $GR^e(I)=34$, $K=\varepsilon\,GR^e(I)/n=\frac{17}{4}$ and $p'_j=\lfloor p_j/K\rfloor$: $p'=(4,2,1,2)$. The profits are rounded down and the factor uses $GR^e(I)$ and $n$.
0-1 knapsack problem (KP: choose a subset of items of maximum profit with total weight at most $c$) with capacity $c=12$ and $n=4$ items sorted by non-increasing efficiency: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 36 & 35 & 28 & 9\\ w_j & 3 & 3 & 5 & 3\end{array}$. The Basic-FPTAS $FP^{\varepsilon}$, with $\varepsilon=\frac{1}{4}$, scales the profits by the factor $K=\varepsilon\,GR^e(I)/n$, where $GR^e(I)$ is the Ext-Greedy value (better of the greedy by efficiency and the best single item). What are the scaled profits $p'_j=\lfloor p_j/K\rfloor$?
$p'=(5,5,4,1)$
$p'=(6,6,5,2)$
$p'=(1,1,1,0)$
$p'=(16,15,12,4)$
Explanation. $GR^e(I)=99$, $K=\varepsilon\,GR^e(I)/n=\frac{99}{16}$ and $p'_j=\lfloor p_j/K\rfloor$: $p'=(5,5,4,1)$. The profits are rounded down and the factor uses $GR^e(I)$ and $n$.
Example 1 · aa-g-kp-fptas-full · level complessa · notes
0/1 knapsack with capacity $c=9$ and items sorted by non-increasing efficiency: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 22 & 25 & 31 & 11 & 16\\ w_j & 2 & 3 & 4 & 2 & 3\end{array}$. The Basic-FPTAS algorithm with $\varepsilon=\frac12$ computes $GR^e(I)=\max\{GR(I),\max_jp_j\}$ ($GR$: greedy by efficiency, skipping the items that do not fit), sets $K=\varepsilon\,GR^e(I)/n$ and $p'_j=\lfloor p_j/K\rfloor$, solves the instance with profits $p'_j$ to optimality and returns the original profit $FP^{\varepsilon}(I)$ of the solution found. What are $FP^{\varepsilon}(I)$ and the optimal value $z(I)$?
$FP^{\varepsilon}(I)=8$, $z(I)=78$
$FP^{\varepsilon}(I)=78$, $z(I)=79$
$FP^{\varepsilon}(I)=78$, $z(I)=156$
$FP^{\varepsilon}(I)=78$, $z(I)=78$
Explanation. $GR^e(I)=78$, $K=\frac{39}{5}$, $p'=(2,3,3,1,2)$. The scaled instance has optimum $8$ with items $\{1,2,3\}$, of original profit $78$; the true optimum is $78$, and indeed $78\ge\frac12\cdot78$.
Example 2 · aa-g-kp-fptas-full · level complessa · notes
0/1 knapsack with capacity $c=13$ and items sorted by non-increasing efficiency: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 36 & 35 & 29 & 32 & 11\\ w_j & 4 & 4 & 6 & 7 & 3\end{array}$. The Basic-FPTAS algorithm with $\varepsilon=\frac12$ computes $GR^e(I)=\max\{GR(I),\max_jp_j\}$ ($GR$: greedy by efficiency, skipping the items that do not fit), sets $K=\varepsilon\,GR^e(I)/n$ and $p'_j=\lfloor p_j/K\rfloor$, solves the instance with profits $p'_j$ to optimality and returns the original profit $FP^{\varepsilon}(I)$ of the solution found. What are $FP^{\varepsilon}(I)$ and the optimal value $z(I)$?
$FP^{\varepsilon}(I)=82$, $z(I)=164$
$FP^{\varepsilon}(I)=9$, $z(I)=82$
$FP^{\varepsilon}(I)=82$, $z(I)=82$
$FP^{\varepsilon}(I)=82$, $z(I)=83$
Explanation. $GR^e(I)=82$, $K=\frac{41}{5}$, $p'=(4,4,3,3,1)$. The scaled instance has optimum $9$ with items $\{1,2,5\}$, of original profit $82$; the true optimum is $82$, and indeed $82\ge\frac12\cdot82$.
3. Approximation algorithms for bin packing (3)
Example 1 · aa-g-bpp-anyfit · level facile · notes
Bin packing (BPP: items into bins of capacity $c$, minimizing the bins) with $c=10$ and weights, in the order of examination, $w=(7,4,3,7,3,6,4)$. Bins are numbered in order of opening; ties on the residual capacity go to the smaller index. Which vector $bin$ (bin of each item) does First Fit (FF) produce?
$bin=(1,2,2,3,1,4,4)$
$bin=(1,2,2,3,3,4,4)$
$bin=(1,2,1,3,3,2,4)$
$bin=(1,2,1,3,2,4,4)$
Explanation. FF gives $bin=(1,2,1,3,2,4,4)$ with $4$ bins. NF keeps a single open bin; FF chooses the first bin where the item fits, BF the one with the smallest residual capacity, WF the one with the largest residual capacity.
Example 2 · aa-g-bpp-anyfit · level facile · notes
Bin packing (BPP: items into bins of capacity $c$, minimizing the bins) with $c=10$ and weights, in the order of examination, $w=(3,7,6,5,7,4,3)$. Bins are numbered in order of opening; ties on the residual capacity go to the smaller index. Which vector $bin$ (bin of each item) does Next Fit (NF) produce?
$bin=(1,1,2,3,4,2,4)$
$bin=(1,1,2,3,4,2,3)$
$bin=(1,1,2,3,4,5,5)$
$bin=(1,1,2,3,4,3,2)$
Explanation. NF gives $bin=(1,1,2,3,4,5,5)$ with $5$ bins. NF keeps a single open bin; FF chooses the first bin where the item fits, BF the one with the smallest residual capacity, WF the one with the largest residual capacity.
Bin packing with capacity $c=10$ and items of weight $(4,2,1,6,6,6,8,3)$ in this order. Next Fit (NF) keeps a single bin open and opens a new one when the item does not fit. How many bins does NF use, and what is the weight bound $\lceil\sum_jw_j/c\rceil$, in this order?
$4$, $6$
$6$, $5$
$5$, $4$
$6$, $4$
Explanation. NF uses $6$ bins and the bound is $\lceil 36/10\rceil=4$; First Fit, which reuses the open bins, uses $5$. Always $NF(I)\le 2z(I)$.
Bin packing with capacity $c=10$ and items of weight $(4,7,3,1,4,7,7,6)$ in this order. Next Fit (NF) keeps a single bin open and opens a new one when the item does not fit. How many bins does NF use, and what is the weight bound $\lceil\sum_jw_j/c\rceil$, in this order?
$6$, $4$
$5$, $4$
$6$, $5$
$4$, $6$
Explanation. NF uses $6$ bins and the bound is $\lceil 39/10\rceil=4$; First Fit, which reuses the open bins, uses $5$. Always $NF(I)\le 2z(I)$.
Example 1 · aa-g-bpp-anyfit-full · level complessa · notes
Bin packing with bins of capacity $c=10$ and items, in input order, of weight $w=(5,3,2,6,6,6,8,4)$. Next Fit (NF) keeps only the last bin open; First Fit (FF), Best Fit (BF) and Worst Fit (WF) put every item, respectively, into the first bin where it fits, into the one with minimum residual capacity and into the one with maximum residual capacity among those where it fits (ties: smallest index), and open a new bin only if it fits in none. How many bins does each algorithm use?
$NF=5$, $FF=5$, $BF=5$, $WF=5$
$NF=6$, $FF=5$, $BF=5$, $WF=6$
$NF=5$, $FF=6$, $BF=5$, $WF=5$
$NF=6$, $FF=5$, $BF=5$, $WF=5$
Explanation. Simulating the four rules: $NF=6$, $FF=5$, $BF=5$, $WF=5$; the weight bound is $\lceil40/10\rceil=4$. NF is not Any Fit: it closes a bin even if a later item would fit into it.
Example 2 · aa-g-bpp-anyfit-full · level complessa · notes
Bin packing with bins of capacity $c=10$ and items, in input order, of weight $w=(4,7,4,2,4,8,7,6)$. Next Fit (NF) keeps only the last bin open; First Fit (FF), Best Fit (BF) and Worst Fit (WF) put every item, respectively, into the first bin where it fits, into the one with minimum residual capacity and into the one with maximum residual capacity among those where it fits (ties: smallest index), and open a new bin only if it fits in none. How many bins does each algorithm use?
$NF=6$, $FF=5$, $BF=5$, $WF=5$
$NF=5$, $FF=6$, $BF=5$, $WF=5$
$NF=6$, $FF=5$, $BF=5$, $WF=6$
$NF=5$, $FF=5$, $BF=5$, $WF=5$
Explanation. Simulating the four rules: $NF=6$, $FF=5$, $BF=5$, $WF=5$; the weight bound is $\lceil42/10\rceil=5$. NF is not Any Fit: it closes a bin even if a later item would fit into it.
4. Vertex coloring: limits of approximation (2)
Example 1 · aa-g-vci-interval · level facile · notes
Interval graph with vertices $1,\dots,6$ and closed intervals $I_{1}=[1,5]$, $I_{2}=[5,8]$, $I_{3}=[6,9]$, $I_{4}=[7,11]$, $I_{5}=[8,9]$, $I_{6}=[8,9]$ (two vertices are adjacent if their intervals intersect). How many colors does the greedy coloring use with the vertices in order of non-decreasing left endpoint?
$3$
$4$
$5$
$6$
Explanation. On an interval graph that order gives $\omega(G)$ colors, the largest number of intervals with a common point: here $5$, and it is optimal since $\chi(G)\ge\omega(G)$. The bound $\Delta(G)+1=6$ holds for every order but is weaker.
Example 2 · aa-g-vci-interval · level facile · notes
Interval graph with vertices $1,\dots,6$ and closed intervals $I_{1}=[3,4]$, $I_{2}=[3,7]$, $I_{3}=[3,7]$, $I_{4}=[6,10]$, $I_{5}=[7,10]$, $I_{6}=[9,13]$ (two vertices are adjacent if their intervals intersect). How many colors does the greedy coloring use with the vertices in order of non-decreasing left endpoint?
$3$
$5$
$4$
$6$
Explanation. On an interval graph that order gives $\omega(G)$ colors, the largest number of intervals with a common point: here $4$, and it is optimal since $\chi(G)\ge\omega(G)$. The bound $\Delta(G)+1=5$ holds for every order but is weaker.
Example 1 · aa-g-vci-planar · level facile · notes
A simple graph has $n=19$ vertices and $m=60$ edges. Using the lemma on the number of edges of planar graphs, what can be said?
$3n-6=51$: it can be planar
$3n-6=51$: it is not planar
$3n-6=54$: it is not planar
$3n-6=54$: it can be planar
Explanation. Every planar graph with $n\ge3$ vertices has $m\le3n-6=51$. Here $m>51$: the graph is not planar.
Example 2 · aa-g-vci-planar · level facile · notes
A simple graph has $n=14$ vertices and $m=52$ edges. Using the lemma on the number of edges of planar graphs, what can be said?
$3n-6=39$: it can be planar
$3n-6=39$: it is not planar
$3n-6=36$: it is not planar
$3n-6=36$: it can be planar
Explanation. Every planar graph with $n\ge3$ vertices has $m\le3n-6=36$. Here $m>36$: the graph is not planar.
5. Maximum clique: limits of approximation (2)
Example 1 · aa-g-cli-product · level facile · notes
Two graphs on the vertices $\{1,2,3,4\}$: $G$ with $E=\{\{2,4\}\}$ and $H$ with $F=\{\{2,3\},\{3,4\}\}$. How many vertices does the strong product $G\boxtimes H$ have, and what is its clique number?
$16$ vertices and $\omega=5$
$16$ vertices and $\omega=2$
$16$ vertices and $\omega=4$
$8$ vertices and $\omega=4$
Explanation. $G\boxtimes H$ has $4\cdot4=16$ vertices and $\omega(G\boxtimes H)=\omega(G)\,\omega(H)=2\cdot2=4$: the product of two cliques is a clique, and every clique of the product lies in such a product.
Example 2 · aa-g-cli-product · level facile · notes
Two graphs on the vertices $\{1,2,3,4\}$: $G$ with $E=\{\{1,3\}\}$ and $H$ with $F=\{\{1,2\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$. How many vertices does the strong product $G\boxtimes H$ have, and what is its clique number?
$8$ vertices and $\omega=6$
$16$ vertices and $\omega=5$
$16$ vertices and $\omega=3$
$16$ vertices and $\omega=6$
Explanation. $G\boxtimes H$ has $4\cdot4=16$ vertices and $\omega(G\boxtimes H)=\omega(G)\,\omega(H)=2\cdot3=6$: the product of two cliques is a clique, and every clique of the product lies in such a product.
Example 1 · aa-g-cli-maximal · level facile · notes
Graph with vertices $1,\dots,8$ and $E=\{\{1,6\},\{2,5\},\{2,7\},\{2,8\},\{3,4\},\{3,5\},\{3,6\},\{3,8\},\{4,8\},\{5,7\},\{6,7\},\{6,8\},\{7,8\}\}$. The greedy algorithm examines the vertices in the order $1,2,\dots,8$ and adds a vertex to $S$ if it is adjacent to no vertex already in $S$. What is $|S|$, and what is the lower bound $\lceil n/(\Delta(G)+1)\rceil$ valid for every maximal stable set?
$|S|=3$, bound $3$
$|S|=2$, bound $2$
$|S|=4$, bound $2$
$|S|=3$, bound $2$
Explanation. The greedy finds $S=\{1,2,3\}$, maximal. With $\Delta(G)=5$ every vertex of $S$ excludes at most $\Delta(G)$ neighbours, hence $|S|\ge\lceil 8/6\rceil=2$ and $\alpha(G)/|S|\le\Delta(G)+1$.
Example 2 · aa-g-cli-maximal · level facile · notes
Graph with vertices $1,\dots,8$ and $E=\{\{1,4\},\{1,5\},\{3,4\},\{4,5\},\{4,8\},\{5,6\},\{5,7\},\{5,8\},\{6,7\}\}$. The greedy algorithm examines the vertices in the order $1,2,\dots,8$ and adds a vertex to $S$ if it is adjacent to no vertex already in $S$. What is $|S|$, and what is the lower bound $\lceil n/(\Delta(G)+1)\rceil$ valid for every maximal stable set?
$|S|=5$, bound $2$
$|S|=4$, bound $2$
$|S|=5$, bound $3$
$|S|=6$, bound $2$
Explanation. The greedy finds $S=\{1,2,3,6,8\}$, maximal. With $\Delta(G)=5$ every vertex of $S$ excludes at most $\Delta(G)$ neighbours, hence $|S|\ge\lceil 8/6\rceil=2$ and $\alpha(G)/|S|\le\Delta(G)+1$.
6. The TSP: the general case and the metric case (2)
Metric TSP with $5$ cities and distances (Manhattan distances between points of the plane, all different) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 12 & 10 & 7 & 4\\ 2 & 12 & - & 2 & 5 & 16\\ 3 & 10 & 2 & - & 3 & 14\\ 4 & 7 & 5 & 3 & - & 11\\ 5 & 4 & 16 & 14 & 11 & -\end{array}$. How long is a minimum spanning tree $T$, whose length $d(T)$ is a lower bound on the optimal tour?
$15$
$17$
$32$
$16$
Explanation. Prim's (or Kruskal's) algorithm gives $d(T)=16$. Removing an edge from the optimal tour gives a spanning tree, so $d(T)\le z(I)$; the double tree gives a tour of length at most $2d(T)=32$.
Metric TSP with $5$ cities and distances (Manhattan distances between points of the plane, all different) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 5 & 6 & 14 & 16\\ 2 & 5 & - & 3 & 11 & 13\\ 3 & 6 & 3 & - & 8 & 10\\ 4 & 14 & 11 & 8 & - & 2\\ 5 & 16 & 13 & 10 & 2 & -\end{array}$. How long is a minimum spanning tree $T$, whose length $d(T)$ is a lower bound on the optimal tour?
$34$
$15$
$18$
$36$
Explanation. Prim's (or Kruskal's) algorithm gives $d(T)=18$. Removing an edge from the optimal tour gives a spanning tree, so $d(T)\le z(I)$; the double tree gives a tour of length at most $2d(T)=36$.
Metric TSP with $5$ cities and distances (Manhattan distances between points of the plane, all different) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 4 & 5 & 9 & 6\\ 2 & 4 & - & 1 & 13 & 10\\ 3 & 5 & 1 & - & 12 & 11\\ 4 & 9 & 13 & 12 & - & 7\\ 5 & 6 & 10 & 11 & 7 & -\end{array}$. The double tree algorithm takes the (unique) minimum spanning tree, doubles its edges, walks it depth first from city $1$ visiting children by increasing index and skips the cities already visited: the tour is the order of first visit. How long is it?
$18$
$36$
$33$
$32$
Explanation. The tree has $d(T)=18$; the order of first visit is $(1,2,3,5,4)$, of length $32\le 2d(T)=36$: shortcuts do not lengthen the walk because the distances are metric.
Metric TSP with $5$ cities and distances (Manhattan distances between points of the plane, all different) $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 5 & 6 & 14 & 16\\ 2 & 5 & - & 3 & 11 & 13\\ 3 & 6 & 3 & - & 8 & 10\\ 4 & 14 & 11 & 8 & - & 2\\ 5 & 16 & 13 & 10 & 2 & -\end{array}$. The double tree algorithm takes the (unique) minimum spanning tree, doubles its edges, walks it depth first from city $1$ visiting children by increasing index and skips the cities already visited: the tour is the order of first visit. How long is it?
$18$
$35$
$34$
$36$
Explanation. The tree has $d(T)=18$; the order of first visit is $(1,2,3,4,5)$, of length $34\le 2d(T)=36$: shortcuts do not lengthen the walk because the distances are metric.
7. Approximation for $P\|C_{\max}$ (2)
Example 1 · aa-g-pcmax-list · level facile · notes
Scheduling $P\,||\,C_{\max}$ with $m=3$ identical machines and times, in list order, $t=(6,8,1,8,2,3,1)$. $LIST$ assigns every job to the least loaded machine (ties: smallest index) in list order; $LPT$ does the same after sorting the jobs by non-increasing time. What are the makespans of $LIST$ and $LPT$, in this order?
$11$, $11$
$10$, $11$
$10$, $10$
$11$, $10$
Explanation. $LIST$ gives $11$ and $LPT$ gives $10$; the lower bound $\lceil\sum_jt_j/m\rceil$ is $10$.
Example 2 · aa-g-pcmax-list · level facile · notes
Scheduling $P\,||\,C_{\max}$ with $m=3$ identical machines and times, in list order, $t=(4,8,3,1,4,8,8)$. $LIST$ assigns every job to the least loaded machine (ties: smallest index) in list order; $LPT$ does the same after sorting the jobs by non-increasing time. What are the makespans of $LIST$ and $LPT$, in this order?
$16$, $12$
$12$, $16$
$12$, $12$
$16$, $16$
Explanation. $LIST$ gives $16$ and $LPT$ gives $12$; the lower bound $\lceil\sum_jt_j/m\rceil$ is $12$.
Example 1 · aa-g-pcmax-ratio · level media · notes
Scheduling $P\,||\,C_{\max}$ with $m=2$ identical machines and times $t=(2,8,3,2,9,6)$. $LPT$ sorts the jobs by non-increasing time and assigns each to the least loaded machine (ties: smallest index). What is the ratio $LPT(I)/z(I)$, with $z(I)$ the optimal makespan?
$\frac{15}{16}$
$\frac{7}{6}$
$\frac{16}{15}$
$1$
Explanation. $LPT(I)=16$ and $z(I)=15$: ratio $\frac{16}{15}$, at most the guarantee $\frac43-\frac1{3m}=\frac{7}{6}$.
Example 2 · aa-g-pcmax-ratio · level media · notes
Scheduling $P\,||\,C_{\max}$ with $m=2$ identical machines and times $t=(9,2,9,6,7,7)$. $LPT$ sorts the jobs by non-increasing time and assigns each to the least loaded machine (ties: smallest index). What is the ratio $LPT(I)/z(I)$, with $z(I)$ the optimal makespan?
$\frac{7}{6}$
$\frac{10}{11}$
$\frac{11}{10}$
$\frac{22}{21}$
Explanation. $LPT(I)=22$ and $z(I)=20$: ratio $\frac{11}{10}$, at most the guarantee $\frac43-\frac1{3m}=\frac{7}{6}$.