Approximating max-min weighted T-joins

作者：Iwata Satoru; Ravi R^*

来源：Operations Research Letters, 2013, 41(4): 321-324.

DOI：10.1016/j.orl.2013.03.004

• T-joins
• Max-min optimization
• Bottleneck problem

Given an undirected graph with nonnegative edge weights, the max-min weighted T-join problem is to find an even cardinality vertex subset T such that the minimum weight T-join for this set is maximum. The problem is NP-hard even on a cycle but permits a simple exact solution on trees. We present a 2/3-approximation algorithm based on a natural cut packing upper bound by using an LP relaxation and uncrossing, and relating it to the T-join problem using duality.

• 出版日期2013-7