The Art Gallery Guardian

Maximum weight hierarchical bb-matching


We consider the following problem, which appeared in [1].

Let L\mathcal{L} be a laminar family consists of sets F1,,FkF_1,\ldots,F_k. Let u1,,uku_1,\ldots,u_k to be positive integers. Consider a graph G=(V,E)G=(V,E) with a weight function w:ENw:E\to \N and capacity function c:ENc:E\to \N. We are interested in finding a ycy\leq c, such that for every FiLF_i\in \mathcal{L}, we have vFie:veEyeui\sum_{v\in F_i} \sum_{e:v\in e\in E} y_e \leq u_i, and eEyewe\sum_{e\in E} y_ew_e is maximized.

Formally, it is the following integer program.

maxyZmeweyes.t.vFie:veEyeuii[k]0yeceeE \begin{aligned} & \max_{y\in \Z^m} & & \sum_{e} w_e y_e & \\ & \text{s.t.} & & \sum_{v\in F_i} \sum_{e:v\in e\in E} y_e \leq u_i & i\in [k] \\ & & & 0\leq y_e \leq c_e & \forall e\in E \\ \end{aligned}

This is a generalization of the maximum weight cc-capacitated bb-matching problem. Indeed, we can simply set Fi={vi}F_i = \set{v_i} and ui=biu_i=b_i. However, this problem is actually no more general than the maximum weight cc-capacitated bb-matching problem.

Let AZm×nA \in \Z^{m\times n} be a matrix such that i=1mAi,j2\sum_{i=1}^m |A_{i,j}|\leq 2 for every jj. We call AA a bidirected matrix.

Theorem1

Given AZm×nA \in \Z^{m\times n} a bidirected matrix and vectors a,bZma,b\in \Z^m, c,d,wZnc,d,w\in \Z^n. The integer program maxxZn{wxaAxb,cxd}\max_{x\in \Z^n} \set{wx \mid a\leq Ax\leq b, c\leq x\leq d} can be solved in polynomial time. In particular, it is equivalent to the maximum weight bb-matching problem on graph of size poly(m,n)poly(m,n).

The above theorem can be found in [2]. Note that in Schrijver’s book, one requires i=1mAi,j=2\sum_{i=1}^m |A_{i,j}|=2. It is not hard to see the statement still holds even if we have \leq in place of ==.

We will express the maximum weight hierarchical bb-matching problem as an integer program over a polytope defined over a bidirected matrix. The integer program is a modification of the integer program in [3]. The integer program here is simpler, because we are not trying to reduce to perfect bb-matching.

We define Fi=Fij:FjFiFjF_i' = F_i \setminus \bigcup_{j: F_j\subsetneq F_i} F_j. We also define CiC_i to be the indices jj, such that for all kk, FjFkFiF_j\subseteq F_k \subsetneq F_i implies j=kj=k. yey_e denote the amount of capacities we assign to ee, xvx_v denotes the capacitated degree, hence xv=e:veEyex_v = \sum_{e:v\in e\in E} y_e. We define zi=vFixvz_i = \sum_{v\in F_i} x_v, which can be transformed to zi=vFixv+jCizjz_i = \sum_{v\in F_i'} x_v + \sum_{j\in C_i} z_j. Therefore we obtain the following integer program by directly applying substitutions.

maxxZn,yZm,zZkeweyes.t.vFixv+jCizjzi=0i[k]e:veEyexv=0vV0yeceeE0ziuii[k] \begin{aligned} & \max_{x\in \Z^n,y\in \Z^m, z\in \Z^k} & & \sum_{e} w_e y_e & \\ & \text{s.t.} & & \sum_{v\in F_i'} x_v + \sum_{j\in C_i} z_j - z_i= 0 & i\in [k] \\ & & & \sum_{e: v\in e\in E} y_e -x_v = 0 & \forall v\in V \\ & & & 0\leq y_e \leq c_e & \forall e\in E \\ & & & 0\leq z_i \leq u_i & \forall i\in [k] \\ \end{aligned}

The matrix here is a bidirected matrix. This shows the original problem can be solved in polynomial time.

References

[1] Y. Emek, S. Kutten, M. Shalom, S. Zaks, Hierarchical b-Matching, arXiv E-Prints. (2019) arXiv:1904.10210.

[2] A. Schrijver, Combinatorial Optimization (3 volume, A, B, & C), Springer, 2003.

[3] I.M. Konstantinos Kaparis Adam N. Letchford, On matroid parity and matching polytopes, Department of Management Science, Lancaster University, 2017.

Posted by Chao Xu on .
Tags: combinatorial optimization, matching, matroid.