Approximating Max-Min Weighted T-join
Satoru Iwata
RIMS, Kyoto University, Kyoto, Japan
RIMS, Kyoto University, Kyoto, Japan
2011/11/11 Fri 4PM-5PM
Given an even subset T of the vertices of an undirected graph, a T-join is a subgraph in which the subset of vertices with odd degree is exactly T. Given edge weights, the weighted T-join problem is to find a T-join of minimum weight. With nonnegative edge weights, the problem can be reduced to finding a minimum weight perfect matching on the metric completion of the vertices in T.
Given an undirected graph with nonnegative edge weights but no specific T, 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 unweighted case of the problem when all weights are either unit or infinity has been well characterized by a decomposition of the underlying graph into factor critical and matching-covered bipartite subgraphs (Frank1993). We consider the weighted version which is NP-hard even on a cycle. After showing a simple exact solution on trees, we present a 2/3-approximation algorithm for the general case. Our algorithm is based on a natural cut packing upper bound obtained using an LP relaxation and uncrossing, and relating it to the T-join problem using duality.
This is a joint work with R. Ravi.
Given an undirected graph with nonnegative edge weights but no specific T, 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 unweighted case of the problem when all weights are either unit or infinity has been well characterized by a decomposition of the underlying graph into factor critical and matching-covered bipartite subgraphs (Frank1993). We consider the weighted version which is NP-hard even on a cycle. After showing a simple exact solution on trees, we present a 2/3-approximation algorithm for the general case. Our algorithm is based on a natural cut packing upper bound obtained using an LP relaxation and uncrossing, and relating it to the T-join problem using duality.
This is a joint work with R. Ravi.
Tags: SatoruIwata