Maximum weight hierarchical -matching
We consider the following problem, which appeared in .
Let be a laminar family consists of sets . Let to be positive integers. Consider a graph with a weight function and capacity function . We are interested in finding a , such that for every , we have , and is maximized.
Formally, it is the following integer program.
This is a generalization of the maximum weight -capacitated -matching problem. Indeed, we can simply set and . However, this problem is actually no more general than the maximum weight -capacitated -matching problem.
Let be a matrix such that for every . We call a bidirected matrix.
Given a bidirected matrix and vectors , . The integer program can be solved in polynomial time. In particular, it is equivalent to the maximum weight -matching problem on graph of size .
The above theorem can be found in . Note that in Schrijver’s book, one requires . It is not hard to see the statement still holds even if we have in place of .
We will express the maximum weight hierarchical -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 . The integer program here is simpler, because we are not trying to reduce to perfect -matching.
We define . We also define to be the indices , such that for all , implies . denote the amount of capacities we assign to , denotes the capacitated degree, hence . We define , which can be transformed to . Therefore we obtain the following integer program by directly applying substitutions.
The matrix here is a bidirected matrix. This shows the original problem can be solved in polynomial time.
 Y. Emek, S. Kutten, M. Shalom, S. Zaks, Hierarchical b-Matching, arXiv E-Prints. (2019) arXiv:1904.10210.
 A. Schrijver, Combinatorial Optimization (3 volume, A, B, & C), Springer, 2003.
 I.M. Konstantinos Kaparis Adam N. Letchford, On matroid parity and matching polytopes, Department of Management Science, Lancaster University, 2017.