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

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Minimum transversals of maximum matchings as approximate solutions to the bisection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1913329)