Approximating max–min weighted TT-joins

Given an undirected graph with nonnegative edge weights, the max–min weighted TT-join problem is to find an even cardinality vertex subset TT such that the minimum weight TT-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/32/3-approximation algorithm based on a natural cut packing upper bound by using an LP relaxation and uncrossing, and relating it to the TT-join problem using duality.