Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142339 | Operations Research Letters | 2013 | 4 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Satoru Iwata, R. Ravi,