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