Approximation Algorithms for NP-Hard Problems


Back to Hochbaum main page

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

  • Page xvi line -14:

  • 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:
    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:

  • 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
    Address: Department of Industrial Engineering
    Operations Research, Etcheverry Hall
    University of California, Berkeley, CA 94720-1777
    "Copyright 1997, PWS Publishing Company, Boston, MA. This material may not be copied, reproduced, or distributed in any form without permission from the publisher."

    Back to Hochbaum main page