Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut

References

• Aumann Yonatan, Rabani Yuval. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. (1998) 27(1):291–301Crossref, Google Scholar
• Billingsley Patrick. Probability and Measure (1995) (John Wiley & Sons, New York) Google Scholar
• Calinescu G., Karloff H., Rabani Y. An improved approximation algorithm for Multiway Cut. J. Comput. System Sci. (2000) 60(3):564–574Crossref, Google Scholar
• Cunningham W. H., Tang L. Optimal 3-terminal cuts and linear programming. Proc. Seventh Conf. Integer Programming Combin. Optim. (IPCO), Lecture Notes in Computer Science (1999) 1610(Springer-Verlag)114–125Crossref, Google Scholar
• Dahlhaus E., Johnson D. S., Papadimitriou C. H., Seymour P. D., Yannakakis M. The complexity of multi-terminal cuts. SIAM J. Comput. (1994) 23(4):864–894Crossref, Google Scholar
• Even Guy, Naor Joseph (Seffi), Rao Satish, Schieber Baruch. Divide-and-conquer approximation algorithms via spreading metrics. J. Assoc. Comput. Machinery (2000) 47(4):585–616Crossref, Google Scholar
• Goemans Michel X., Williamson David P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Machinery (1995) 42(6):1115–1145Crossref, Google Scholar
• Leighton F. T., Rao S. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. Assoc. Comput. Machinery (1999) 46(6):787–832Crossref, Google Scholar
• Linial Nathan, London Eran, Rabinovich Yuri. The geometry of graphs and some of its algorithmic applications. Combinatorica (1995) 15(2):215–245Crossref, Google Scholar