## Approximation Algorithms for NP-Hard Problems

### Errata

Back to Hochbaum main page

• Page xvi line 7:
	R_A(I) =A(I)/OPT(I) \leq \delta .


• Page xvi line -14:
	approximation


• Page 7, top two displayed expressions:
q_k in each of them should be q_c.

• Page 7, line 13 of section 1.2.2. (right before "Algorithm NS"):
P_d should be J_d.

• Page 8, line 14:
r_k should be q_h.

• Page 11, line 12:
Replace the word "smaller" with "bigger".

• Page 13, line -2:
"The sum of these intervals" should be "The sum of the lengths of these intervals".

• Page 14 line -16:
C^*_max is missing in the expression in Theorem 1.5. Replace the formula "C^LPT_max \leq 4/3 -1/3m" with:
	C^LPT_max \leq (4/3 -1/3m) C^*_max


• Page 16, displayed expression in middle of page:
On both lines, a "minus" (-) should be a "plus"(+) in the following spot:
	\sum_{j\in\cal J} p_j + \sum_{i=1}^m ...
^


• Page 16, paragraph beginning "Suppose that there are k...":
Need to insert a phrase as follows:
	Suppose that there are k such jobs (1\le k\le m-1) that
begin on or before $t_s$ and complete at or after time t_f;
without loss of generality, assume these are jobs J_1,\ldots,J_k,
and let \alpha = \max_{1\le j\le k} (s_j - r_j).

In other words, insert the phrase, "without loss of generality, assume these
are jobs J_1,\ldots,J_k,".


• Page 24 line 8:
	\le p_{i1}^{max}+\sum_{s=1}^{k_i-1} \sum_{j=1}^n p_{ij} \bar{y}(v_{is},w_j)
\le ..

^^^^^^^^^^^         ^^^^^^^^^^^^^^^^^^

i.e., add summation and replace \bar{y}_{ij} by \bar{y}(v_{is},w_j)

• Page 40 last line:
	\sum_{k=1}^j
i

i.e., replace k by i in summation.

• Page 51 line 2:
Inequality should be:
	W(L) \leq (17/10)*OPT(L)


• Page 62 line 19:
	X={1/4,1/3,/1/2,2/3}
^


• Page 132 line -11:
	O(n) variables and O(m+n^2) edges
^


• Page 234 the reference [KPR91] is incorrect. The correct reference is:
  Philip Klein and Serge A. Plotkin and Satish Rao.
Excluded minors, network decomposition, and multicommodity flow.
STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. 1993,
pages 682--690, San Diego, California, United States


• Page 354 line -4:
Replace the sentence starting with "Now choose..." with:
	Recursively remove from G[V-F] degree one vertices and choose a
disjoint or almost disjoint cycle (if one exists) or the entire
remaining graph.


• Page 364 lines -14 and -5:
Replace the definitions of k and T from "k=1/[4 \epsilon ^2 P_0]", " T=1[2 \epsilon P_0]" to:
	k=1/4 [\epsilon ^2 P_0]
T=1/2 [\epsilon P_0]


• Page 371 line 8:
         2S6K should be 256K.


• Page 372 in Lemma 9.7:
        "...and I is the shifting..."  should be
"...and l is the shifting...".
^^^


• Page 378 line 5 in Section 9.4.1:
        "cost(S)=\max_{i\in S} \min_j C_{ij}"  should be
"cost(S)=\max_{i\in V} \min_{j\in S} C_{ij}".


• Page 381 line 9:
Insert after the line:
	Let BOTTLENECK(w)=(V,E(w)), where E(w)={e \in E|c_e \leq w},
that is,the subgraph containing all edges with cost not exceeding w.


• Page 389 line 16 from bottom and line 14 from bottom:
         OPT(J) should be OPT(I).


• Page 390 Exercise 9.4 line 2 and line 4:
         OPT(J) should be OPT(I).


• Page 462 line 7 and 9:
         \frac{arccos v_i v_j}{\pi} instead of arccos \frac{v_i v_j}{\pi}, and
\frac{arccos v_i v_j}{2\pi} instead of arccos \frac{v_i v_j}{2\pi}


• Page 571 line 9:
         In the definition of [IS} Independent set:
"is minimized" should be "is maximized".


• Page 567 line 19:
         In the definition of [k-CMM] the objective running
index should be p and the min should read max as here:
"max_{p=1,...,k}max_{i,j\in V_p} w_{(i,j)}".


Approximation Algorithms for NP-Hard Problems
Edited by Dorit S. Hochbaum