Neave effect also occurs with Tausworthe sequences
Shu Tezuka
WSC 1991
We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a value rij for each pair of vertices i and j is given, and a minimum-cost set of edges such that there are rij vertex-disjoint paths between vertices i and j must be found. In the case for which rij ∈ {0, 1, 2} for all i, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in which rij = k for all i, j, we can find a solution of cost no more than 2H(k) times optimal, where H(n) = 1 + 1/2 + ⋯ + 1/2. No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems.
Shu Tezuka
WSC 1991
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011