On a bidirected relaxation for the MULTIWAY CUT problem

In this paper, we study a bidirected linear programming relaxation of MULTIWAY CUT. We resolve an open problem posed by Vazirani [Approximation Algorithms, first ed., Springer, Berlin, Heidelberg, 2001], and show that the integrality gap of this relaxation is not better than that for a geometric linear programming relaxation given by Caˇlinescu et al. [J. Comput. System Sci. 60(3) (2000) 564-574], and may be strictly worse on some instances.