Многогранник пересечения матроидов

Определение:

Для двух матроидов [math]M_1 = (S, \mathcal{I}_1) [/math] и [math]M_2 = (S, \mathcal{I}_2) [/math] многогранником пересечения (англ. intersection polytope) называется выпуклая оболочка (англ. convex hull) инцидентных векторов общего независимого множества: [math]Conv\{\mathcal{X}(I), I \in \mathcal{I}_1 \cap \mathcal{I}_2 \} (1)[/math]

Теорема:

Пусть [math]r_1[/math] и [math]r_2 : 2^S \mapsto Z_{+}[/math] ранговые функции матроидов [math]M_1 = (S, \mathcal{I}_1) [/math] и [math]M_2 = (S, \mathcal{I}_2) [/math] соответсвенно. Тогда многогранник пересечений [math](1)[/math] эквивалентен множеству [math]\mathit{x} \in R^{S}[/math] , определенным следующей системой общего двойного интегралоа (англ. totally dual integral (TDI)) [math](2)[/math] : [math]x(u) := \sum\limits_{e \in U} x_e \leqslant r_i(U) \mid \forall U \subseteq S , i = 1, 2[/math] [math] x \ge 0[/math]

Доказательство:

[math]\triangleright[/math]

Достаточно показать, что эта система (2) является TDI , так как тогда все точки экстремума будут целыми, и тогда множество вершин будет являться набором инцидентных векторов общего независимого множества для двух матроидов . Для доказательства TDI, рассмотрим следующее двойное линейное программирование для взвешенного вектора [math] \mathit{w} \in Z^{S} (3)[/math]: [math]\max_{x \ge 0: x(u) \leqslant r_i(U), i = 1, 2 } [/math] [math]\mathbf\mathit{w^Tx} = [/math] минимизировать [math] \sum\limits_{U \subseteq S} r_1(U)u_1(U) + \sum\limits_{U \subseteq S} r_2(U)y_2(U)[/math] С учетом того, что [math]\sum\limits_{e \in U} [y_1(U) + y_2(U)] \ge w_e \mid \forall e \in S[/math] и так же [math]y_1, y_2 \ge 0[/math] Заметим, что мы можем предположить [math]w \ge 0[/math] , так как любое отрицательное значение может быть удалено, поскольку оно никак не влияет на целостность двойственности.

[math]\triangleleft[/math]

Утверждение:

Существуют оптимальные решения [math](y_1^*, y_2^*)[/math] для системы [math](3)[/math] , которое удовлетворяет свойствам [math](4) [/math]: [math] y_1^*(U) = 0[/math] [math]\forall U \notin \mathcal{C}_1 [/math] [math] y_2^*(U) = 0 [/math] [math]\forall U \notin \mathcal{C}_2 [/math] для каких-то цепочек [math]\mathcal{C}_1 , \mathcal{C}_2 \subseteq 2^S [/math]

[math]\triangleright[/math]

Пусть [math](y_1^*, y_2^*) [/math] будет оптимальным решением для [math](3)[/math]. Зафиксируем [math] y_2 = y_2^* [/math], и получаем: минимизируем [math] \sum\limits_{U \subseteq S} (r_1(U)y_1(U) + r_2(U)y_2(U)) [/math] при условии [math]\sum\limits_{e \in U} y_1(U) \ge w_e - \sum\limits_{e \in U} y_2^*(U)[/math] [math] \forall e \in S[/math] с учетом того, что [math] y_1 \ge 0 [/math] Это сводится к двойному линейному программированию задачи о максимальном независимом множестве с весом [math]w[/math]. Таким образом, оптимальное решение [math]y_1^*[/math] может быть выбрано для цепочки. Аналогично, делая замену [math]y_1 = y_1^*[/math] , оптимальное решение [math]y_2^*[/math] также может быть выбрано для цепочки. Более того, эти решения удовлетворяют [math] \sum\limits_{U \in \mathcal{C}_1 : e \in U} y_1^*(U) = w_e^{(1)}[/math] [math] \sum\limits_{U \in \mathcal{C}_2: e \in U} y_2^*(U) = w_e^{(2)}[/math] и поэтому [math] \sum\limits_{i = 1}^{2} \sum\limits_{U \subseteq S} y_1^*(U) = w_e [/math] для всех [math]e \in S[/math]

[math]\triangleleft[/math]

Источники информации

• Advanced Combinatorial Optimization, lecture 12