Fully Dynamic All Pairs Shortest Paths
- PDF / 190,278 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 69 Downloads / 214 Views
tor), but more efficiently. Two such examples, that appear in [7], are mentioned here. Theorems 1, 2 can be applied for the improvement of the running time of the algorithm by Lenstra, Shmoys, and Tardos [5] for the scheduling of unrelated parallel machines without preemption (RjjCmax ): N jobs are to be scheduled on M machines, with each job i scheduled on exactly one machine j with processing time pij , so that the maximum total processing time over all machines is minimized. Then, for any fixed r > 1, there is a deterministic (1 + r)-approximation algorithm that runs in O(M 2 N log2 N log M) time, and a randomized version that runs in O(M N log M log N) expected time. For the version of the problem with preemption, there are polynomial-time approximation schemes that run in O(M N 2 log2 N) time and O(M N log N log M) expected time in the deterministic and randomized case respectively. A well-known lower bound for the metric Traveling Salesman Problem (metric TSP) on N nodes is the HeldKarp bound [2], that can be formulated as the optimum of a linear program over the subtour elimination polytope. By using a randomized minimum-cut algorithm by Karger and Stein [3], one can obtain a randomized approximation scheme that computes the Held-Karp bound in O(N 4 log6 N) expected time.
F
Cross References Minimum Makespan on Unrelated Machines Recommended Reading 1. Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4, 86–107 (1994) 2. Held, M., Karp, R.M.: The traveling-salesman problem and minimum cost spanning trees. Oper. Res. 18, 1138–1162 (1970) ˜ 2 ) algorithm for minimum cut. 3. Karger, D.R., Stein, C.: An O(n In: Proceeding of 25th Annual ACM Symposium on Theory of Computing (STOC), 1993, pp. 757–765 4. Leighton, F.T., Makedon, F., Plotkin, S.A., Stein, C., Tardos, É., Tragoudas, S.: Fast approximation algorithms for multicommodity flow problems. J. Comp. Syst. Sci. 50(2), 228–243 (1995) 5. Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. Ser. A 24, 259–272 (1990) 6. Plotkin, S.A., Shmoys, D.B., Tardos, É.: Fast approximation algorithms for fractional packing and covering problems. In: Proceedings of 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 495–504 7. Plotkin, S.A., Shmoys, D.B., Tardos, É.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2) 257–301 (1995). Preliminary version appeared in [6] 8. Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM 37, 318–334 (1990) 9. Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp. 538–546
Open Problems The main open problem is the further reduction of the running time for the approximate solution of the various fractional problems. One direction would be to improve the bounds for
Data Loading...
