TY - JOUR

T1 - Finding Well-Balanced Pairs of Edge-Disjoint Trees in Edge-Weighted Graphs

AU - Bang-Jensen, Jørgen

AU - Goncalves, Daniel

AU - Gørtz, Inge Li

PY - 2007

Y1 - 2007

N2 - The well-known number partition problem is NP-hard even in the following version: Given a set S of n non-negative integers; partition S into two sets X and Y such that vertical bar X vertical bar = vertical bar Y vertical bar and the sum of the elements in X is as close as possible to the sum of the elements in Y (or equivalently, minimize the maximum of the two sums). In this paper we study the following generalization of the partition problem: given an edge-weighted graph G containing two edge-disjoint spanning trees. Find a pair of edge-disjoint spanning trees such that the maximum weight of these two trees is as small as possible. In the case when G is precisely the union of two trees this problem may be seen as a generalization of the partition problem in which we have added a graph structure to the numbers (through the edges) and the extra restriction that only the sets X and Y which correspond to trees in G are valid partitions. We first show how to obtain a 2-approximation via an algorithm for weighted matroid partition. Then we describe a simple heuristic which when applied to the 2-approximation above will result in a solution whose value is no more than 3/2 times the value of an optimal solution. We also show that the approach above may sometimes exclude all the optimal solutions. Both the partition problem and its generalization to the problem above on edge-disjoint spanning trees are special cases of the problem of finding, in a weighted matroid with two disjoint bases, a pair of disjoint bases which minimize the maximum of their weights. In the last part of the paper we give some results on this problem for transversal matroids which turn out to be analogous to those for graphs.

AB - The well-known number partition problem is NP-hard even in the following version: Given a set S of n non-negative integers; partition S into two sets X and Y such that vertical bar X vertical bar = vertical bar Y vertical bar and the sum of the elements in X is as close as possible to the sum of the elements in Y (or equivalently, minimize the maximum of the two sums). In this paper we study the following generalization of the partition problem: given an edge-weighted graph G containing two edge-disjoint spanning trees. Find a pair of edge-disjoint spanning trees such that the maximum weight of these two trees is as small as possible. In the case when G is precisely the union of two trees this problem may be seen as a generalization of the partition problem in which we have added a graph structure to the numbers (through the edges) and the extra restriction that only the sets X and Y which correspond to trees in G are valid partitions. We first show how to obtain a 2-approximation via an algorithm for weighted matroid partition. Then we describe a simple heuristic which when applied to the 2-approximation above will result in a solution whose value is no more than 3/2 times the value of an optimal solution. We also show that the approach above may sometimes exclude all the optimal solutions. Both the partition problem and its generalization to the problem above on edge-disjoint spanning trees are special cases of the problem of finding, in a weighted matroid with two disjoint bases, a pair of disjoint bases which minimize the maximum of their weights. In the last part of the paper we give some results on this problem for transversal matroids which turn out to be analogous to those for graphs.

U2 - 10.1016/j.disopt.2007.09.003

DO - 10.1016/j.disopt.2007.09.003

M3 - Journal article

VL - 4

SP - 334

EP - 348

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

IS - 3-4

ER -