|
Article Excerpt
We examine formulations for the well-known b-matching problem in the presence of integer demands on the edges. A subset M of edges is feasible if for each node v the total demand of edges in M incident to v is at most [b.sub.v]. We examine the system of star inequalities for this problem. This system yields an exact linear description for b-matchings in bipartite graphs. For the demand version, we show that the integrality gap for this system is at least 2.5 and at most 2.764. For general graphs, the gap lies between 3 and 3.264. We also describe a 3-approximation algorithm (2.5 for bipartite graphs) for the cardinality version of the problem. A fully polynomial approximation scheme is also presented for the problem on a tree, thus generalising a well-known result for the knapsack problem. Recently, the notion of demand matching has arisen in the design of Clos network switches.
Key words: b-matching; linear programming; integrality gap; approximation algorithm
1. Introduction. A combinatorial maximum packing problem is determined by a ground set V, each element u of which has an associated profit, denoted [p.sub.u], and a collection F of feasible subsets of V. The objective is to find a feasible set F [member of] F inducing a profit p(F) = [[summation of].sub.u[member of]F] [p.sub.u], of maximum value. Feasibility for such problems is often determined by some set of resource capacities into which at most some bounded number of ground elements can be packed. For instance, in the b-matching problem on a graph, a subset M of its edges is feasible if each node v is incident to at most [b.sub.v] edges of M. We are interested in understanding the relationship of such base problems, where ground elements in effect have a unit size, to their demand version, where the elements each come with an integer demand value. For instance, in the case of b-matchings, each edge e could be additionally supplied with a demand [d.sub.e]. A set M of edges is then feasible if for each node v the total demand of edges in M incident to v does not exceed the capacity [b.sub.v]. Naturally, this gives rise to a completely different collection of feasible sets.
Analysis for such demand problems often requires new methods from those used for the base problem itself. This is largely because the whole demand must be satisfied before its profit may be reaped. Such "all-or-nothing" constraints arise quite naturally in practice; bandwidth trading in communication networks is one such example. In this paper, our attention is restricted exclusively to the case of hard capacity constraints. The quintessential starting place for this study is the knapsack problem. Here an integrality gap of two for the standard linear programming (LP) formulation is well known. Multiple knapsack problems, where the set of packable items is the same for each knapsack, have also been studied from the perspective of providing good approximation algorithms, see Chekuri and Khanna [6]. Our interest, however, lies in understanding how the structure of some base combinatorial problem interacts with its demand version. The demand b-matching problem, for instance, can be viewed as having many parallel knapsacks, one associated with each node. Coupling of the constraints only arises due to each edge being in two different knapsacks.
Theoretical work on the demand versions of combinatorial packing problems has been rather limited. We now review some of this work. One well-studied case of the generalized assignment problem is where each task has a size independent of its assignment. This problem is a special case of the demand-matching problem. To see this, note that the base problem can be viewed as a bipartite b-matching problem with the following property. Every node v on one side of the bipartition has a common demand value (associated with its task) on each of its incident edges, and its by-value is set to be equal to this demand value. The generalized assignment problem, in full generality where sizes may vary for a fixed task, was studied by Shmoys and Tardos [24], even though their focus was on congestion minimization. In fact, some of our techniques and findings bear resemblance to theirs. Their results are revisited and used in Chekuri and Khanna [6], where the maximization form is studied.
A demand version of network flows was studied by Cosares and Saniee (cf. the ring-loading problem of Cosares and Saniee [9]) and by Kleinberg [17], who gave the first general and comprehensive study of the topic. In particular, Kleinberg introduced the term unsplittable flow and, relevant to the study in the present paper, he was the first to examine the maximization form of these problems. One example is the study (Kleinberg [18]), of the maximum single-source unsplittable flow problem. Here, the base combinatorial problem is that of packing paths into an edge-capacitated network. In the single-source setting, one is also given a source s and a collection of terminals [t.sub.1], [t.sub.2], ..., [t.sub.k] with demands [d.sub.1], [d.sub.2], ..., [d.sub.k], respectively. In addition, it is common to require a no-bottleneck condition so that each [d.sub.i] is at most the minimum edge capacity in the network. The packing problem is to satisfy the maximum number of the demands subject to the edge capacity constraints. This problem may be viewed in the "demand" framework as follows. Let each s - [t.sub.i] path have the demand [d.sub.i]. If we add a sink node t and edges tit of capacity [d.sub.i], then the goal is to find a maximum packing of the weighted s - t flow paths. This single-source problem has been further developed in Kolliopoulos and Stein [19], Dinitz et al. [10], and Skutella [25].
Unsplittable flow with general sets of commodities has also been studied. For instance, in Kolliopoulos and Stein [20], the first approximation algorithm for general capacitated maximum unsplittable flow is given. Special classes of graphs have also been examined. Various special cases of the problem of packing subpaths (with demands) in an edge-capacitated path are studied in Farach and Liberatore [13], Bar-Noy et al. [1], and Calinescu et al. [3], although a constant factor approximation for the general problem first appeared in Chakrabarti et al. [4]. This was improved and extended to a constant factor (48) approximation for the maximum profit unsplittable flow problem where the underlying graph is a tree (Chekuri et al. [7]). We mention that the maximum unsplittable flow problem on the tree, without the no-bottleneck assumption, also includes the demand-matching problem, in the case where the tree is a star. Namely, the demand-matching graph may be represented by demand edges between the leaf nodes of the star, and the node capacities are simulated by the edge capacities in the tree.
A traditional attack in solving general packing problems is to find a linear description for the convex hull of incidence vectors of feasible sets. A normal starting point is to formulate an integer program based on some m x n 0, 1 matrix A: max{p x x: Ax [less than or equal to] b, [x.sub.i] [member of] {0, 1}} where any 0, 1 solution identifies a feasible set. For example, if G is bipartite, then its node-edge incidence matrix is totally unimodular. Hence, this matrix immediately yields such a formulation for the b-matching problem (Hoffman and Kruskal [15]), whose relaxation has an integrality gap of one. The demand version of the original 0, 1 packing problem is then: max{p x x: [A.sup.d]x [less than or equal to] b, [x.sub.i] [member of] {0, 1}}, where [A.sup.d] is obtained from A by multiplying each column i by the value [d.sup.i]. In Kolliopoulos and Stein [20], a framework is developed for relating such demand-packing problems to 0, 1 packing problems. They refer to a column-restricted packing integer program as one arising from such a matrix with all nonzero entries in any column the same, and with each [d.sub.i] [less than or equal to] [b.sub.j] for each i, j. (1) They show that bounds on the integrality gap for column-restricted packing problems can be directly tied to bounds on the integrality gaps for general 0, 1 packing problems. The key proof method is called grouping and scaling, whose origin is in the earlier paper Kolliopoulos and Stein [19]. In fact, it follows from their work that a bound of [PHI] on the integrality gap for a family of 0, 1 packing problems translates to an O([phi]) gap for the demand versions of the same family. This is stated explicitly in Chekuri et al. [7] for 0, 1 packing problems arising from an arbitrary fixed matrix A. Specifically, the following result is given, whose proof is implicit in the work of Kolliopoulos and Stein [20]. Let A be a fixed 0, 1 matrix and W be a given class of so-called closed objective functions W. If [phi] is the worst 0, 1 integrality gap of a packing problem for A and objective w [member of] W, for any integral right-hand side b, then the worst gap for any such demand version is at most 11.54[PHI]. Several refinements are stated in Chekuri et al. [7] for application to other problems, and in particular for giving a unified handling, and some improvements, of results in Calinescu et al. [3], Bar-Noy et al. [1], and Chakrabarti et al. [4]. The potential for applying grouping and scaling was missed in these papers.
We largely ignore the congestion minimization form of all of these problems. Connections between the congestion minimization and maximization problems seem not to be fully understood and are worth exploring. For multicommodity flow where the supply graph is a tree, for instance, the congestion problem is trivial. Finding a maximum routable (obeying capacities) subset of the commodities, however, is not. Even the case of unit profits and demands requires a nontrivial analysis (Garg et al. [14]); as mentioned, a constant gap for the general version is given in Chekuri et al. [7].
We close by mentioning a link between demand matchings and the design of a class of communication switches. The switch is modelled as a graph with a bipartition of its nodes 1 [union] O representing its input and output ports. In addition, the edges of the graph come with (fractional) weights representing traffic amounts between corresponding ports. The goal is to schedule transmission of traffic for all edges, using a minimum number of time slots. This amounts to colouring the edges, so that each colour class is a demand matching (where each [b.sub.v] = 1). An introduction to this area and some of its open problems can be found in Ngo and Vu [21] and Du et al. [11]. They consider a model where each node of the bipartite graph has a maximum fractional degree of [DELTA]. Moreover, they assume that at each node v, of fractional degree k, say, the edges incident to v can be partitioned into k "bins," each of whose fractional weight is one. The goal is to find a smallest constant c such that the edges can be partitioned into c[DELTA] demand matchings (asymptotically). The current best such bound on c is 2.548 (Correa and Goemans [8]); there a more general version is studied where the bin condition is weakened and one only requires that the fractional weight of each edge is at most one. The best lower bound for the switch problem is presently given by c = 5/4. At first glance our integrality gap of 2.5 for demand matching in bipartite graphs would seem to suggest a 2.5 lower bound for the above problems. However, our lower-bound examples do not satisfy the extra bin conditions from the switch design problem. In fact, the demands (weights) on our edges are not even bounded by one. It is an interesting question to understand the colouring question when one wishes to partition into general demand matchings.
1.1. The demand-matching...
|
