Minimum transversals of maximum matchings as approximate solutions to the bisection problem (Q1913329)

The bisection problem requires to find a partition of the vertex set of a given complete graph with \(2m\) vertices and weighted edges into two parts of size \(m\), optimizing the sum of the (nonnegative) weights of the internal edges. The problem is NP-complete. If the objective function is to be maximized and the edges satisfy the triangle inequality, approximate solutions are obtained by first determining a maximum weight matching and then selecting a bisection that does not cut any of the matching edges---a heuristic which is poor if the objective function is to be minimized. The paper proves the following theorem: Given a weighted complete graph satisfying the relaxed triangle inequality \(c(u,v)\leq\tau\cdot(c(u,w)+c(w,v))\) for all \(u,v,w\in X\) for some \(\tau\geq 1\), the minimum weight \(c_{\text{trans}}\) of (``\(M\)-transversal'') bisections cutting all edges of a given maximum weight perfect matching \(M\) is bounded from above in terms of the weight \(c_{\min}\) of an overall minimum bisection as follows: \(c_{\text{trans}}\leq(\tau^2+{1\over 2}\tau+{1\over 2})\cdot c_{\min}\). In this inequality, for each fixed \(\tau\geq 1\), the factor \(\tau^2+{1\over 2}\tau+{1\over 2}\) is asymptotically best possible.