← Back to the site

Question bank

357 fixed questions · 16 generated questions

Fixed questions (357)

1. Principles of approximation algorithms (64)

aa-f-001 · level facile · notes
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)$?
  1. $\alpha=\frac43$
  2. $\alpha=\frac54$
  3. $\alpha=\frac34$
  4. $\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$.
aa-f-002 · level facile · notes
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)}$?
  1. $\frac56$ and $20\%$
  2. $\frac65$ and $2$
  3. $\frac56$ and $16.7\%$
  4. $\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$.
aa-f-003 · level teorema · notes
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?
  1. In both a PTAS and an FPTAS the time is polynomial for every fixed $\varepsilon$, and in neither in $\frac1\varepsilon$
  2. A time $O(n^{1/\varepsilon})$ is polynomial both in the size and in $\frac1\varepsilon$, hence it gives an FPTAS
  3. In a PTAS the time is polynomial for every fixed $\varepsilon$; in an FPTAS it is polynomial in $\frac1\varepsilon$ too
  4. 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.
aa-f-004 · level facile · notes
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?
  1. That every constant larger than $\frac32$ is a relative guarantee of $\mathscr{A}$
  2. That no constant smaller than $\frac32$ is a relative guarantee of $\mathscr{A}$
  3. That $\frac32$ is a relative guarantee of $\mathscr{A}$, valid for every instance
  4. 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.
aa-f-027 · level facile · notes
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?
  1. $4$
  2. $\frac{9}{5}$
  3. $\frac54$
  4. $\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.
aa-f-028 · level teorema · notes
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?
  1. $r(\mathscr{A})$ is always attained by some instance
  2. $\mathscr{A}$ is an $\alpha$-approximation if and only if $\alpha\ge r(\mathscr{A})$
  3. $\mathscr{A}$ is an $\alpha$-approximation if and only if $\alpha=r(\mathscr{A})$
  4. $\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.
aa-f-029 · level facile · notes
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?
  1. $\beta=2$, because $\chi(G)\ge 3$
  2. $\beta=5$, the number of colors used
  3. $\beta=\frac53$, the ratio of colors used to chromatic number
  4. $\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.
aa-f-030 · level facile · notes
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)$?
  1. $\mathscr{A}(I)/z(I)\le\beta$ for every instance
  2. $\mathscr{A}(I)/z(I)\ge 1+\beta$ for every instance
  3. Nothing: the two guarantees are independent
  4. $\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.
aa-f-031 · level facile · notes
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)$?
  1. $30\le z(I)\le 60$
  2. $z(I)\le 15$
  3. $15\le z(I)\le 30$
  4. $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.
aa-f-032 · level facile · notes
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?
  1. That it becomes exponential for every $\varepsilon<\frac12$
  2. That it grows: a smaller allowed error needs more time
  3. That it decreases: with small $\varepsilon$ there are fewer solutions to examine
  4. 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$.
aa-f-033 · level facile · notes
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?
  1. $O(n^2/\varepsilon)$
  2. $O(n^{1/\varepsilon})$
  3. $O(2^{1/\varepsilon}\,n)$
  4. $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$.
aa-f-034 · level facile · notes
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}$?
  1. From $O(n^2)$ to $O(n^{2/10})$: it decreases
  2. It stays $O(n^2)$: the exponent does not depend on $\varepsilon$
  3. It becomes exponential in $n$
  4. 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.
aa-f-090 · level facile · notes
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?
  1. Because every optimization problem has positive values
  2. Because $\mathscr{A}(I)$ must equal $z(I)$
  3. Because negative values are infeasible
  4. 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.
aa-f-125 · level facile · notes
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. $1.25$ in both cases
  2. $1.25$ and $0.8$
  3. $0.8$ and $1.25$
  4. $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.
aa-f-126 · level facile · notes
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?
  1. The ratio between the heuristic value and the optimal value
  2. The worst-case running time
  3. The difference between the optimal value and a lower bound
  4. 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.
aa-f-127 · level facile · notes
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?
  1. At least $53$
  2. At least $150$
  3. At least $47$
  4. 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.
aa-f-202 · level facile · notes
Minimization problem: the optimum is $60$ and the heuristic finds $72$. Which performance ratio does it achieve?
  1. $\frac56$
  2. $12$
  3. $\frac15$
  4. $\frac65$
Explanation. For a minimization problem the ratio is $\mathscr{A}(I)/z(I)=72/60=\frac65$: it is always at least $1$.
aa-f-203 · level facile · notes
A maximization problem has $z(I)=30$ and an algorithm $\mathscr{A}$ returns $\mathscr{A}(I)=20$. What is the performance ratio on $I$?
  1. $10$
  2. $\frac13$
  3. $\frac32$
  4. $\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$.
aa-f-204 · level facile · notes
If an algorithm $\mathscr{A}$ always returns a feasible solution, what can be said of its performance ratio on every instance?
  1. It can be negative
  2. It is at least $1$
  3. It is at most $1$
  4. 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.
aa-f-205 · level facile · notes
An algorithm for a minimization problem has $\mathscr{A}(I)\le 2z(I)$ on every instance. What can be concluded?
  1. It is a $2$-approximation algorithm
  2. It is a $2$-additive algorithm
  3. Its relative error is at most $\frac12$
  4. 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$.
aa-f-206 · level facile · notes
An algorithm for a maximization problem has $\mathscr{A}(I)\ge\frac12 z(I)$ on every instance. Which $\alpha$-approximation is it?
  1. $\alpha=\frac12$
  2. $\alpha=\frac32$
  3. None: for maximization problems $\alpha$ is less than $1$
  4. $\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.
aa-f-207 · level facile · notes
In the definition of an $\alpha$-approximation algorithm, what must hold for the constant $\alpha$?
  1. $0<\alpha<1$, for every instance
  2. $\alpha$ is the ratio on one single instance
  3. $\alpha\ge1$ and it does not depend on the instance
  4. $\alpha$ may depend on the instance $I$
Explanation. $\alpha\in[1,+\infty)$ is a constant: the same inequality must hold for all instances.
aa-f-208 · level facile · notes
What does the worst-case performance ratio $r(\mathscr{A})$ represent?
  1. The minimum of the performance ratio over instances
  2. The supremum of the performance ratio over all instances
  3. The performance ratio on the largest instance
  4. The average of the performance ratios
Explanation. $r(\mathscr{A})=\sup_I$ of the ratio: it is the smallest constant $\alpha$ for which $\mathscr{A}$ is an $\alpha$-approximation.
aa-f-209 · level facile · notes
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?
  1. That the guarantee $\frac32$ is tight
  2. That the algorithm is optimal
  3. That the problem has no approximation scheme
  4. 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$.
aa-f-210 · level facile · notes
If the heuristic value exceeds the optimum by at most one unit, on every instance of a minimization problem, which kind of algorithm is it?
  1. A relative $1$-approximation algorithm
  2. An exact algorithm on every instance
  3. A relative $2$-approximation algorithm
  4. A $1$-additive approximation algorithm
Explanation. $\mathscr{A}(I)-z(I)\le\beta$ with $\beta=1$ on every instance is the additive guarantee; it is not exact, since it may miss by one.
aa-f-211 · level facile · notes
A maximization problem has $z(I)=17$; which values can a $2$-additive algorithm return on this instance?
  1. Only $15$
  2. Any value between $\frac{17}{2}$ and $17$
  3. Any value between $15$ and $17$
  4. 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$.
aa-f-212 · level facile · notes
What is the worst-case additive error $e(\mathscr{A})$ of an algorithm for a minimization problem?
  1. $\sup_I\,(z(I)-\mathscr{A}(I))$
  2. $\sup_I\,(\mathscr{A}(I)-z(I))$
  3. $\max_I\,\mathscr{A}(I)/z(I)$
  4. $\inf_I\,(\mathscr{A}(I)-z(I))$
Explanation. It is the supremum of the difference between heuristic value and optimum; for a maximization problem the two terms are swapped.
aa-f-213 · level facile · notes
For a minimization problem, $z(I)=8$ and $\mathscr{A}(I)=10$. What are the additive error and the relative error?
  1. $2$ and $\frac14$
  2. $2$ and $\frac15$
  3. $\frac54$ and $\frac14$
  4. $\frac14$ and $2$
Explanation. Additive error $\mathscr{A}(I)-z(I)=2$; relative error $(\mathscr{A}(I)-z(I))/z(I)=2/8=\frac14$ (one divides by the optimum).
aa-f-214 · level facile · notes
For a maximization problem, $z(I)=50$ and $\mathscr{A}(I)=40$. What is the relative error?
  1. $\frac14$
  2. $\frac54$
  3. $10$
  4. $\frac15$
Explanation. The relative error always divides by the optimum: $(z(I)-\mathscr{A}(I))/z(I)=10/50=\frac15$.
aa-f-215 · level facile · notes
What is an approximation scheme for a problem $\mathscr{P}$?
  1. A pseudo-polynomial exact algorithm
  2. A family of instances on which a guarantee is tight
  3. A family of algorithms $\mathscr{A}_\varepsilon$
  4. 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.
aa-f-216 · level facile · notes
A scheme runs in time $O(n^{1/\varepsilon})$. What is it?
  1. A polynomial exact algorithm
  2. A PTAS, but not an FPTAS
  3. An FPTAS
  4. 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.
aa-f-217 · level facile · notes
To which class does an approximation scheme belong whose algorithm $\mathscr{A}_\varepsilon$ takes $O(n^3/\varepsilon)$ operations?
  1. An FPTAS (and hence also a PTAS)
  2. A PTAS but not an FPTAS
  3. An exponential algorithm
  4. A $\frac1\varepsilon$-additive algorithm
Explanation. The time is polynomial both in the size $n$ and in the accuracy $\frac1\varepsilon$: it is an FPTAS; every FPTAS is also a PTAS.
aa-f-218 · level facile · notes
What is called the «accuracy» of an approximation scheme?
  1. The relative error $\varepsilon$
  2. The ratio $1+\varepsilon$
  3. The running time
  4. 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.
aa-f-219 · level facile · notes
A scheme for a maximization problem has relative error $\varepsilon=\frac14$. Which approximation guarantee does it give?
  1. $\varepsilon=\frac14$, i.e. $\frac14$
  2. $1-\varepsilon=\frac34$
  3. $\frac{1}{1-\varepsilon}=\frac43$
  4. $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.
aa-f-220 · level teorema · notes
Which relation links the worst-case ratio $r(\mathscr{A})$ to the relative guarantees of $\mathscr{A}$?
  1. $r(\mathscr{A})=1$ for every feasible algorithm, whatever the guarantee $\alpha$
  2. It is the smallest guarantee $\alpha$, i.e. the tight one
  3. Every guarantee $\alpha$ of $\mathscr{A}$ is strictly smaller than $r(\mathscr{A})$, and no guarantee is tight
  4. $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.
aa-f-221 · level teorema · notes
An approximation scheme for a minimization problem with relative error $\varepsilon$: what does every $\mathscr{A}_\varepsilon$ guarantee?
  1. $\mathscr{A}_\varepsilon(I)\le(1+\varepsilon)z(I)$ on every instance
  2. $\mathscr{A}_\varepsilon(I)\le z(I)+\varepsilon$
  3. $\mathscr{A}_\varepsilon(I)\ge(1-\varepsilon)z(I)$
  4. $\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.
aa-f-222 · level teorema · notes
What does $e(\mathscr{A})=\infty$ mean for an algorithm $\mathscr{A}$?
  1. $\mathscr{A}$ has no finite relative guarantee
  2. $\mathscr{A}$ does not terminate
  3. $\mathscr{A}$ returns infeasible solutions
  4. $\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.
aa-f-223 · level teorema · notes
Which relation holds between the classes of approximation schemes?
  1. PTAS and FPTAS are the same thing
  2. An FPTAS is not an approximation scheme
  3. Every FPTAS is a PTAS, not conversely
  4. 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.
aa-f-224 · level ipotesi · notes
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?
  1. That the instance has a unique optimal solution
  2. That it always returns a feasible solution
  3. That $\mathscr{A}$ is polynomial
  4. 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.
aa-f-225 · level ipotesi · notes
Why does the chapter assume $z(I)>0$?
  1. Because the ratios divide by $z(I)$
  2. Because otherwise the problem has no feasible solutions
  3. Because greedy algorithms require positive weights
  4. 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.
aa-f-226 · level ipotesi · notes
An algorithm has $\mathscr{A}(I)\le 2z(I)$ on all instances except an infinite family. Is it a $2$-approximation?
  1. Yes, if the family is infinite but rare
  2. Yes: it is enough that it holds on the reference instances
  3. Yes, if $r(\mathscr{A})<\infty$ on the other instances
  4. 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$.
aa-f-227 · level ipotesi · notes
In the definition of a PTAS the running time of $\mathscr{A}_\varepsilon$ must be polynomial in the instance size: for which $\varepsilon$?
  1. Only for $\varepsilon=\frac12$
  2. For no $\varepsilon$: pseudo-polynomial is enough
  3. For every fixed $\varepsilon\in(0,1)$
  4. 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.
aa-f-228 · level ipotesi · notes
To prove that a relative guarantee $\alpha$ is tight, what is it enough to exhibit?
  1. An instance with ratio larger than $\alpha$
  2. An instance with ratio exactly $\alpha$
  3. An instance on which the algorithm is optimal
  4. 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.
aa-f-229 · level ipotesi · notes
In the definition of a $\beta$-additive algorithm, what is required of $\beta$?
  1. $\beta\ge0$ constant
  2. $\beta\ge1$
  3. $\beta$ proportional to $z(I)$
  4. $\beta$ depending on the instance size
Explanation. $\beta\in[0,+\infty)$ is a constant; if it depended on $z(I)$ or on the size it would no longer be an additive guarantee.
aa-f-316 · level teorema · notes
For a minimization problem, which relation is there between the relative error $\varepsilon(I)$ and the performance ratio $R(I)$?
  1. $R(I)=\varepsilon(I)$
  2. $R(I)=1+\varepsilon(I)$
  3. $R(I)=1-\varepsilon(I)$
  4. $R(I)=\frac{1}{1-\varepsilon(I)}$
Explanation. $\frac{\mathscr{A}(I)}{z(I)}=1+\frac{\mathscr{A}(I)-z(I)}{z(I)}$; for a maximization problem $R(I)=\frac{1}{1-\varepsilon(I)}$.
aa-f-317 · level teorema · notes
For a maximization problem, a relative error at most $\varepsilon$ is equivalent to which ratio?
  1. $\frac{z(I)}{\mathscr{A}(I)}\le\frac{1}{1-\varepsilon}$
  2. $\frac{z(I)}{\mathscr{A}(I)}\le1+\varepsilon$
  3. $\frac{\mathscr{A}(I)}{z(I)}\le1+\varepsilon$
  4. $z(I)-\mathscr{A}(I)\le\varepsilon$
Explanation. $\mathscr{A}(I)\ge(1-\varepsilon)z(I)$, i.e. $z(I)/\mathscr{A}(I)\le\frac{1}{1-\varepsilon}$, which is more than $1+\varepsilon$.
aa-f-318 · level teorema · notes
What does $r(\mathscr{A})=\infty$ mean?
  1. $\mathscr{A}$ has no additive guarantee
  2. $\mathscr{A}$ has exponential running time
  3. $\mathscr{A}$ is optimal on every instance
  4. $\mathscr{A}$ has no finite relative guarantee
Explanation. The ratio is bounded by no constant: $\mathscr{A}$ is not an $\alpha$-approximation for any $\alpha$.
aa-f-319 · level teorema · notes
An approximation scheme for a minimization problem gives, once $\varepsilon$ is chosen, which guarantee?
  1. An additive guarantee $\varepsilon$
  2. A $2$-approximation
  3. A $(1+\varepsilon)$-approximation
  4. An $\varepsilon$-approximation
Explanation. Relative error $\le\varepsilon$ means $\mathscr{A}_\varepsilon(I)\le(1+\varepsilon)z(I)$.
aa-f-320 · level ipotesi · notes
For an FPTAS the running time must be polynomial in which quantities?
  1. In the optimal value $z(I)$ and in $n$
  2. In the size and in $\frac1\varepsilon$
  3. Only in the instance size
  4. Only in the accuracy $\frac1\varepsilon$
Explanation. Polynomial in both; only in the size (for fixed $\varepsilon$) is enough for a PTAS.
aa-f-321 · level ipotesi · notes
An approximation scheme requires relative error at most $\varepsilon$: for which $\varepsilon$?
  1. For every $\varepsilon\in(0,1)$
  2. For a single fixed $\varepsilon$
  3. Only for $\varepsilon\ge\frac12$
  4. For $\varepsilon=0$
Explanation. The family contains an algorithm for every $\varepsilon\in(0,1)$: the precision is chosen at will.
aa-f-322 · level ipotesi · notes
Does the additive guarantee, unlike the relative one, require $z(I)>0$?
  1. Yes, always
  2. Yes, only for maximization problems
  3. Yes, and also $\mathscr{A}(I)>0$
  4. No: it compares a difference
Explanation. $\mathscr{A}(I)-z(I)\le\beta$ makes sense also with zero or negative values; positivity is needed for ratios.
aa-f-323 · level ipotesi · notes
Is $r(\mathscr{A})=\frac32$ enough to say that $\mathscr{A}$ is a $\frac32$-approximation?
  1. No: $r(\mathscr{A})<\frac32$ is needed
  2. Only for minimization problems
  3. Yes: every ratio is at most the supremum
  4. No: an instance with ratio $\frac32$ is also needed
Explanation. Every ratio is $\le\sup=\frac32$, even if no instance attains it exactly.
aa-f-336 · level facile · notes
What is $z(I)/\mathscr{A}(I)$ if, in a maximization problem, $z(I)=45$ and the heuristic solution is worth $36$?
  1. $\frac15$
  2. $\frac54$
  3. $\frac45$
  4. $9$
Explanation. For a maximization problem the ratio is $z(I)/\mathscr{A}(I)=45/36=\frac54$.
aa-f-337 · level facile · notes
A $3$-approximation algorithm for a minimization problem, on an instance with $z(I)=12$, which values can it return?
  1. From $12$ to $36$
  2. From $4$ to $12$
  3. From $12$ to $15$
  4. Only $36$
Explanation. $z(I)\le\mathscr{A}(I)\le3z(I)$: between $12$ and $36$.
aa-f-338 · level facile · notes
Maximization, optimum $18$: within which interval is the value found by a $2$-approximation?
  1. From $18$ to $36$
  2. From $16$ to $18$
  3. Only $9$
  4. From $9$ to $18$
Explanation. $z(I)/\mathscr{A}(I)\le2$ and $\mathscr{A}(I)\le z(I)$: between $9$ and $18$.
aa-f-339 · level facile · notes
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. $1$
  2. $\frac{23}{18}$
  3. $\frac32$
  4. $\frac43$
Explanation. $r(\mathscr{A})$ is the supremum of the ratios over all instances, not the average: $\frac32$.
aa-f-340 · level facile · notes
An algorithm always errs by at most $3$ units and on one instance errs by exactly $3$. What is $e(\mathscr{A})$?
  1. $0$
  2. $3$
  3. $4$
  4. $\frac13$
Explanation. The additive guarantee $3$ is attained: it is the smallest possible, hence $e(\mathscr{A})=3$.
aa-f-341 · level facile · notes
A scheme for a minimization problem with $\varepsilon=0.1$ guarantees which value on an instance with $z(I)=50$?
  1. At most $55$
  2. At most $50.1$
  3. At least $45$
  4. Exactly $50$
Explanation. Relative error $\le0.1$: $\mathscr{A}_\varepsilon(I)\le1.1\cdot50=55$.
aa-f-342 · level facile · notes
A scheme runs in time $O(2^{1/\varepsilon}n^2)$. What is it?
  1. An FPTAS, hence a PTAS
  2. Neither a PTAS nor an FPTAS
  3. A polynomial exact algorithm
  4. A PTAS, not an FPTAS
Explanation. For fixed $\varepsilon$ the time is polynomial in $n$; the dependence on $\frac1\varepsilon$ is exponential, hence not an FPTAS.
aa-f-343 · level facile · notes
What does one confuse when calling «$\varepsilon$-approximation» a scheme with relative error $\varepsilon$?
  1. Minimization with maximization
  2. Running time with space
  3. The error with the ratio
  4. The PTAS with the FPTAS
Explanation. A relative error $\varepsilon$ gives ratio $1+\varepsilon$ (minimization) or $\frac{1}{1-\varepsilon}$ (maximization), never $\varepsilon<1$.
aa-f-344 · level teorema · notes
If $\mathscr{A}$ is an $\alpha$-approximation and $\alpha'>\alpha$, what can be said?
  1. $\mathscr{A}$ is exact
  2. It is also an $\alpha'$-approximation
  3. $\mathscr{A}$ is not an $\alpha'$-approximation
  4. $r(\mathscr{A})=\alpha'$
Explanation. If the ratio is always $\le\alpha$, it is also $\le\alpha'$: all weaker guarantees hold.
aa-f-345 · level teorema · notes
Is a $\beta$-additive algorithm for a minimization problem with $z(I)\ge1$ on every instance also relative?
  1. Yes, a $(1+\beta)$-approximation
  2. No, never, for no $\beta$
  3. Yes, a $\beta$-approximation
  4. Only if $\beta=0$, i.e. exact
Explanation. $\mathscr{A}(I)\le z(I)+\beta\le z(I)+\beta z(I)=(1+\beta)z(I)$ if $z(I)\ge1$.
aa-f-346 · level ipotesi · notes
To derive from an additive guarantee $\beta$ the relative guarantee $1+\beta$ (minimization), which assumption is needed?
  1. $\beta<1$ and $\beta>0$
  2. That $\mathscr{A}$ is polynomial
  3. No assumption
  4. $z(I)\ge1$ on every instance
Explanation. One needs $\beta\le\beta z(I)$, i.e. $z(I)\ge1$; with tiny optima the relative error can be huge.
aa-f-347 · level ipotesi · notes
Over which instances is the worst-case ratio $r(\mathscr{A})$ computed?
  1. Over those with large $n$
  2. Over a single instance
  3. Over all instances of the problem
  4. Over the reference instances
Explanation. It is a supremum over all instances: a worst-case measure, not an average one.

2. Approximation algorithms for the knapsack problem (50)

aa-f-005 · level teorema · notes
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?
  1. $GR$, $GR^e$ and $H^2$ all have ratio $2$
  2. $GR$ has no constant guarantee, $GR^e$ has $r(GR^e)=2$, $H^2$ has $r(H^2)=\frac43$
  3. $GR$ has $r(GR)=2$ and $GR^e$ has $r(GR^e)=\frac43$
  4. $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.
aa-f-006 · level ipotesi · notes
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$?
  1. $z(I)\le\sum_{i<s}p_i+p_s$; $GR(I)\ge\sum_{i<s}p_i$; $p_{\max}\ge p_s$
  2. $z(I)\le\sum_{i<s}p_i+p_s$; $GR(I)\ge\sum_{i<s}p_i$; $p_{\max}\le p_s$
  3. $z(I)\le\sum_{i<s}p_i$; $GR(I)\ge\sum_{i\le s}p_i$; $p_{\max}\ge p_s$
  4. $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$.
aa-f-007 · level facile · notes
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$?
  1. $\frac43$
  2. $\frac32$
  3. $\frac65$
  4. $\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.
aa-f-008 · level facile · notes
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?
  1. There is a polynomial algorithm with absolute guarantee $p_{\max}$, the maximum profit of an item
  2. There is a polynomial algorithm with absolute guarantee $1$, obtained by rounding the Dantzig bound
  3. An algorithm with absolute guarantee $k$ and time $O(f(n,c))$ would solve every instance optimally in the same time
  4. 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.
aa-f-035 · level facile · notes
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}$?
  1. $s=2$, $\mathit{rc}=0$
  2. $s=3$, $\mathit{rc}=3$
  3. $s=4$, $\mathit{rc}=0$
  4. $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.
aa-f-036 · level facile · notes
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?
  1. Because otherwise the split item would be the first one
  2. Because otherwise the greedy does not terminate
  3. Otherwise all items fit, there is no split item and taking them all is optimal
  4. 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.
aa-f-037 · level facile · notes
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)$?
  1. $28$
  2. $23$
  3. $21$
  4. $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$.
aa-f-038 · level teorema · notes
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)$?
  1. $\frac M2$, which grows without bound with $M$
  2. $2$, for every $M$
  3. $1$: $GR$ is optimal
  4. $\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.
aa-f-039 · level facile · notes
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)$?
  1. $2$, the value of $GR$
  2. $M+2$, the sum of the profits
  3. $\frac M2$
  4. $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.
aa-f-040 · level facile · notes
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?
  1. All items equal: $GR^e$ is always optimal
  2. A single item: the ratio is $1$
  3. $c=2M$ and three items $(2,1)$, $(M,M)$, $(M,M)$: $GR^e$ is about $M$, the optimum $2M$
  4. $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$.
aa-f-041 · level facile · notes
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?
  1. On the items with profit larger than $\max\{p_i,p_k\}$
  2. On the other items with profit at most $\min\{p_i,p_k\}$ and weight at most the residual capacity
  3. On all the other items, whatever their profit
  4. 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}$.
aa-f-042 · level facile · notes
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?
  1. $O(n^3)$, and $O(n^2)$ with a more careful implementation
  2. $O(n\log n)$, as the greedy
  3. $O(2^n)$, because it tries subsets
  4. $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$.
aa-f-043 · level facile · notes
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$?
  1. $\frac54$ and $O(n^4)$
  2. $\frac65$ and $O(n^4)$
  3. $\frac43$ and $O(n^5)$
  4. $\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$.
aa-f-044 · level facile · notes
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?
  1. $\ell=8$ and ratio $\frac98$
  2. $\ell=9$ and ratio $\frac{11}{10}$
  3. $\ell=8$ and ratio $\frac{10}{9}$
  4. $\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.
aa-f-045 · level facile · notes
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?
  1. Ratio at most $5$, relative error at most $80\%$
  2. Ratio at most $\frac54$, relative error at most $20\%$
  3. Ratio at most $\frac65$, relative error at most $20\%$
  4. 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.
aa-f-046 · level facile · notes
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$?
  1. The scaled profits are small (of order $n/\varepsilon$), and the DP by profits costs in proportion to the total profit
  2. Because the DP on the capacity does not depend on the profits
  3. Because the scaled instance has fewer items
  4. 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.
aa-f-047 · level ipotesi · notes
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?
  1. Divide all profits by $k$ and round down
  2. Add $k$ dummy items of zero profit
  3. Reduce the capacity by $k$ units
  4. 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.
aa-f-091 · level facile · notes
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?
  1. $\mathscr{A}(I)\ge z(I)$ and $\mathscr{A}(I)/z(I)\ge1$
  2. $\mathscr{A}(I)=z(I)$
  3. $\mathscr{A}(I)\le z(I)$ and $\mathscr{A}(I)/z(I)\ge1$
  4. $\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$.
aa-f-092 · level facile · notes
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?
  1. It is enough to try the pairs of lightest items
  2. The best pair is always the one of maximum total profit
  3. 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
  4. 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.
aa-f-093 · level teorema · notes
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)$?
  1. $(\vartheta+2)/\vartheta$
  2. $\vartheta/2$, which grows without bound: $GR$ has no constant guarantee
  3. $2$, for every $\vartheta$
  4. $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.
aa-f-094 · level facile · notes
Why can the greedy $GR$ by efficiency be arbitrarily far from the optimum of the 0/1 knapsack?
  1. A small and very efficient item can take the capacity that a large and profitable item would need
  2. Because $GR$ does not respect the capacity
  3. Because $GR$ sorts the items by weight
  4. 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\}$.
aa-f-095 · level teorema · notes
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. $1$
  2. $\frac{\vartheta}{2}$
  3. $\frac32$
  4. $\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$.
aa-f-096 · level teorema · notes
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?
  1. It is smaller than $1$
  2. It tends to $2$
  3. It tends to $\frac43$ as $M\to\infty$
  4. 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$.
aa-f-097 · level facile · notes
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)?
  1. $z=40$, $H^2=22$
  2. $z=40$, $H^2=32$
  3. $z=40$, $H^2=40$
  4. $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$.
aa-f-098 · level facile · notes
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$?
  1. $\frac43$ and $\frac65$
  2. $\frac32$ and $\frac54$
  3. $2$ and $\frac43$
  4. $\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.
aa-f-099 · level teorema · notes
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?
  1. Because the time is exponential in $n$ for every $\varepsilon$
  2. Because it does not guarantee relative error $\varepsilon$
  3. It is also an FPTAS
  4. 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)$.
aa-f-100 · level facile · notes
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$?
  1. $n^2$
  2. $n^6$
  3. $n^4$, because $\ell=5-2=3$
  4. $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.
aa-f-101 · level teorema · notes
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?
  1. $FP^{\varepsilon}(I)\ge z(I)-\varepsilon$
  2. $FP^{\varepsilon}(I)\ge(1-\varepsilon)\,z(I)$
  3. $FP^{\varepsilon}(I)=z(I)$
  4. $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)$.
aa-f-102 · level ipotesi · notes
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?
  1. The guarantee $z(I)\le2\,GR^e(I)$ of Ext-Greedy bounds the optimal scaled value by $2n/\varepsilon$
  2. The fact that the scaled profits are at most $1$
  3. The fact that always $n\le Q$
  4. 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$.
aa-f-103 · level facile · notes
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$?
  1. $20$
  2. $100$
  3. $2000$
  4. $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.
aa-f-124 · level facile · notes
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?
  1. All have ratio $2$
  2. $GR$: $\frac43$; $GR^e$: no constant; $H^2$: $2$; $H^{\ell}$: $\frac{\ell+1}{\ell}$
  3. $GR$: no constant; $GR^e$: $2$; $H^2$: $\frac43$; $H^{\ell}$: $\frac{\ell+2}{\ell+1}$
  4. $GR$: $2$; $GR^e$: $\frac43$; $H^2$: $\frac32$; $H^{\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.
aa-f-128 · level facile · notes
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$?
  1. Because every item weighs more than $c/2$
  2. It does not always exist: it depends on the profits
  3. Adding the items in order, sooner or later the weight exceeds $c$
  4. 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.
aa-f-129 · level teorema · notes
In the 0/1 knapsack (items sorted by efficiency, critical item $s$) $z(I)\le\sum_{j<s}p_j+p_s$ holds. Why?
  1. Because $p_s$ is the maximum profit
  2. Because $z(I)\le z(\mathrm{LP})\le\sum_{j<s}p_j+p_s$
  3. Because the optimum always contains the critical item
  4. Because the items after $s$ never fit in the knapsack
Explanation. $z(\mathrm{LP})=\sum_{j<s}p_j+\mathit{rc}\,p_s/w_s$ and $\mathit{rc}<w_s$. It is the first step of the guarantee $2$ of Ext-Greedy.
aa-f-130 · level facile · notes
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$?
  1. $16$
  2. $14$
  3. $19$
  4. $13$
Explanation. It takes $(8,4)$ and $(6,3)$ (weight $7$), skips $(5,5)$, takes $(2,2)$: $16$. $14$ stops at the critical item.
aa-f-131 · level facile · notes
How much time does the greedy algorithm $GR$ for the 0/1 knapsack with $n$ items take, including the sorting by efficiency?
  1. $O(n)$
  2. $O(n^2)$
  3. $O(nc)$
  4. $O(n\log n)$
Explanation. Sorting costs $O(n\log n)$ and the scan $O(n)$. $O(nc)$ is the pseudo-polynomial time of dynamic programming.
aa-f-132 · level facile · notes
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?
  1. $GR=2$, Ext-Greedy $=12$
  2. $GR=12$, Ext-Greedy $=12$
  3. $GR=2$, Ext-Greedy $=10$
  4. $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.
aa-f-133 · level teorema · notes
For Ext-Greedy ($GR^e=\max\{GR,p_{\max}\}$) $z(I)/GR^e(I)\le2$ holds. Which chain of inequalities proves it ($s$ critical item)?
  1. $z\le\sum_jp_j$ and $\sum_jp_j\le2\,GR^e$
  2. $z\le\sum_{j<s}p_j+p_s\le GR+p_{\max}\le2\,GR^e$
  3. $z\le GR+p_s$ and $p_s\le GR$, hence $z\le2\,GR$
  4. $z\le n\,p_{\max}$ and $n\,p_{\max}\le2\,GR^e$
Explanation. $GR$ takes at least the items before $s$, and $p_s\le p_{\max}$; both terms are at most $GR^e$.
aa-f-134 · level teorema · notes
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?
  1. They are consistent with the guess on $i$ and $k$
  2. Because the other items are always heavier
  3. To make the residual greedy solution optimal
  4. 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.
aa-f-135 · level facile · notes
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$?
  1. $O(n^3)$
  2. $O(3n)$
  3. $O(2^n)$
  4. $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$.
aa-f-136 · level facile · notes
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?
  1. $O(nc)$
  2. $O(2^n)$
  3. $O(n)$
  4. $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.
aa-f-137 · level facile · notes
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$?
  1. $K=0.5$, $p'_j=74$
  2. $K=2$, $p'_j=18$
  3. $K=2$, $p'_j=18.5$
  4. $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.
aa-f-138 · level teorema · notes
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?
  1. Weights and capacity do not change: the constraints are the same
  2. Because the scaled profits are smaller than the original ones
  3. Because the weights are scaled by the same factor too
  4. 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.
aa-f-139 · level facile · notes
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?
  1. At least $\frac43$ of $z(I)$
  2. At most $\frac34$ of $z(I)$
  3. At least $\frac13$ of $z(I)$
  4. 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.
aa-f-140 · level teorema · notes
For Ext-Greedy one proves $z(I)/GR^e(I)\le2$ and then that there are instances with $z(I)/GR^e(I)\to2$. What is the second proposition for?
  1. To prove the first proposition
  2. To show that the average ratio is $2$
  3. To show that $2$ cannot be lowered
  4. To show that Ext-Greedy is optimal on those instances
Explanation. A guarantee is tight if it cannot be lowered; a family of instances whose ratio tends to $2$ proves it.
aa-f-141 · level teorema · notes
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?
  1. $c$: because $GR$ is worth only $1$
  2. $c/2$: the ratio of $GR$ is unbounded
  3. $2$: it is exactly the worst case of $GR$
  4. $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.
aa-f-142 · level facile · notes
For the algorithm $H^2$ of the knapsack $z(I)/H^2(I)\le\frac43$ holds. On an instance with $z(I)=120$, which minimum value does $H^2$ guarantee?
  1. $90$
  2. $80$
  3. $60$
  4. $100$
Explanation. $H^2\ge\frac34\cdot120=90$. $60$ is the guarantee of Ext-Greedy ($\frac12z$); $80$ would use the factor $\frac23$.
aa-f-143 · level facile · notes
For the algorithm $H^{\ell}$ of the knapsack $z(I)/H^{\ell}(I)\le\frac{\ell+2}{\ell+1}$ holds (tight). Which guarantee does $\ell=4$ give?
  1. $\frac54$
  2. $\frac43$
  3. $\frac76$
  4. $\frac65$
Explanation. $\frac{4+2}{4+1}=\frac65$. With $\ell=2$ one gets back $\frac43$, the ratio of $H^2$.
aa-f-144 · level facile · notes
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?
  1. $\ell=8$, time $O(n^2/\varepsilon)$
  2. $\ell=1$, time $O(n^2)$
  3. $\ell=8$, time $O(n^9)$
  4. $\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.
aa-f-145 · level teorema · notes
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?
  1. Increase the capacity by $k$
  2. Multiply the profits by $k+1$
  3. Divide the profits by $k$ and round
  4. 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.
aa-f-146 · level facile · notes
The 0/1 knapsack is NP-hard. If $P\neq NP$, which kind of guarantee does it admit in polynomial time?
  1. Only relative, up to an FPTAS
  2. Only absolute, with constant error $k$
  3. Both, relative and absolute
  4. 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).

3. Approximation algorithms for bin packing (42)

aa-f-009 · level teorema · notes
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)$?
  1. $r(NF)=r(WF)=2$ and $r(FF)=r(BF)=\frac{17}{10}$
  2. $r(NF)=2$ and $r(WF)=r(FF)=r(BF)=\frac{17}{10}$
  3. $r(NF)=r(WF)=r(FF)=r(BF)=2$
  4. $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}$.
aa-f-010 · level ipotesi · notes
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?
  1. 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
  2. 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
  3. The items are sorted by non-increasing weight; $z(I)\ge\lceil\sum_i w_i/c\rceil$; $k$ is an integer
  4. 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)$.
aa-f-011 · level ipotesi · notes
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$)?
  1. The items are sorted by non-increasing weight, hence the first bins are full
  2. The number of bins is at most $\frac{17}{10}z(I)$, hence few bins are empty
  3. The content of two bins never fits into one, whatever the bin selection rule
  4. 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$.
aa-f-012 · level facile · notes
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?
  1. It may exceed the capacity of the open bin
  2. It may open a bin for an item that would fit into a closed bin
  3. It sorts the items by non-increasing weight before packing them
  4. 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.
aa-f-048 · level facile · notes
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?
  1. NF $4$, FF $2$
  2. NF $3$, FF $2$
  3. NF $2$, FF $2$
  4. 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.
aa-f-049 · level facile · notes
In bin packing with $n$ items, Next Fit (NF) keeps a single bin open at a time. How much time does it take, and why?
  1. $O(n)$: every item is compared only with the open bin
  2. $O(n^2)$: every item is compared with all bins
  3. $O(n\log n)$: the items must be sorted
  4. $O(2^n)$: all partitions are tried
Explanation. One check per item: if it fits it goes into the open bin, otherwise a new bin is opened. The speed is paid with poorly filled bins.
aa-f-050 · level facile · notes
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?
  1. FF in the $1$st, BF in the $1$st, WF in the $2$nd
  2. FF in the $3$rd, BF in the $3$rd, WF in the $2$nd
  3. FF in the $2$nd, BF in the $2$nd, WF in the $3$rd
  4. 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.
aa-f-051 · level facile · notes
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)?
  1. Yes, but only with Worst Fit
  2. No, because the total load $15$ is not a multiple of $c$
  3. No: two bins have load at most $5$, and the content of the second would have fitted into the first
  4. 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.
aa-f-052 · level ipotesi · notes
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?
  1. The content of any two bins does not fit into one
  2. Two consecutive NF bins together weigh more than $c$
  3. Every NF bin weighs more than $c/2$
  4. 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$.
aa-f-053 · level facile · notes
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?
  1. $5$
  2. $6$
  3. $4$
  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)$.
aa-f-054 · level facile · notes
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?
  1. Worst Fit is not an Any Fit algorithm
  2. First Fit and Best Fit violate the half-full property
  3. The guarantees depend only on the order of the items
  4. 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.
aa-f-055 · level facile · notes
Next Fit (NF) for bin packing has worst-case ratio $r(NF)=2$. Which kind of instance approaches it?
  1. Items sorted by non-increasing weight
  2. Items all of weight $1$, with large $c$
  3. Items alternating weight about $c/2$ and very small weight: NF closes every bin half empty
  4. 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.
aa-f-104 · level facile · notes
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?
  1. $\mathscr{A}(I)/z(I)\le1$
  2. $\mathscr{A}(I)/z(I)\ge1$
  3. $z(I)/\mathscr{A}(I)\ge1$
  4. $\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.
aa-f-105 · level facile · notes
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?
  1. Next Fit: it closes the bin as soon as an item does not fit, even if the item would fit in an earlier one
  2. First Fit: it chooses the first bin
  3. Best Fit: it chooses the fullest bin
  4. 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.
aa-f-106 · level teorema · notes
In a solution produced by an Any Fit algorithm for bin packing, any two bins have together weight greater than $c$. Why?
  1. Because every bin is more than half full by construction of the choice rule
  2. Because the items are sorted by weight
  3. It is not true for Worst Fit
  4. 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.
aa-f-107 · level facile · notes
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?
  1. $2$, with loads $(9,9)$
  2. $4$, with loads $(6,5,4,3)$
  3. $2$, with loads $(10,8)$
  4. $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$).
aa-f-108 · level facile · notes
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)?
  1. Into a new bin
  2. Into bin $2$, which becomes full
  3. Into bin $1$, the first where it fits
  4. 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$.
aa-f-109 · level facile · notes
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?
  1. Ratio $2$, tight; First Fit has asymptotic ratio $\frac{17}{10}$
  2. Ratio $\frac{17}{10}$, as First Fit
  3. Ratio $\frac32$
  4. 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}$.
aa-f-110 · level teorema · notes
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)$?
  1. That no Any Fit algorithm has ratio below $2$
  2. That Worst Fit is not Any Fit
  3. That First Fit has ratio $2$
  4. 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}$.
aa-f-111 · level facile · notes
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?
  1. $200$
  2. $150$
  3. $170$
  4. $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.
aa-f-112 · level ipotesi · notes
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?
  1. Next Fit has guarantee $\frac{17}{10}$
  2. Next Fit still keeps $NF(I)\le2z(I)$, because two consecutive bins together exceed $c$
  3. Next Fit loses every constant guarantee
  4. 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.
aa-f-152 · level facile · notes
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. $(1,2,2,3,4,5)$
  2. $(1,2,2,3,4,4)$
  3. $(1,2,1,3,4,1)$
  4. $(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.
aa-f-153 · level facile · notes
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?
  1. $P_3=\{4,5,6\}$, weight $8$
  2. $P_3=\{3\}$, weight $8$
  3. $P_3=\{3,4,5\}$, weight $14$
  4. $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$.
aa-f-154 · level facile · notes
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?
  1. It opens a new bin and puts it there
  2. It puts it into the first closed bin where it fits
  3. It discards it and moves to the next item
  4. 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.
aa-f-155 · level facile · notes
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?
  1. $4$, with loads $(5,10,6,6)$
  2. $4$, with loads $(10,7,4,6)$
  3. $3$, with loads $(10,7,10)$
  4. $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$.
aa-f-156 · level facile · notes
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?
  1. Always the last bin opened so far
  2. The first bin (in order of opening) where it fits
  3. The order of the items, scanned by non-increasing weight
  4. 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.
aa-f-157 · level facile · notes
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. $(1,2,2,1,3)$
  2. $(1,2,1,2,3)$
  3. $(1,2,2,3,3)$
  4. $(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.
aa-f-158 · level facile · notes
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?
  1. Into bin $2$
  2. Into bin $3$
  3. Into bin $4$
  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.
aa-f-159 · level facile · notes
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?
  1. Both $2$
  2. Both $3$
  3. FF $3$, WF $2$
  4. 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.
aa-f-160 · level facile · notes
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?
  1. Scan the heaviest items before the others
  2. Avoid residuals too small for future items
  3. Fill every open bin as much as possible
  4. 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.
aa-f-161 · level facile · notes
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?
  1. $6$, and it does not: three bins have load $2$
  2. $6$, and it does: two consecutive bins exceed $10$
  3. $4$, and it does: a single bin has load $\le5$
  4. $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)$.
aa-f-162 · level facile · notes
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?
  1. For every pair of bins, together they weigh more than $c$
  2. Every bin, without exception, weighs more than $c/2$
  3. At most one bin is not completely filled
  4. 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.
aa-f-163 · level facile · notes
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?
  1. No, it does not; and yes, they can be merged
  2. No, it does not; and they cannot be merged
  3. Yes, it does; and yes, they can be merged
  4. 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$.
aa-f-164 · level teorema · notes
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)$?
  1. From $\sum_iw_i\le c$, which holds for every instance
  2. From $k-1<2z(I)$, since $k$ and $z(I)$ are integers
  3. From $k<2z(I)$, dividing by $\frac c2$
  4. 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.
aa-f-165 · level ipotesi · notes
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?
  1. Yes: the proof uses only the property of the solution
  2. No: the proof uses the Any Fit condition
  3. Yes, but only in the limit $z(I)\to\infty$
  4. 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.
aa-f-166 · level facile · notes
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?
  1. $NF=10$, $z=5$, ratio $2$
  2. $NF=20$, $z=6$, ratio $\frac{10}3$
  3. $NF=10$, $z=10$, ratio $1$
  4. $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$.
aa-f-167 · level facile · notes
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)$?
  1. $7$
  2. $2$
  3. $4$
  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$.
aa-f-168 · level teorema · notes
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?
  1. Because the small items all end up in the first opened bin
  2. Every small item goes into the new bin, left with residual $\frac n2-2$
  3. Because two items of weight $\frac n2$ together exceed the capacity $c=n$
  4. 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.
aa-f-169 · level facile · notes
In bin packing Next Fit and Worst Fit have the same worst-case ratio, $r(NF)=r(WF)=2$. Are they therefore equivalent?
  1. No: only NF can leave many bins half full or less
  2. Yes: the same ratio means the same solutions
  3. No: WF uses fewer bins than NF on every instance
  4. 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.
aa-f-170 · level facile · notes
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?
  1. The factor went down from $2$ to $\frac{17}{10}$
  2. The result now also holds for Worst Fit
  3. The result now holds only with sorted items
  4. 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$.
aa-f-171 · level teorema · notes
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?
  1. It is at most $\frac{17}{10}$, like First Fit
  2. Nothing: the Any Fit condition gives no guarantee
  3. It lies between $\frac{17}{10}$ and $2$
  4. 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.
aa-f-172 · level facile · notes
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$?
  1. The additive constant $+2$ of the First Fit bound
  2. The rule for choosing among the bins where the item fits
  3. The order in which the items are scanned
  4. 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).

4. Vertex coloring: limits of approximation (59)

aa-f-013 · level teorema · notes
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?
  1. It has a $(\Delta(G)+1)$-approximation for every graph, $DSATUR$
  2. It has no polynomial $\alpha$-approximation for any constant $\alpha\ge 1$
  3. It has a polynomial $\frac43$-approximation, but none below $\frac43$
  4. 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)$.
aa-f-014 · level ipotesi · notes
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:
  1. that deciding whether $\chi(G)\le 3$ is NP-complete, and that the number of colors is an integer
  2. that deciding whether $\chi(G)\le 2$ is NP-complete, and that the number of colors is an integer
  3. that deciding whether $\chi(G)\le 4$ is NP-complete, and that planar graphs have $\chi(G)\le 4$
  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.
aa-f-015 · level facile · notes
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?
  1. By non-increasing right endpoint $b_v$
  2. By non-increasing length $b_v-a_v$
  3. With any vertex order
  4. 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.
aa-f-016 · level facile · notes
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?
  1. $O(2^n)$: the problem is NP-complete
  2. $O(nm)$, with a shortest path from every vertex
  3. $O(n+m)$, with a breadth-first search
  4. $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.
aa-f-056 · level ipotesi · notes
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$?
  1. It would use $2$ colors, contradicting $\chi(G)=3$
  2. It would not terminate, because the problem is NP-hard
  3. It would use fewer than $4$ colors, i.e., $3$: it would decide in polynomial time whether $\chi(G)\le 3$
  4. 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.
aa-f-057 · level facile · notes
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?
  1. Because with $2$ colors the greedy coloring is always optimal
  2. Deciding whether $\chi(G)\le 2$ is polynomial (bipartite graphs), so no contradiction arises
  3. Because no graph has $\chi(G)=2$
  4. Because $\frac32>\frac43$
Explanation. The argument needs an NP-complete decision problem; 2-colorability is decided by breadth-first search in $O(n+m)$.
aa-f-058 · level facile · notes
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$)?
  1. Ratio at most $n$; no polynomial algorithm guarantees $n^{1-\varepsilon}$ for any $\varepsilon>0$
  2. Ratio at most $2$; no polynomial algorithm guarantees less than $2$
  3. Ratio at most $\Delta+1$; no polynomial algorithm guarantees less than $\frac43$
  4. 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.
aa-f-059 · level facile · notes
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?
  1. $30$
  2. $45$
  3. $27$
  4. $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.
aa-f-060 · level facile · notes
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?
  1. None: planar graphs are as hard as all others
  2. Additive: $PL(I)-\chi(G)\le 0$, i.e., $PL$ is exact
  3. Additive: $PL(I)-\chi(G)\le 2$, recognizing separately the graphs with $\chi(G)\le 2$
  4. 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$.
aa-f-061 · level facile · notes
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?
  1. Exactly $1$: on these graphs it is optimal
  2. At most $2$, because it uses at most $4$ colors and $\chi(G)\ge 2$
  3. At most $4$, because it uses at most $4$ colors and $\chi(G)\ge 1$
  4. 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.
aa-f-062 · level facile · notes
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?
  1. $3$
  2. $4$
  3. $2$
  4. $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)$.
aa-f-063 · level facile · notes
Zuckerman's theorem excludes, if $P\neq NP$, the ratios $n^{1-\varepsilon}$ for coloring. Why does it also exclude every constant ratio $\alpha$?
  1. Because every constant is below $\frac43$
  2. Because constant ratios hold only on planar graphs
  3. It does not: $\alpha$-approximations with large $\alpha$ exist
  4. 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.
aa-f-113 · level facile · notes
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?
  1. $\omega(G)/\mathscr{A}(I)$
  2. $\mathscr{A}(I)/\chi(G)\ge1$
  3. $\chi(G)/\mathscr{A}(I)\ge1$
  4. $\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.
aa-f-114 · level facile · notes
The Petersen graph has $n=10$, $m=15$, maximum degree $\Delta=3$ and contains cycles of length $5$. Which consequences does this have for coloring?
  1. It is not bipartite, hence $\chi\ge3$; the bound $\Delta+1$ gives $\chi\le4$
  2. It is bipartite, hence $\chi=2$
  3. $\chi=\Delta+1=4$ always
  4. $\chi=n/2=5$
Explanation. An odd cycle prevents $2$-coloring; greedy coloring guarantees at most $\Delta+1=4$ colors. Actually $\chi=3$.
aa-f-123 · level facile · notes
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?
  1. Complete graphs: $2$ colors are needed
  2. Graphs with a triangle: $3$ colors suffice
  3. All graphs with $n\le100$
  4. 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.
aa-f-173 · level facile · notes
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?
  1. Exact on bounded degree and interval; guarantee on bipartite and planar
  2. Exact on bipartite and interval; guarantee on bounded degree and planar
  3. Exact on all four classes
  4. 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.
aa-f-174 · level facile · notes
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?
  1. The theorem is about all graphs; the hard ones are not bipartite
  2. Because on bipartite graphs the chromatic number is $\chi(G)=1$
  3. Because the theorem holds only under $P=NP$
  4. 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$.
aa-f-175 · level facile · notes
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?
  1. $\{4,6\}$: a closed walk of length $6$, hence $\chi\ge3$
  2. None: the graph is bipartite and $\chi=2$
  3. $\{5,6\}$: a closed walk of length $4$, hence $\chi\ge3$
  4. $\{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.
aa-f-176 · level facile · notes
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?
  1. Exactly $3$
  2. It depends on the maximum degree $\Delta(G)$
  3. Exactly $2$
  4. $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.
aa-f-177 · level facile · notes
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$?
  1. $2$ colors with every order; $\Delta+1=9$
  2. $2$ colors with every order; $\Delta+1=10$
  3. $10$ colors with every order; $\Delta+1=10$
  4. 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$.
aa-f-178 · level teorema · notes
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?
  1. Complete graphs and odd cycles; for the others $\chi(G)\le\Delta(G)$
  2. Trees and even cycles; for the others $\chi(G)\le\Delta(G)-1$
  3. Planar graphs; for the others $\chi(G)\le4$
  4. 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.
aa-f-179 · level teorema · notes
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$?
  1. On planar graphs there is an exact algorithm, but not polynomial in $n$
  2. The minimum possible additive error on planar graphs is $2$
  3. On planar graphs no algorithm has a constant ratio
  4. 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$.
aa-f-180 · level ipotesi · notes
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$?
  1. Because the graph $G-v$ then becomes bipartite
  2. Because every planar graph has maximum degree at most $5$
  3. Its neighbors use at most $5$ colors; if all, a swap frees one
  4. 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).
aa-f-181 · level facile · notes
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?
  1. By non-increasing number of intersections (degree)
  2. By non-decreasing left endpoint $a_v$
  3. In any order: on interval graphs it is always optimal
  4. 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.
aa-f-182 · level facile · notes
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?
  1. Optimality is guaranteed only with the left-endpoint order
  2. The chromatic number of this graph is $\chi(G)=4$
  3. The given graph is not an interval graph
  4. 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$).
aa-f-230 · level facile · notes
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$)?
  1. Deciding whether $\chi(G)\le3$
  2. Deciding whether $\chi(G)\le2$
  3. Deciding whether $G$ is planar
  4. 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.
aa-f-231 · level facile · notes
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. $1+\varepsilon$
  2. $\log n$
  3. $\frac43-\varepsilon$
  4. $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}$.
aa-f-232 · level facile · notes
When is a graph $G=(V,E)$ called bipartite?
  1. If $\omega(G)=2$, i.e. it has an edge
  2. If every vertex has degree exactly $2$
  3. If $\chi(G)\le2$
  4. If it has an even number of vertices
Explanation. Bipartite means colorable with two colors: the two color classes are stable sets.
aa-f-233 · level facile · notes
With which complexity can one decide whether $\chi(G)\le2$ (and find a $2$-coloring if it exists)?
  1. It is not known in polynomial time
  2. $O(n+m)$, with a breadth-first search
  3. $O(2^n)$, trying all partitions
  4. $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.
aa-f-234 · level facile · notes
A graph has maximum degree $\Delta(G)=5$. At most how many colors does the greedy coloring use, with any order of the vertices?
  1. $6$
  2. $5$
  3. $10$
  4. It depends on the order, without bound
Explanation. When greedy colors a vertex, its already colored neighbours are at most $\Delta(G)$: one of the colors $1,\dots,\Delta(G)+1$ is free.
aa-f-235 · level facile · notes
At most how many edges can a simple planar graph with $n=10$ vertices have?
  1. $27$
  2. $30$
  3. $45$
  4. $24$
Explanation. For $n\ge3$ a planar graph has $m\le3n-6=24$; $45=\binom{10}{2}$ is the complete graph, which is not planar.
aa-f-236 · level facile · notes
Why does every planar graph have a vertex of degree at most $5$?
  1. Because $\omega(G)\le4$
  2. Because every face is a triangle
  3. Because $m\le3n-6$
  4. Because planar graphs are bipartite
Explanation. If all degrees were at least $6$ we would have $2m\ge6n$, against $2m\le6n-12$.
aa-f-237 · level facile · notes
What does Heawood's theorem (1890) state on planar graphs?
  1. Every planar graph is bipartite
  2. Every planar graph can be colored with $5$ colors
  3. Every planar graph can be colored with $3$ colors
  4. Coloring a planar graph with $5$ colors is NP-hard
Explanation. The vertex of degree at most $5$ allows a proof by induction that becomes a polynomial algorithm; deciding $3$-colorability stays hard.
aa-f-238 · level facile · notes
The algorithm $PL$ on planar graphs returns $4$ colors on a graph with $\chi(G)=3$. Is this consistent with the guarantee of $PL$?
  1. Yes: the error $4-3=1$ is at most $2$
  2. No: $PL$ is exact on planar graphs
  3. No: $PL$ always uses $5$ colors
  4. Yes, but only because $\chi(G)\ge4$
Explanation. $PL$ is $2$-additive: $PL(I)-\chi(G)\le2$; with $\chi(G)=3$ it may return $3$, $4$ or $5$ colors.
aa-f-239 · level facile · notes
In an interval graph, when are two vertices $u$ and $v$ adjacent?
  1. When the left endpoints coincide, $a_u=a_v$
  2. When one interval contains the other one
  3. When the two intervals are disjoint
  4. When the two intervals intersect
Explanation. The definition associates a closed interval with every vertex; the edges are the pairs of intervals with at least one common point.
aa-f-240 · level facile · notes
On an interval graph, with which order of the vertices is the greedy coloring optimal?
  1. By decreasing degree of the vertices
  2. With any order of the vertices
  3. By non-decreasing left endpoint $a_v$
  4. 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.
aa-f-241 · level facile · notes
On a graph with $\Delta(G)=3$, greedy uses at most $4$ colors. Which ratio does it guarantee with respect to $\chi(G)$, if $G$ has at least one edge?
  1. Greedy is optimal on these graphs
  2. At most $2$, because $\chi(G)\ge2$
  3. At most $\frac43$, as for planar graphs
  4. At most $4$, and not better
Explanation. With an edge $\chi(G)\ge2$, hence $GC(I)/\chi(G)\le4/2=2$: in general $\frac{\Delta(G)+1}{2}$.
aa-f-242 · level teorema · notes
Which consequence does Zuckerman's result have for the approximation of the VCP (if $P\neq NP$)?
  1. No constant $\alpha$-approximation
  2. The VCP has a PTAS but no FPTAS
  3. The VCP has a polynomial $\frac43$-approximation
  4. The VCP has a polynomial $2$-additive algorithm
Explanation. A constant $\alpha$ would be smaller than $n^{1-\varepsilon}$ for large $n$: no constant ratio, hence no approximation scheme.
aa-f-243 · level teorema · notes
What does Theorem 4.1 state for a polynomial algorithm $\mathscr{A}$ for the VCP, if $P\neq NP$?
  1. On every graph $\mathscr{A}(I)/\chi(G)\ge\frac43$
  2. There is a graph with $\mathscr{A}(I)-\chi(G)\ge\frac43$
  3. $\mathscr{A}$ is a $\frac43$-approximation
  4. There is a graph with $\mathscr{A}(I)/\chi(G)\ge\frac43$
Explanation. It is a worst-case result: there is at least one graph on which the ratio is at least $\frac43$, not on all of them.
aa-f-244 · level teorema · notes
Which guarantee does $PL$ have on planar graphs if the five color algorithm is replaced by the four color one?
  1. It becomes exact
  2. Ratio at most $\frac43$, not additive
  3. Additive error at most $1$
  4. 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.
aa-f-245 · level teorema · notes
Which inequality holds, for every graph $G$ and every order of the vertices, for the greedy coloring $GC$?
  1. $GC(I)\le\Delta(G)$
  2. $GC(I)\le\Delta(G)+1$
  3. $GC(I)\le\omega(G)$
  4. $GC(I)\le\chi(G)+1$
Explanation. Every vertex has at most $\Delta(G)$ neighbours colored before it; $GC(I)\le\Delta(G)$ fails on the complete graph $K_n$.
aa-f-246 · level teorema · notes
What holds on an interval graph for the greedy coloring with the vertices by non-decreasing $a_v$?
  1. $GC(I)=\omega(G)=\chi(G)$
  2. $GC(I)=\Delta(G)+1$
  3. $GC(I)\le2\chi(G)$
  4. $GC(I)=\chi(G)+1$
Explanation. Greedy uses $\omega(G)$ colors and $\omega(G)\le\chi(G)\le GC(I)$: all equal, the coloring is optimal.
aa-f-247 · level teorema · notes
What does breadth-first search guarantee on bipartite graphs?
  1. A coloring with at most $3$ colors
  2. A $\frac43$-approximation
  3. The clique number $\omega(G)$
  4. An optimal coloring
Explanation. On bipartite graphs the search finds a $2$-coloring, optimal because a graph with an edge needs $2$ colors.
aa-f-248 · level teorema · notes
On which property of planar graphs is the polynomial five color algorithm based?
  1. Every planar graph has $\omega(G)\le3$
  2. Every planar graph is an interval graph
  3. Every planar graph has a vertex of degree at most $5$
  4. Every planar graph is a bipartite graph
Explanation. One removes a vertex of degree $\le5$, colors the rest and reinserts it, recoloring if its neighbours use all five colors.
aa-f-249 · level ipotesi · notes
Theorem 4.1 (no ratio always $<\frac43$) requires which assumption?
  1. That $\chi(G)\ge4$
  2. $P\neq NP$
  3. That the graph is planar
  4. That the algorithm is greedy
Explanation. If $P=NP$, $3$-colorability would be decidable in polynomial time and the proof would collapse.
aa-f-250 · level ipotesi · notes
Theorem 4.1 concerns the algorithms for the VCP with which property?
  1. Polynomial algorithms
  2. Exact algorithms
  3. Algorithms with an additive guarantee
  4. Greedy algorithms
Explanation. An exponential algorithm can find $\chi(G)$ exactly: the limit holds for polynomial algorithms.
aa-f-251 · level ipotesi · notes
The lemma $m\le3n-6$ on planar graphs holds under which assumption on the number of vertices?
  1. $n\ge1$
  2. $n$ even
  3. $n\ge6$
  4. $n\ge3$
Explanation. With $n=2$ and one edge we would get $1\le0$: the lemma requires at least three vertices.
aa-f-252 · level ipotesi · notes
For which graphs does the guarantee $PL(I)-\chi(G)\le2$ hold?
  1. For graphs with $\Delta(G)\le5$
  2. For interval graphs
  3. For planar graphs
  4. For all graphs
Explanation. $PL$ uses the five color algorithm, which works only on planar graphs; on general graphs there is no constant guarantee.
aa-f-253 · level ipotesi · notes
In the analysis of $PL$, why is the error at most $2$ on non-bipartite planar graphs?
  1. Because planar graphs have $\omega(G)\le2$ and $\Delta(G)\le5$
  2. Because $\chi(G)\ge3$ and $PL$ uses $\le5$ colors
  3. Because planar graphs always have $\chi(G)\le2$
  4. Because $PL$ colors every graph by breadth-first search
Explanation. Bipartite graphs are colored optimally; on the others $\chi(G)\ge3$ and colors are at most $5$: $5-3=2$.
aa-f-254 · level ipotesi · notes
Greedy coloring is optimal on interval graphs: which assumption on the order of the vertices is needed?
  1. The order by non-decreasing left endpoint
  2. None: every order of the vertices is optimal
  3. The order by length of the interval
  4. The order by increasing degree
Explanation. With an arbitrary order greedy may use more than $\omega(G)$ colors even on an interval graph.
aa-f-255 · level ipotesi · notes
For which $\varepsilon$ does Zuckerman's result on the VCP hold?
  1. Only for $\varepsilon\ge\frac12$
  2. Only for $\varepsilon<\frac13$
  3. For $\varepsilon=0$
  4. For every $\varepsilon>0$
Explanation. For every $\varepsilon>0$, if $P\neq NP$: with $\varepsilon=0$ the ratio $n$ is trivially achievable.
aa-f-256 · level ipotesi · notes
Does the bound $GC(I)\le\Delta(G)+1$ depend on the order in which greedy colors the vertices?
  1. Yes: only for the order of the names
  2. Yes: only on planar graphs
  3. No: it holds for every order
  4. Yes: only by decreasing degree
Explanation. The proof only uses that a vertex has at most $\Delta(G)$ neighbours: it holds whatever the order.
aa-f-324 · level teorema · notes
On an interval graph, what is $\omega(G)$?
  1. The maximum degree of the graph plus one
  2. The number of pairwise disjoint intervals
  3. The most intervals sharing a point
  4. The total number of intervals
Explanation. Pairwise intersecting intervals share a common point (Helly property on the line): cliques are the intervals containing a point.
aa-f-325 · level teorema · notes
In the proof of the $\frac43$ bound, what would an algorithm with ratio always $<\frac43$ do on a graph with $\chi(G)=3$?
  1. It would not terminate
  2. It would use at most $3$ colors
  3. It would use at least $4$ colors
  4. It would use $2$ colors
Explanation. $\mathscr{A}(I)<\frac43\cdot3=4$, hence $\mathscr{A}(I)\le3$: this way $3$-colorability would be decided.
aa-f-326 · level teorema · notes
Does the VCP have an approximation scheme (PTAS), if $P\neq NP$?
  1. No: not even a constant ratio
  2. Yes, a PTAS but no FPTAS
  3. Yes, it even has an FPTAS
  4. Yes, on general graphs
Explanation. A PTAS would give a constant ratio $1+\varepsilon$, ruled out by the corollary.
aa-f-327 · level ipotesi · notes
For which graphs does the corollary «no constant ratio for the VCP» hold?
  1. For planar graphs
  2. For interval graphs
  3. For bipartite graphs
  4. For general graphs
Explanation. On planar graphs $PL$ is $2$-additive and interval and bipartite graphs are colored optimally: the limit concerns arbitrary graphs.
aa-f-328 · level ipotesi · notes
Under which assumption does the five color algorithm apply?
  1. That $\omega(G)\le5$
  2. That the graph is an interval graph
  3. That the graph is planar
  4. That $\Delta(G)\le5$
Explanation. It uses the vertex of degree at most $5$, which exists in every planar graph but not in an arbitrary graph.
aa-f-329 · level ipotesi · notes
Breadth-first search colors optimally with $2$ colors: under which assumption?
  1. That $\Delta(G)\le2$
  2. That the graph is bipartite
  3. That the graph is planar
  4. That the graph is connected and complete
Explanation. If the graph is not bipartite the search finds an edge between same-colored vertices and $\chi(G)\ge3$.
aa-f-356 · level teorema · notes
What does the algorithm $PL$ do on a planar graph?
  1. It uses greedy by degree
  2. It tries all colorings
  3. Optimal on bipartite, else $5$
  4. It always uses $4$ colors
Explanation. First breadth-first search (bipartite?), otherwise the five color algorithm: error at most $2$.

5. Maximum clique: limits of approximation (56)

aa-f-017 · level teorema · notes
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?
  1. $\omega(G\boxtimes H)=\omega(G)+\omega(H)$
  2. $\omega(G\boxtimes H)=\max\{\omega(G),\omega(H)\}$
  3. $\omega(G\boxtimes H)=\omega(G)^{\omega(H)}$
  4. $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$
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.
aa-f-018 · level ipotesi · notes
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:
  1. $\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
  2. $\omega(G)=\alpha(\overline{G})$; from a stable set of $\overline{G}$ one extracts a clique of $G$; the half-full property
  3. $\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
  4. $\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.
aa-f-019 · level facile · notes
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?
  1. $\omega(G)\le 5$ and the MCP is solved in $O(n^5)$, while the MSSP stays NP-hard
  2. $\omega(G)\le 4$ and the MCP is solved in $O(n^4)$, while the MSSP stays NP-hard
  3. $\omega(G)\le 4$ and the MCP is solved in $O(n^4)$; so is the MSSP, through the complement
  4. $\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.
aa-f-020 · level facile · notes
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?
  1. $4$
  2. $5$
  3. $6$
  4. $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.
aa-f-064 · level facile · notes
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$?
  1. $25$ vertices, $\omega(G\boxtimes G)=4$
  2. $10$ vertices, $\omega(G\boxtimes G)=4$
  3. $25$ vertices, $\omega(G\boxtimes G)=2$
  4. $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.
aa-f-065 · level facile · notes
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?
  1. $8$
  2. $16$
  3. $2$
  4. $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.
aa-f-066 · level facile · notes
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$?
  1. $16$
  2. $\frac43$
  3. $2$
  4. $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$.
aa-f-067 · level facile · notes
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$)?
  1. At most $\sqrt n$; a PTAS exists
  2. At most $n$; no polynomial algorithm guarantees $n^{1-\varepsilon}$ for any $\varepsilon>0$
  3. At most $2$; no polynomial algorithm guarantees less than $2$
  4. 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.
aa-f-068 · level facile · notes
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$?
  1. For every fixed $\Delta$, and even when $\Delta\le\log_2 n$
  2. Only for $\Delta\le 3$
  3. Never: $2^{\Delta}$ is always exponential
  4. 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.
aa-f-069 · level facile · notes
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$?
  1. At most $3$
  2. At most $\frac43$
  3. No constant ratio
  4. 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.
aa-f-070 · level facile · notes
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?
  1. Because the complement of a planar graph is still planar
  2. Because on planar graphs $\alpha(G)=\omega(G)$
  3. The complement of a planar or bounded-degree graph is dense: on the original class the stable set stays NP-hard
  4. 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).
aa-f-071 · level facile · notes
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?
  1. Because planar graphs have at most $4n$ edges
  2. Every planar graph has $\omega(G)\le 4$ ($K_5$ is not planar): $O(n^4)$ subsets are checked
  3. Because every planar graph has maximum degree at most $4$
  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.
aa-f-115 · level facile · notes
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?
  1. $\mathscr{A}(I)=\omega(G)$
  2. $\mathscr{A}(I)\le\omega(G)$ and $\omega(G)/\mathscr{A}(I)\ge1$
  3. $\mathscr{A}(I)\ge\omega(G)$
  4. $\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$.
aa-f-116 · level facile · notes
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?
  1. $9$, by $\{1,2,3\}\times\{1,2,3\}$
  2. $6$, by $\{1,2,3\}\times\{1,2\}$
  3. $3$, by $\{1,2,3\}\times\{1\}$
  4. $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.
aa-f-183 · level facile · notes
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$?
  1. $t=2$, on a graph with $2n^2$ vertices
  2. $t=2$, on a graph with $n^4$ vertices
  3. $t=1$, on a graph with $n^2$ vertices
  4. $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.
aa-f-184 · level facile · notes
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?
  1. The assumption: $NP\neq ZPP$ for Håstad, $P\neq NP$ for Zuckerman
  2. The bound: $n^{1/2}$ for Håstad, $n^{1-\varepsilon}$ for Zuckerman
  3. The problem: clique for Håstad, stable set for Zuckerman
  4. 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.
aa-f-185 · level teorema · notes
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?
  1. The problem has a PTAS but not an FPTAS
  2. The problem has ratio $2$ but not a PTAS
  3. The problem has ratio $n^{1/2}$ but not a constant one
  4. 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).
aa-f-186 · level facile · notes
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?
  1. $K_5$ has $5$ vertices of degree $4$, more than $3$
  2. $K_5$ has more than $3\cdot5=15$ edges
  3. $K_5$ has $10$ edges, more than $3\cdot5-6=9$
  4. $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$.
aa-f-187 · level facile · notes
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$?
  1. For every graph with $\Delta\le\sqrt n$
  2. For fixed $\Delta$, and also for $\Delta\le\log_2n$
  3. Only for graphs with $\Delta\le3$, like cubic ones
  4. 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.
aa-f-188 · level facile · notes
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?
  1. $28$
  2. $64$
  3. $12$
  4. $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.
aa-f-189 · level facile · notes
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?
  1. The fiber $\{4,5\}$: it has $2\ge\sqrt6$ vertices
  2. $K$ itself: it is already a clique of $G$
  3. $\{1,2,3,4,5\}$: it joins projection and fiber
  4. $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$.
aa-f-257 · level facile · notes
In the strong product $G\boxtimes H$, when are two distinct vertices $(u,x)$ and $(v,y)$ adjacent?
  1. If $\{u,v\}\in E$ and also $\{x,y\}\in F$, no other case
  2. If $u=v$ or $x=y$, whatever the edges are
  3. If $\{u,v\}\in E$ or $\{x,y\}\in F$, even alone
  4. 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.
aa-f-258 · level facile · notes
How many vertices does the strong product of a graph with $5$ vertices and a graph with $7$ vertices have?
  1. $5^7$
  2. $70$
  3. $35$
  4. $12$
Explanation. The vertex set is the Cartesian product $V\times W$: $5\cdot7=35$ vertices.
aa-f-259 · level facile · notes
If $\omega(G)=3$ and $\omega(H)=4$, what is $\omega(G\boxtimes H)$?
  1. $81$
  2. $12$
  3. $7$
  4. $4$
Explanation. By Proposition 5.2 the clique number of the strong product is the product of the clique numbers: $3\cdot4=12$.
aa-f-260 · level facile · notes
If $K$ is a clique of $G\boxtimes H$, what is its projection $p(K)$ on the vertices of $G$?
  1. A clique of $G$
  2. A stable set of $G$
  3. A clique of $H$
  4. An arbitrary set of vertices of $G$
Explanation. Two elements of $K$ with different first coordinates have adjacent first coordinates in $G$: the projection is a clique.
aa-f-261 · level facile · notes
The strong power $G^{\boxtimes k}$ of a graph with $n$ vertices: how many vertices does it have and what is its clique number?
  1. $kn$ vertices and $k\,\omega(G)$
  2. $n^k$ vertices and $k\,\omega(G)$
  3. $kn$ vertices and $\omega(G)^k$
  4. $n^k$ vertices and $\omega(G)^k$
Explanation. Applying the strong product $k-1$ times: the vertices multiply and so do the clique numbers. For fixed $k$ the size stays polynomial.
aa-f-262 · level facile · notes
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$?
  1. $16$
  2. $8$
  3. $\sqrt4=2$
  4. $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}$.
aa-f-263 · level facile · notes
The trivial ratio $n$ for the MCP is obtained by returning what?
  1. The vertex of minimum degree with its neighbours
  2. A single vertex
  3. All the vertices
  4. 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.
aa-f-264 · level facile · notes
Why does a planar graph contain no clique of $5$ vertices?
  1. Because $K_5$ has $10>3\cdot5-6=9$ edges
  2. Because planar graphs are bipartite
  3. Because planar graphs have maximum degree $4$
  4. Because $\chi(G)\le4$ implies $n\le4$
Explanation. A subgraph of a planar graph is planar, and $K_5$ violates $m\le3n-6$: hence $\omega(G)\le4$.
aa-f-265 · level facile · notes
How is the MCP solved to optimality on a planar graph in $O(n^4)$ time?
  1. By greedy by decreasing degree
  2. By a breadth-first search of the graph
  3. By the five color algorithm
  4. By trying all sets of at most $4$ vertices
Explanation. Since $\omega(G)\le4$, it is enough to enumerate the subsets of at most $4$ vertices: there are $O(n^4)$ of them.
aa-f-266 · level facile · notes
A graph has maximum degree $\Delta(G)=6$. Which bound holds for $\omega(G)$?
  1. $\omega(G)\le3$
  2. $\omega(G)\le12$
  3. $\omega(G)\le7$
  4. $\omega(G)\le6$
Explanation. In a clique every vertex is adjacent to the other $\omega(G)-1$, hence $\omega(G)-1\le\Delta(G)$.
aa-f-267 · level facile · notes
Why is the MCP solved in $O(n\,2^{\Delta}\Delta^2)$ time, with $\Delta=\Delta(G)$?
  1. Because one uses dynamic programming by profits on the adjacency matrix
  2. Each clique lies in a closed neighbourhood
  3. Because greedy by decreasing degree is optimal on graphs of bounded maximum degree
  4. Because every graph of bounded degree is planar, so that $\omega(G)\le4$
Explanation. For each vertex $v$ there are at most $2^{\Delta}$ subsets of neighbours, and checking whether one is a clique costs $O(\Delta^2)$.
aa-f-268 · level facile · notes
Why do the negative results on the MCP also hold for the maximum stable set problem (MSSP)?
  1. Because $\alpha(G)=\omega(\overline G)$, with the same $n$
  2. Because every clique of $G$ is also a stable set of $G$
  3. Because the MSSP is easier than the MCP on every graph
  4. Because $\alpha(G)=\omega(G)$ holds for every graph $G$
Explanation. $\alpha(G)=\omega(\overline G)$ and the complement is built in $O(n^2)$: an algorithm for one problem gives the same ratio for the other.
aa-f-269 · level facile · notes
A graph has $n=20$ vertices and $\Delta(G)=4$. At least how many vertices does every maximal stable set have?
  1. $5$
  2. $20$
  3. $1$
  4. $4$
Explanation. Every vertex of $S$ excludes at most $\Delta(G)$ neighbours: $n\le|S|(\Delta(G)+1)$, hence $|S|\ge20/5=4$.
aa-f-270 · level teorema · notes
Which equality holds for the clique number of the strong product of any two graphs $G$ and $H$?
  1. $\omega(G\boxtimes H)=\max\{\omega(G),\omega(H)\}$
  2. $\omega(G\boxtimes H)=\omega(G)^{\omega(H)}$
  3. $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$
  4. $\omega(G\boxtimes H)=\omega(G)+\omega(H)$
Explanation. The product of two cliques is a clique ($\ge$), and every clique $K$ has $|K|\le|p(K)|\max_u|K_u|\le\omega(G)\omega(H)$ ($\le$).
aa-f-271 · level teorema · notes
What does the amplification theorem on the MCP state?
  1. Every polynomial algorithm for the MCP has ratio at least $\frac43$
  2. A constant $\alpha$ gives every constant $\beta>1$
  3. The MCP has a polynomial $2$-approximation on every graph
  4. If the MCP has a PTAS then necessarily $P=NP$
Explanation. With the strong power $G^{\boxtimes k}$ the ratio drops to $\alpha^{1/k}$, which for large $k$ is $\le\beta$.
aa-f-272 · level teorema · notes
What do the results of Håstad (1999) and Zuckerman (2007) state on the MCP, if $P\neq NP$?
  1. No ratio $n^{1-\varepsilon}$, for every $\varepsilon>0$
  2. The MCP has an FPTAS, but no polynomial exact algorithm
  3. The MCP has a polynomial $2$-approximation but no PTAS
  4. No ratio $\le\log n$ is possible, but $\sqrt n$ is
Explanation. The trivial ratio is $n$: one cannot go down even to $n^{1-\varepsilon}$, hence no constant ratio.
aa-f-273 · level teorema · notes
What holds for the MCP on planar graphs?
  1. The MCP stays non-approximable within $n^{1-\varepsilon}$
  2. $\omega(G)\le5$ and an exponential algorithm is needed
  3. The MCP only has a polynomial $2$-approximation
  4. $\omega(G)\le4$ and the MCP is solved to optimality in $O(n^4)$
Explanation. A clique of a planar graph has at most $4$ vertices: enumerating the subsets of at most $4$ vertices is polynomial.
aa-f-274 · level teorema · notes
Which guarantee does the greedy that builds a maximal stable set $S$ have, on every graph?
  1. $\alpha(G)-|S|\le1$
  2. $\alpha(G)/|S|\le\omega(G)$
  3. $\alpha(G)/|S|\le\Delta(G)+1$
  4. $\alpha(G)/|S|\le2$
Explanation. $|S|\ge\frac{n}{\Delta(G)+1}$ and $\alpha(G)\le n$: the ratio is at most $\Delta(G)+1$, constant on graphs of bounded degree.
aa-f-275 · level teorema · notes
What holds for the approximation of the maximum stable set problem (MSSP), if $P\neq NP$?
  1. It is solvable to optimality in polynomial time
  2. No constant ratio
  3. It has a polynomial $2$-approximation on every graph
  4. It has a PTAS, although not an FPTAS
Explanation. Through the complement the MSSP inherits the limits of the MCP.
aa-f-276 · level teorema · notes
On graphs of maximum degree $\Delta(G)\le\Delta$ constant, what holds for the MCP?
  1. It is solved to optimality in polynomial time
  2. It stays non-approximable within $n^{1-\varepsilon}$
  3. It only has a $(\Delta+1)$-approximation
  4. It is NP-hard even for $\Delta=3$
Explanation. With constant $\Delta$, $2^{\Delta}\Delta^2$ is a constant: the time is linear in $n$.
aa-f-277 · level ipotesi · notes
The amplification theorem uses $G^{\boxtimes k}$ with fixed $k$. Why must $k$ be constant?
  1. Because for large $k$, $\omega(G)^k$ is not an integer
  2. Because the strong product is not associative
  3. Because for $k\ge3$ the graph is no longer simple
  4. Because $G^{\boxtimes k}$ has $n^k$ vertices
Explanation. With $k$ growing with $n$ the size $n^k$ would be superpolynomial and the algorithm would no longer be polynomial.
aa-f-278 · level ipotesi · notes
The amplification theorem starts from an $\alpha$-approximation: which assumption on $\alpha$ is needed?
  1. $\alpha=n^{1-\varepsilon}$
  2. None: it holds for every ratio $\alpha(n)$
  3. $\alpha$ is a constant
  4. $\alpha<2$
Explanation. The argument fixes $k$ with $\alpha^{1/k}\le\beta$, possible only if $\alpha$ does not grow with $n$.
aa-f-279 · level ipotesi · notes
Under which assumption does the result of Håstad and Zuckerman on the MCP hold?
  1. That the algorithm is greedy
  2. $P\neq NP$
  3. That the graph is planar
  4. That $\Delta(G)$ is bounded
Explanation. Without $P\neq NP$ the MCP could be solved in polynomial time; on planar graphs and graphs of bounded degree it is easy.
aa-f-280 · level ipotesi · notes
For which graphs does the bound $\omega(G)\le4$ hold?
  1. For planar graphs
  2. For all graphs with $\Delta(G)\le4$
  3. For all graphs
  4. For bipartite graphs only
Explanation. It comes from $K_5$ not being planar; a non-planar graph may contain arbitrarily large cliques.
aa-f-281 · level ipotesi · notes
For which kind of stable set $S$ does the bound $|S|\ge\frac{n}{\Delta(G)+1}$ hold?
  1. For every stable set
  2. Only for a maximum stable set
  3. Only for a stable set found by breadth-first search
  4. 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.
aa-f-282 · level ipotesi · notes
Under which assumption is the exact $O(n\,2^{\Delta}\Delta^2)$ algorithm for the MCP polynomial?
  1. That $\omega(G)\le4$ holds for the graph
  2. That the graph is bipartite and connected
  3. That $\Delta(G)$ is a constant
  4. That the graph is planar and connected
Explanation. If $\Delta$ grows with $n$ the factor $2^{\Delta}$ becomes exponential.
aa-f-283 · level ipotesi · notes
Why does passing to the complement transfer a ratio $n^{1-\varepsilon}$ from the MCP to the MSSP?
  1. Because $\Delta(\overline G)=\Delta(G)$
  2. Because $\overline G$ has the same $n$ vertices
  3. Because $\overline G$ has fewer edges
  4. Because $\overline G$ is planar
Explanation. The ratio is expressed as a function of $n$, which does not change, and the complement costs $O(n^2)$.
aa-f-284 · level ipotesi · notes
Does the equality $\omega(G\boxtimes H)=\omega(G)\,\omega(H)$ require assumptions on $G$ and $H$?
  1. No: it holds for every pair of graphs
  2. Yes: $G$ and $H$ must be planar
  3. Yes: $G=H$
  4. Yes: $G$ and $H$ must have the same number of vertices
Explanation. The proposition holds for any two graphs; the case $G=H$ (strong powers) is the one used in the amplification.
aa-f-330 · level teorema · notes
In the amplification, from a clique of $G^{\boxtimes k}$ of size $\ge\omega(G)^k/\alpha$ one gets a clique of $G$ of size at least:
  1. $\omega(G)^k/\alpha$
  2. $\omega(G)-\alpha$
  3. $\omega(G)/\alpha^{1/k}$
  4. $\omega(G)/\alpha$
Explanation. A clique $K$ of the product has a projection or a fibre of size $\ge|K|^{1/k}$: the ratio becomes $\alpha^{1/k}$.
aa-f-331 · level teorema · notes
Combining the amplification with the results of Håstad and Zuckerman, what is concluded for the MCP?
  1. An FPTAS
  2. No constant ratio
  3. A PTAS but no FPTAS
  4. A $2$-approximation
Explanation. A constant ratio would give every ratio $\beta>1$, i.e. a PTAS; but not even $n^{1-\varepsilon}$ is achievable.
aa-f-332 · level teorema · notes
Which inequality holds for every graph $G$ between clique number and maximum degree?
  1. $\omega(G)\le\Delta(G)+1$
  2. $\omega(G)\le\Delta(G)$
  3. $\omega(G)\ge\Delta(G)$
  4. $\omega(G)\le\frac{\Delta(G)}{2}$
Explanation. A vertex of a clique has at least $\omega(G)-1$ neighbours; $K_n$ shows that $\omega(G)\le\Delta(G)$ is false.
aa-f-333 · level ipotesi · notes
The $n^{1-\varepsilon}$ limit for the MCP concerns algorithms with which property?
  1. Exact
  2. Greedy
  3. With an additive guarantee
  4. Polynomial
Explanation. An exponential algorithm finds $\omega(G)$ exactly; the limit holds for polynomial ones, if $P\neq NP$.
aa-f-334 · level ipotesi · notes
The guarantee $\alpha(G)/|S|\le\Delta(G)+1$ of greedy is a constant ratio under which assumption?
  1. That $\omega(G)\le4$ holds
  2. None: it is always constant
  3. That $\Delta(G)$ is constant
  4. That the graph is planar
Explanation. On general graphs $\Delta(G)$ can be $n-1$ and the guarantee becomes $n$, consistent with the negative results.
aa-f-335 · level ipotesi · notes
In the strong product, when are two vertices $(u,x)$ and $(u,y)$ with the same first coordinate adjacent?
  1. When $u$ has degree $>0$
  2. When $\{x,y\}\in F$
  3. Always, for all $x,y$
  4. Never, since $u=u$
Explanation. With $u=v$ the first condition holds; the second remains, $x=y$ (excluded, distinct vertices) or $\{x,y\}\in F$.
aa-f-357 · level teorema · notes
Which complete graph is the largest one contained in a planar graph?
  1. $K_5$
  2. $K_3$
  3. $K_6$
  4. $K_4$
Explanation. $K_5$ is not planar, $K_4$ is: hence $\omega(G)\le4$ on planar graphs.

6. The TSP: the general case and the metric case (44)

aa-f-021 · level teorema · notes
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?
  1. The general TSP has no constant approximation; on the metric TSP $DT$ has ratio $2$ and $CH$ ratio $\frac32$
  2. The general TSP has no constant approximation; on the metric TSP $DT$ has ratio $\frac32$ and $CH$ ratio $2$
  3. The general TSP has a $2$-approximation, $DT$; on the metric TSP $CH$ has ratio $\frac32$
  4. 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.
aa-f-022 · level ipotesi · notes
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)$?
  1. $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
  2. $d(T)\le z(I)/2$; the Eulerian circuit of the doubled tree has length $2d(T)$; distances are symmetric
  3. The nearest neighbour tour has length at most $2z(I)$; every city has even degree; distances are symmetric
  4. $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$.
aa-f-023 · level ipotesi · notes
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)$?
  1. $d(T)\le z(I)$; $d(M)\le d(T)$; the odd-degree cities of $T$ are odd in number
  2. $d(T)\le z(I)$; the doubled tree circuit has length $2d(T)$; distances are symmetric
  3. $d(T)\le z(I)$; $d(M)\le z(I)/2$; shortcuts do not lengthen the Eulerian circuit of $T\cup M$
  4. $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.
aa-f-072 · level ipotesi · notes
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?
  1. Distance $2$ on the edges and $1$ on non-adjacent pairs
  2. 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
  3. Distance $1$ on all pairs: every tour is optimal
  4. 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.
aa-f-073 · level facile · notes
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?
  1. Cities in the plane with Euclidean distances
  2. Instances with arbitrary integer distances
  3. Instances with $d_{ij}\in\{1,2\}$ and $d_{ij}\ne d_{ji}$
  4. 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.
aa-f-074 · level facile · notes
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?
  1. It is polynomial, because the triangle inequality allows shortcuts
  2. It is polynomial on Euclidean instances, NP-hard on the others
  3. It has no constant approximation either
  4. 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.
aa-f-075 · level facile · notes
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)$?
  1. $DT(I)\le 7$ and $z(I)\ge 14$
  2. $DT(I)\le\frac{21}{2}$ and $z(I)\ge 7$
  3. $DT(I)\le 14$ and $z(I)\ge 7$
  4. $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)$.
aa-f-076 · level facile · notes
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?
  1. $0$
  2. $4$
  3. $3$
  4. $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.
aa-f-077 · level ipotesi · notes
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?
  1. Removing an edge from the optimal tour gives a path through all cities, i.e., a spanning tree, of length at most $z(I)$
  2. The triangle inequality allows shortening the tree
  3. The optimal tour always contains the minimum spanning tree
  4. 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.
aa-f-078 · level ipotesi · notes
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$?
  1. Because $M$ has half the edges of the optimal tour
  2. Because every edge of $M$ is shorter than every edge of the tour
  3. Because $M$ is contained in the minimum spanning tree
  4. 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.
aa-f-079 · level facile · notes
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)$?
  1. $\frac{28}{3}\le z(I)\le 10$
  2. $z(I)\ge 14$
  3. $10\le z(I)\le 14$
  4. $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$).
aa-f-080 · level facile · notes
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?
  1. $2$ for every $n$
  2. $\frac{14}{9}$, and it tends to $2$
  3. $\frac{14}{9}$, and it tends to $\frac32$
  4. $\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.
aa-f-117 · level teorema · notes
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$?
  1. By the triangle inequality every shortcut $d_{u_0u_q}$ is at most the length of the stretch of $W$ it replaces
  2. Because $\sigma$ has fewer cities than $W$
  3. Because the distances are all equal
  4. 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.
aa-f-118 · level facile · notes
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?
  1. Both double the edges of $T$
  2. Double tree: adds a matching; Christofides: doubles $T$
  3. Neither uses an Eulerian multigraph
  4. 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.
aa-f-119 · level teorema · notes
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?
  1. That the double tree is better than Christofides
  2. That shortcuts may lengthen the tour
  3. That the guarantee $\frac32$ of Christofides is tight: the matching may cost almost half the optimal tour
  4. 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.
aa-f-120 · level ipotesi · notes
The guarantee $CH(I)\le\frac32z(I)$ of Christofides uses the triangle inequality. What happens for the general TSP, without this assumption?
  1. The general TSP becomes polynomial
  2. No polynomial algorithm has a constant ratio, if P $\ne$ NP
  3. Christofides stays a $\frac32$-approximation
  4. 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.
aa-f-190 · level facile · notes
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?
  1. $21$
  2. $20$
  3. $29$
  4. $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$.
aa-f-191 · level ipotesi · notes
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}$)?
  1. Because Hamiltonian cycle is easy on metric graphs
  2. Because in the metric TSP distances can be $0$
  3. The instances built violate the triangle inequality
  4. 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.
aa-f-192 · level facile · notes
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?
  1. No: the condition concerns only nearby cities
  2. No: $9\le5+4$ holds, equality being allowed
  3. Yes: $d_{15}$ is not strictly smaller than $d_{12}+d_{25}$
  4. 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.
aa-f-193 · level facile · notes
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?
  1. Shortcuts (skipping already visited cities) do not lengthen the walk
  2. It makes the TSP solvable in polynomial time
  3. It guarantees that the minimum spanning tree is already a tour
  4. 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.
aa-f-194 · level facile · notes
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. $\{1,2\},\{3,4\},\{1,4\}$, with $d(T)=8$
  2. $\{1,2\},\{1,3\},\{2,3\}$, with $d(T)=8$
  3. $\{1,2\},\{3,4\}$, with $d(T)=4$
  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.
aa-f-195 · level facile · notes
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. $(1,3,4,2)$
  2. $(1,2,1,3,4)$
  3. $(1,2,3,4)$
  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$.
aa-f-196 · level facile · notes
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. $(1,2,4,3)$, of length $12$
  2. $(1,2,3,4)$, of length $11$
  3. $(1,2,3,4)$, of length $14$
  4. $(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.
aa-f-197 · level facile · notes
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?
  1. The last copy of the edge to the parent is a bridge, used last
  2. Because Kruskal's algorithm always returns a path
  3. Because in the doubled tree every city has degree $2$
  4. 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.
aa-f-198 · level facile · notes
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. $(1,2,3,4)$, of length $11$
  2. $(1,3,4,2)$, of length $15$
  3. $(1,2,1,3,4)$, of length $14$
  4. $(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.
aa-f-199 · level facile · notes
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?
  1. Because the leaves of a tree are always even in number
  2. Because the blossom algorithm requires it
  3. The degrees of a graph sum to twice the number of edges
  4. 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).
aa-f-200 · level facile · notes
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?
  1. $z(I)\ge14.5$
  2. $z(I)\ge20$
  3. $z(I)\ge29$
  4. $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.
aa-f-201 · level teorema · notes
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$?
  1. The MST is the star; leaves consecutive in preorder are not joined by $P$
  2. Because the minimum tree is the path $P$, traversed twice
  3. Because the shortcuts save $b-a$ at every single step
  4. 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)$.
aa-f-285 · level facile · notes
From which NP-complete problem does one reduce to show that the general TSP has no constant ratio (if $P\neq NP$)?
  1. Hamiltonian cycle
  2. Bin packing
  3. $2$-colorability
  4. Minimum spanning tree
Explanation. Edges of the graph get distance $1$ and the other pairs a very large distance: a ratio $\alpha$ would tell Hamiltonian graphs apart.
aa-f-286 · level facile · notes
Which property of the distances makes a TSP instance metric?
  1. $d_{ij}\le d_{ik}\cdot d_{kj}$ for every triple
  2. $d_{ij}=d_{ik}+d_{kj}$ for every triple
  3. $d_{ij}\ge d_{ik}+d_{kj}$ for every triple
  4. $d_{ij}\le d_{ik}+d_{kj}$ for every triple
Explanation. It is the triangle inequality: going directly from $i$ to $j$ costs no more than passing through $k$.
aa-f-287 · level facile · notes
Why is the cost of a minimum spanning tree $T$ a lower bound for the TSP?
  1. Because the triangle inequality holds
  2. Because $T$ always has exactly $n$ edges
  3. An optimal tour minus an edge is a tree
  4. Because every spanning tree is a tour
Explanation. An optimal tour minus an edge is a Hamiltonian path, i.e. a spanning tree: $d(T)\le z(I)$, even without the metric.
aa-f-288 · level facile · notes
In the double tree algorithm, what is done with the edges of the minimum spanning tree?
  1. They are sorted by decreasing cost and dropped
  2. They are doubled, giving an Eulerian multigraph
  3. The longest ones of the tree are removed
  4. The vertices of odd degree are matched
Explanation. Doubling the edges every vertex gets even degree: there is an Eulerian circuit of cost $2d(T)$, then shortcuts are taken.
aa-f-289 · level facile · notes
What are the «shortcuts» applied to the Eulerian circuit?
  1. Already visited cities are skipped
  2. The longest edges of the circuit are removed
  3. Two crossing edges are swapped (2-opt)
  4. A perfect matching is added
Explanation. From the closed walk only the first visit of every city is kept; with the metric the cost does not increase.
aa-f-290 · level facile · notes
A metric instance has a minimum spanning tree of cost $d(T)=30$. At most how much does the double tree tour cost?
  1. $45$
  2. $30$
  3. $90$
  4. $60$
Explanation. The Eulerian circuit costs $2d(T)=60$ and shortcuts do not lengthen it: $DT(I)\le60$.
aa-f-291 · level facile · notes
In the Christofides algorithm, which vertices are matched by a minimum weight perfect matching?
  1. Only the leaves of the tree
  2. The vertices of even degree of the tree
  3. The vertices of odd degree of the tree
  4. All the vertices of the tree
Explanation. Adding the matching of the odd vertices of $T$ every degree becomes even and the multigraph is Eulerian.
aa-f-292 · level facile · notes
Why is the number of vertices of odd degree of a tree even?
  1. Because a tree has exactly two leaves
  2. Because the degree sum is even
  3. Because a tree always has $n-1$ edges
  4. Because every tree is a bipartite graph
Explanation. In every graph $\sum_v\deg(v)=2m$ is even, hence odd degrees come in even number: the perfect matching exists.
aa-f-293 · level facile · notes
A metric instance has $z(I)=40$. At most how much does a minimum perfect matching of an even set $O$ of cities cost?
  1. $20$
  2. $40$
  3. $\frac{40}{3}$
  4. $80$
Explanation. The optimal tour, restricted to $O$ with shortcuts, splits into two perfect matchings; the better one costs at most $z(I)/2=20$.
aa-f-294 · level facile · notes
On a metric instance with $z(I)=24$, at most how much does the Christofides tour cost?
  1. $48$
  2. $30$
  3. $24$
  4. $36$
Explanation. $CH(I)\le d(T)+d(M)\le z(I)+\frac{z(I)}{2}=36$.
aa-f-295 · level facile · notes
The tight instances of double tree have ratio $\frac{2n}{n+2}$. What is it for $n=7$?
  1. $\frac{16}{9}$
  2. $\frac{9}{7}$
  3. $\frac{14}{9}$
  4. $\frac{7}{9}$
Explanation. $\frac{2\cdot7}{7+2}=\frac{14}{9}\approx1.56$; as $n$ grows the ratio tends to $2$.
aa-f-296 · level facile · notes
What do double tree and Christofides have in common?
  1. Both match the odd vertices
  2. Minimum spanning tree
  3. Both use 2-opt
  4. Both are exact on metric instances
Explanation. They differ only in how the tree is made Eulerian: doubled edges (DT) or matching of the odd vertices (CH).
aa-f-297 · level facile · notes
What do the tight instances of Christofides show?
  1. That the ratio $\frac32$ cannot be improved
  2. That Christofides is an optimal algorithm
  3. That double tree is always better
  4. That the metric TSP has a PTAS
Explanation. On a family of metric instances the ratio tends to $\frac32$: the guarantee is tight.
aa-f-298 · level facile · notes
A connected multigraph has an Eulerian circuit if and only if:
  1. every vertex has odd degree
  2. it is a tree
  3. it has an even number of vertices
  4. every vertex has even degree
Explanation. It is Euler's theorem: exactly what doubling the edges and matching the odd vertices guarantee.
aa-f-299 · level teorema · notes
Which guarantee does double tree have on metric instances?
  1. $DT(I)\le z(I)+2$
  2. $DT(I)\le\frac43z(I)$
  3. $DT(I)\le2z(I)$
  4. $DT(I)\le\frac32z(I)$
Explanation. $DT(I)\le2d(T)\le2z(I)$: shortcuts (metric) and the tree lower bound.
aa-f-300 · level ipotesi · notes
Shortcuts do not lengthen the walk: which assumption is needed?
  1. A unique spanning tree
  2. The triangle inequality
  3. All distances equal
  4. An odd number of cities
Explanation. Skipping a city replaces two edges by one, which by the triangle inequality costs no more.

7. Approximation for $P\|C_{\max}$ (42)

aa-f-024 · level ipotesi · notes
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)$?
  1. $S_\ell\le\frac1m\sum_{j\ne\ell}t_j$; $z(I)\ge\frac1m\sum_j t_j$; $z(I)\ge 2t_\ell$
  2. $\ell$ is the longest job; $z(I)=\frac1m\sum_j t_j$; $z(I)\ge t_\ell$
  3. The jobs are sorted by non-increasing duration; $z(I)\ge t_\ell$; $S_\ell\le z(I)$
  4. $S_\ell\le\frac1m\sum_{j\ne\ell}t_j$; $z(I)\ge\frac1m\sum_j t_j$; $z(I)\ge t_\ell$
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$.
aa-f-025 · level facile · notes
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?
  1. $\frac43$
  2. $\frac54$
  3. $\frac76$
  4. $\frac32$
Explanation. $\frac43-\frac1{3m}=\frac43-\frac16=\frac76$. With any list $LIST$ guarantees $2-\frac12=\frac32$.
aa-f-026 · level teorema · notes
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?
  1. Neither is reached: the ratios are only approached as $n$ grows
  2. Both are tight: for every $m\ge 2$ some instances reach exactly the two ratios
  3. Both are tight only for $m=2$; for $m\ge 3$ the ratios are lower
  4. 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$).
aa-f-081 · level facile · notes
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$?
  1. $8$ and $8$
  2. $9$ and $7$
  3. $8$ and $7$
  4. $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.
aa-f-082 · level facile · notes
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?
  1. $LPT$ is exponential, $LIST$ polynomial
  2. $LIST$ can work online, assigning jobs as they arrive; $LPT$ must know all the jobs to sort them
  3. $LIST$ requires knowing all the jobs, $LPT$ does not
  4. $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}$.
aa-f-083 · level teorema · notes
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$?
  1. $\ell$ goes on the least loaded machine, whose load is at most the average load, which contains only jobs other than $\ell$
  2. Because $\ell$ is the longest job
  3. Because the jobs are sorted by non-increasing time
  4. 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.
aa-f-084 · level facile · notes
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?
  1. $19$
  2. $5$
  3. $\frac{19}{3}$
  4. $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.
aa-f-085 · level facile · notes
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?
  1. $5$ and $4$: ratio $\frac54$
  2. $6$ and $3$: ratio $2$
  3. $5$ and $3$: ratio $\frac53=2-\frac13$
  4. $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.
aa-f-086 · level facile · notes
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?
  1. $12$ and $9$
  2. $11$ and $9$: ratio $\frac{11}{9}=\frac43-\frac19$
  3. $9$ and $9$: $LPT$ is optimal
  4. $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$.
aa-f-087 · level facile · notes
In scheduling $P\,||\,C_{\max}$, $LIST$ guarantees $2-\frac1m$ and $LPT$ guarantees $\frac43-\frac1{3m}$. What are they with $m=4$ machines?
  1. $\frac74$ and $\frac54$
  2. $\frac74$ and $\frac43$
  3. $\frac32$ and $\frac54$
  4. $2$ and $\frac43$
Explanation. $2-\frac14=\frac74$ and $\frac43-\frac1{12}=\frac{15}{12}=\frac54$. As $m$ grows the guarantees tend to $2$ and $\frac43$.
aa-f-088 · level facile · notes
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}$?
  1. $LIST(I)=\mathrm{LB}$ for every list
  2. $LIST(I)\le\mathrm{LB}+1$
  3. $LIST(I)\ge 2\,\mathrm{LB}$ for some instance
  4. $LIST(I)\le\frac1m\sum_jt_j+\max_jt_j\le 2\,\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$.
aa-f-089 · level facile · notes
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$?
  1. $LIST$ $3$, $LPT$ $3$
  2. $LIST$ $4$, $LPT$ $2$
  3. $LIST$ $3$, $LPT$ $2$
  4. $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.
aa-f-121 · level facile · notes
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?
  1. $z(I)\ge m$ and $z(I)\ge n$
  2. $z(I)\ge\mathscr{A}(I)$
  3. $z(I)\ge\max_jt_j$ and $z(I)\ge\frac1m\sum_jt_j$
  4. $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$.
aa-f-122 · level ipotesi · notes
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?
  1. The machines have different speeds
  2. The jobs are examined by non-increasing duration, so the last assigned job is short compared to the optimum
  3. The jobs are examined in random order
  4. 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.
aa-f-147 · level facile · notes
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?
  1. $8$
  2. $7$
  3. $9$
  4. $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$.
aa-f-148 · level facile · notes
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$?
  1. Because the list is sorted by decreasing times
  2. Because the machines are empty at the start
  3. Because the longest job is always the last one
  4. 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.
aa-f-149 · level facile · notes
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?
  1. $6$
  2. $9$
  3. $7$
  4. $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$.
aa-f-150 · level facile · notes
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?
  1. $S_\ell\le24$, makespan $\le27$
  2. $S_\ell\le8$, makespan $\le11$
  3. $S_\ell\le9$, makespan $\le12$
  4. $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$.
aa-f-151 · level teorema · notes
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)$?
  1. $\frac1m\sum_jt_j\le z(I)$ and $t_\ell\le z(I)$
  2. $t_\ell\le\frac1m\sum_jt_j$ and $z(I)\le\sum_jt_j$
  3. $LIST$ is optimal for $m=1$ and $t_\ell\le1$
  4. $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$.
aa-f-301 · level facile · notes
How does the algorithm $LIST$ assign the jobs?
  1. By decreasing duration, in round robin
  2. By solving an ILP model of the instance
  3. In list order, each to the least loaded machine
  4. Each job to the most loaded machine
Explanation. $LIST$ takes the jobs in the given order and puts each on the machine that becomes free first.
aa-f-302 · level facile · notes
How does $LPT$ differ from $LIST$?
  1. It moves jobs after the initial assignment
  2. It first sorts the jobs by non-increasing duration
  3. It assigns every job to the most loaded machine
  4. It uses a single machine for all the jobs
Explanation. $LPT$ is $LIST$ with the list of jobs by decreasing duration: long jobs go first.
aa-f-303 · level facile · notes
Which elementary lower bound holds for $z(I)$ in $P\,||\,C_{\max}$?
  1. $\max\{\max_j t_j,\ \sum_j t_j/m\}$
  2. $\min_j t_j$, the shortest job
  3. $\sum_j t_j$, the sum of the durations
  4. $\max_j t_j/m$
Explanation. The makespan is at least the longest job and at least the average machine load.
aa-f-304 · level facile · notes
Durations $t=(5,4,3,3,3)$ on $m=2$ machines. What is the lower bound $\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}$?
  1. $5$
  2. $18$
  3. $8$
  4. $9$
Explanation. $\sum_j t_j=18$, $18/2=9$, $\max_j t_j=5$: the bound is $9$ (and it is attained, $\{5,4\},\{3,3,3\}$).
aa-f-305 · level facile · notes
With $m=4$ machines, which guarantee does $LIST$ have?
  1. $2$
  2. $\frac{5}{4}$
  3. $\frac74$
  4. $\frac43$
Explanation. $LIST(I)/z(I)\le2-\frac1m=2-\frac14=\frac74$.
aa-f-306 · level facile · notes
Which worst-case ratio does the algorithm $LPT$ guarantee on three identical parallel machines?
  1. $\frac{10}{9}$
  2. $\frac{11}{9}$
  3. $\frac43$
  4. $\frac53$
Explanation. $\frac43-\frac{1}{3m}=\frac43-\frac19=\frac{11}{9}$.
aa-f-307 · level facile · notes
Why does the job $\ell$ that ends last with $LIST$ start at most at the average load of the other jobs?
  1. It goes to the least loaded machine
  2. Because it is the shortest job
  3. Because $LIST$ sorts the jobs
  4. Because all machines have the same load
Explanation. At assignment time the chosen machine has the minimum load, and the minimum does not exceed the average $\frac1m\sum_{j\neq\ell}t_j$.
aa-f-308 · level facile · notes
The guarantee $2-\frac1m$ of $LIST$ is tight: what does it mean?
  1. $LIST$ always has ratio exactly $2-\frac1m$
  2. $LIST$ is optimal on every instance with $m=2$
  3. There is an instance with ratio equal to $2$
  4. For every $m$ an instance attains $2-\frac1m$
Explanation. Proposition 7.3 gives, for every $m\ge2$, an instance and a list that attain the bound.
aa-f-309 · level facile · notes
For $m=2$ the tight instance of $LPT$ has ratio equal to what?
  1. $\frac32$
  2. $\frac65$
  3. $\frac76$
  4. $\frac43$
Explanation. $\frac43-\frac16=\frac76$; for instance durations $(3,3,2,2,2)$: $LPT=7$, optimum $6$.
aa-f-310 · level facile · notes
Durations $(3,3,2,2,2)$ on $m=2$ machines. What is the makespan of $LPT$?
  1. $12$
  2. $7$
  3. $6$
  4. $8$
Explanation. $LPT$: $3\to M_1$, $3\to M_2$, $2\to M_1$ ($5$), $2\to M_2$ ($5$), $2\to M_1$ ($7$). The optimum is $6$: $\{3,3\},\{2,2,2\}$.
aa-f-311 · level facile · notes
Two machines and the list of jobs of durations $2,2,2,2,4$, in this order: which makespan does $LIST$ produce?
  1. $8$
  2. $6$
  3. $12$
  4. $4$
Explanation. $LIST$ puts the four jobs of length $2$ in pairs ($4$ and $4$), then the $4$ on one machine: $8$. The optimum is $6$.
aa-f-312 · level facile · notes
Why does $LPT$ have a better guarantee than $LIST$?
  1. Because $LPT$ is exact
  2. Because $LPT$ uses more machines
  3. Because $LPT$ ignores short jobs
  4. 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.
aa-f-313 · level teorema · notes
Which guarantee does $LIST$ have for every instance and every list?
  1. $LIST(I)\le z(I)+\max_jt_j$, not relative
  2. $LIST(I)\le\frac32z(I)$
  3. $LIST(I)\le\left(2-\frac1m\right)z(I)$
  4. $LIST(I)\le\frac43z(I)$
Explanation. $C_{\max}=S_\ell+t_\ell\le\frac1m\sum_{j\neq\ell}t_j+t_\ell\le z(I)+(1-\frac1m)t_\ell\le(2-\frac1m)z(I)$.
aa-f-314 · level ipotesi · notes
Does the guarantee $2-\frac1m$ of $LIST$ depend on the order of the list?
  1. Yes: only for $m=2$
  2. No: it holds for every list
  3. Yes: only for decreasing durations
  4. Yes: only for increasing durations
Explanation. The proof only uses that every job goes to the least loaded machine; the decreasing order gives the better guarantee of $LPT$.
aa-f-315 · level ipotesi · notes
For which $m$ is the tightness of $2-\frac1m$ for $LIST$ proved?
  1. For every $m\ge2$
  2. Only for $m=2$
  3. Only for even $m$
  4. Only for $m\le3$
Explanation. For every $m\ge2$ Proposition 7.3 builds an instance $I_m$ with ratio exactly $2-\frac1m$.
aa-f-348 · level facile · notes
What is the guarantee of $LPT$ with $m=2$ machines?
  1. $\frac32$
  2. $\frac43$
  3. $\frac54$
  4. $\frac76$
Explanation. $\frac43-\frac{1}{3\cdot2}=\frac76$.
aa-f-349 · level facile · notes
On two machines, which worst-case ratio does the rule $LIST$ have?
  1. $\frac76$
  2. $\frac43$
  3. $\frac32$
  4. $2$
Explanation. $2-\frac12=\frac32$.
aa-f-350 · level facile · notes
Which value does the guarantee of $LIST$ tend to as the number of machines $m$ grows?
  1. $\frac32$
  2. $2$
  3. $\frac43$
  4. $1$
Explanation. $2-\frac1m\to2$; that of $LPT$, $\frac43-\frac{1}{3m}$, tends to $\frac43$.
aa-f-351 · level facile · notes
Three machines and jobs of length $7,2,2,2$: which elementary lower bound is obtained for the optimal makespan?
  1. $7$
  2. $5$
  3. $13$
  4. $4$
Explanation. $\sum_jt_j=13$, $\lceil13/3\rceil=5$, $\max_jt_j=7$: the bound is $7$, and it is the optimum.
aa-f-352 · level facile · notes
Durations $(5,4,3,3,3)$ on $m=2$ machines: which makespan does $LPT$ give?
  1. $9$
  2. $11$
  3. $8$
  4. $10$
Explanation. $5\to M_1$, $4\to M_2$, $3\to M_2$ ($7$), $3\to M_1$ ($8$), $3\to M_2$ ($10$). The optimum is $9$.
aa-f-353 · level facile · notes
With $m=3$ and the other jobs' durations summing to $24$, at most when does the last job $\ell$ of $LIST$ start?
  1. At time $12$
  2. At time $6$
  3. At time $8$
  4. At time $24$
Explanation. $S_\ell\le\frac1m\sum_{j\neq\ell}t_j=24/3=8$.
aa-f-354 · level facile · notes
What mistake does one make saying that $LPT$ is optimal because it puts long jobs first?
  1. $LPT$ is not polynomial
  2. $LPT$ may be non-optimal
  3. None: $LPT$ is optimal
  4. $LPT$ has ratio $2$
Explanation. The tight instances show that $LPT$ can err: $P\,||\,C_{\max}$ is NP-hard.
aa-f-355 · level facile · notes
The tight instances of $LPT$ have $2m+1$ jobs. How many jobs do they have with $m=3$?
  1. $7$
  2. $6$
  3. $9$
  4. $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)$?
  1. $72\le z(I)\le 128$
  2. $72\le z(I)\le 96$
  3. $96\le z(I)\le 128$
  4. $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)$?
  1. $z(I)=16$
  2. $4\le z(I)\le 16$
  3. $4\le z(I)\le 8$
  4. $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?
  1. $\frac{9}{5}$ and $\frac{4}{5}$
  2. $\frac{5}{9}$ and $\frac{4}{9}$
  3. $\frac{9}{5}$ and $\frac{4}{9}$
  4. $\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?
  1. $\frac{5}{36}$ and $\frac{41}{36}$
  2. $\frac{41}{36}$ and $\frac{5}{41}$
  3. $\frac{36}{41}$ and $\frac{5}{36}$
  4. $\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)$?
  1. $33$
  2. $27$
  3. $26$
  4. $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)$?
  1. $33$
  2. $43$
  3. $41$
  4. $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$.
Example 1 · aa-g-kp-fptas · level media · notes
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$?
  1. $p'=(1,0,0,0)$
  2. $p'=(4,3,2,3)$
  3. $p'=(4,2,1,2)$
  4. $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$.
Example 2 · aa-g-kp-fptas · level media · notes
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$?
  1. $p'=(5,5,4,1)$
  2. $p'=(6,6,5,2)$
  3. $p'=(1,1,1,0)$
  4. $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)$?
  1. $FP^{\varepsilon}(I)=8$, $z(I)=78$
  2. $FP^{\varepsilon}(I)=78$, $z(I)=79$
  3. $FP^{\varepsilon}(I)=78$, $z(I)=156$
  4. $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)$?
  1. $FP^{\varepsilon}(I)=82$, $z(I)=164$
  2. $FP^{\varepsilon}(I)=9$, $z(I)=82$
  3. $FP^{\varepsilon}(I)=82$, $z(I)=82$
  4. $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?
  1. $bin=(1,2,2,3,1,4,4)$
  2. $bin=(1,2,2,3,3,4,4)$
  3. $bin=(1,2,1,3,3,2,4)$
  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?
  1. $bin=(1,1,2,3,4,2,4)$
  2. $bin=(1,1,2,3,4,2,3)$
  3. $bin=(1,1,2,3,4,5,5)$
  4. $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.
Example 1 · aa-g-bpp-nf · level facile · notes
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?
  1. $4$, $6$
  2. $6$, $5$
  3. $5$, $4$
  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)$.
Example 2 · aa-g-bpp-nf · level facile · notes
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?
  1. $6$, $4$
  2. $5$, $4$
  3. $6$, $5$
  4. $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?
  1. $NF=5$, $FF=5$, $BF=5$, $WF=5$
  2. $NF=6$, $FF=5$, $BF=5$, $WF=6$
  3. $NF=5$, $FF=6$, $BF=5$, $WF=5$
  4. $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?
  1. $NF=6$, $FF=5$, $BF=5$, $WF=5$
  2. $NF=5$, $FF=6$, $BF=5$, $WF=5$
  3. $NF=6$, $FF=5$, $BF=5$, $WF=6$
  4. $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?
  1. $3$
  2. $4$
  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 $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?
  1. $3$
  2. $5$
  3. $4$
  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?
  1. $3n-6=51$: it can be planar
  2. $3n-6=51$: it is not planar
  3. $3n-6=54$: it is not planar
  4. $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?
  1. $3n-6=39$: it can be planar
  2. $3n-6=39$: it is not planar
  3. $3n-6=36$: it is not planar
  4. $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?
  1. $16$ vertices and $\omega=5$
  2. $16$ vertices and $\omega=2$
  3. $16$ vertices and $\omega=4$
  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?
  1. $8$ vertices and $\omega=6$
  2. $16$ vertices and $\omega=5$
  3. $16$ vertices and $\omega=3$
  4. $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?
  1. $|S|=3$, bound $3$
  2. $|S|=2$, bound $2$
  3. $|S|=4$, bound $2$
  4. $|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?
  1. $|S|=5$, bound $2$
  2. $|S|=4$, bound $2$
  3. $|S|=5$, bound $3$
  4. $|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)

Example 1 · aa-g-tsp-mst · level facile · notes
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?
  1. $15$
  2. $17$
  3. $32$
  4. $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$.
Example 2 · aa-g-tsp-mst · level facile · notes
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?
  1. $34$
  2. $15$
  3. $18$
  4. $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$.
Example 1 · aa-g-tsp-dt · level media · notes
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?
  1. $18$
  2. $36$
  3. $33$
  4. $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.
Example 2 · aa-g-tsp-dt · level media · notes
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?
  1. $18$
  2. $35$
  3. $34$
  4. $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?
  1. $11$, $11$
  2. $10$, $11$
  3. $10$, $10$
  4. $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?
  1. $16$, $12$
  2. $12$, $16$
  3. $12$, $12$
  4. $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?
  1. $\frac{15}{16}$
  2. $\frac{7}{6}$
  3. $\frac{16}{15}$
  4. $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?
  1. $\frac{7}{6}$
  2. $\frac{10}{11}$
  3. $\frac{11}{10}$
  4. $\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}$.