R_A(I) =A(I)/OPT(I) \leq \delta .

approximation

C^LPT_max \leq (4/3 -1/3m) C^*_max

\sum_{j\in\cal J} p_j + \sum_{i=1}^m ... ^

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,".

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

\sum_{k=1}^j ii.e., replace k by i in summation.

W(L) \leq (17/10)*OPT(L)

X={1/4,1/3,/1/2,2/3} ^

O(n) variables and O(m+n^2) edges ^

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

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.

k=1/4 [\epsilon ^2 P_0] T=1/2 [\epsilon P_0]

2S6K should be 256K.

"...and I is the shifting..."

"cost(S)=\max_{i\in S} \min_j C_{ij}"

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.

OPT(J) should be OPT(I).

OPT(J) should be OPT(I).

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

In the definition of [IS} Independent set: "is minimized" should be "is maximized".

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)}".

Address: Department of Industrial Engineering

"Copyright 1997, PWS Publishing Company, Boston, MA. This material may not be copied, reproduced, or distributed in any form without permission from the publisher."