查看文章

In this paper, we provide a survey and explanation of several methods for approximating the NP-hard problem of finding a multiway separator in a graph. This is motivated by the problem of assigning nodes in an ethernet switch connected testbed without violating bandwidth constraints. As a critical component of the multiway separator problem, we discuss in some detail the sparse cut problem, with several modern ا (log) approaches, which result in realizable ا (log2) approximations to the multiway separator problem, and some even better theoretical bounds. Finally, we conclude with a less formal discussion of the mapping of the more general typed-nodes testbed problem to the multiway separator problem.