割り当て問題

バランスのとれた割り当て問題では、二部グラフの両方の部分が同じ数の頂点を持ち、それをnで表します。

バランスのとれた割り当てのための最初の多項式時間アルゴリズムの1つは、ハンガリーアルゴリズムでした。これはグローバルアルゴリズムであり、増加パス（マッチングされていない頂点間の交互パス）に沿ったマッチングの改善に基づいています。フィボナッチヒープを 使用した場合の実行時間複雑度は、${\displaystyle O(mn+n^{2}\log n)}$[ ^{2 ]}ここでmはエッジの数です。これは現在、この問題に対する強力な多項式アルゴリズムの中で最速の実行時間です^。ハンガリーアルゴリズムのいくつかのバリアントは、GPU アクセラレーションを含む並列計算からも恩恵を受けています。^{[ 3 ]}すべての重みが整数の場合、実行時間は次のように改善できます。 ${\displaystyle O(mn+n^{2}\log \log n)}$しかし、結果として得られるアルゴリズムは弱多項式にすぎない。^{[ 4 ]}重みが整数であり、すべての重みが最大でC（C > 1は整数）である場合、この問題はで解くことができる。${\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}$重みスケーリングと呼ばれる手法では、弱多項式時間で実行できます。^{[ 5 ] [ 6 ] [ 7 ]}

グローバルな方法に加えて、ローカルな更新を見つけることに基づくローカルな方法もあります（完全な増加パスではなく）。これらの方法は漸近的な実行時間の保証は劣りますが、実際にはうまくいくことが多いです。これらのアルゴリズムは、オークションアルゴリズム、プッシュリラベルアルゴリズム、またはプリフロープッシュアルゴリズムと呼ばれます。これらのアルゴリズムの一部は同等であることが示されています。^{[ 8 ]}

局所的な方法の中には、グラフが完全マッチングを許容することを前提としているものがあります。そうでない場合、これらの方法の中には永遠に実行され続けるものもあります。^{[ 1 ] : 3}この問題を解決する簡単な技術的方法は、入力グラフに非常に大きな重みを持つ人工的なエッジを追加して、完全な二部グラフ に拡張することです。これらの重みは、可能な解に人工的なエッジが出現しないように、既存のすべてのマッチングの重みを超える必要があります。

Mulmuley、Vazirani、Vaziraniら^{[ 9 ]}が示したように、最小重み完全マッチングの問題は、グラフの隣接行列におけるマイナーの探索に変換される。分離補題を用いると、グラフにおける最小重み完全マッチングは、少なくとも1/2の確率で見つけることができる。n個の頂点を持つグラフの場合、${\displaystyle O(\log ^{2}(n))}$時間。

不均衡割り当て問題では、二部グラフの大きい方の部分はn 個の頂点を持ち、小さい方の部分はr < n個の頂点を持ちます。また、グラフ内の最大マッチングの濃度以下である定数sが存在します。目標は、サイズがちょうどsの最小コストマッチングを見つけることです。最も一般的なケースは、グラフが片側完全マッチング (つまり、サイズrのマッチング) を許容し、s = rとなる場合です。

不均衡な割り当ては均衡な割り当てに還元できます。単純な還元方法は、追加することです。${\displaystyle nr}$小さい方の部分に新しい頂点を追加し、コスト0のエッジを使用して大きい方の部分にそれらを接続します。ただし、これには${\displaystyle n(nr)}$新しい辺。より効率的な縮小法は倍増法と呼ばれる。ここでは、新しいグラフG'G' は、元のグラフGの 2 つのコピー、順方向コピーGfと逆方向コピーGb から構築されます。逆方向コピーは「反転」され、G'の各辺にn + r個の頂点が存在するようになります。コピー間には、2 種類の連結辺を追加する必要があります。^{[ 1 ] : 4–6}

• 大きい方から大きい方へ： Gfの大きい方の部分の各頂点から、 Gbの対応する頂点へコストゼロのエッジを追加します。
• 小から小へ：元のグラフに片側完全マッチングがない場合、Gfの小さい部分の各頂点から、 Gbの対応する頂点に非常にコストの高いエッジを追加します。

総じて、最大${\displaystyle n+r}$新しいエッジが必要です。結果として得られるグラフは常にサイズが完全に一致します。${\displaystyle n+r}$このグラフにおける最小コスト完全マッチングは、GfおよびGb における最小コスト最大カーディナリティマッチングから構成される必要があります。 この倍増手法の主な問題点は、速度向上がないことです。${\displaystyle r\ll n}$。

削減法を用いる代わりに、不均衡な割り当て問題は、均衡な割り当てのための既存のアルゴリズムを直接一般化することによって解決できる。ハンガリーアルゴリズムは、この問題を一般化して解決することができる。${\displaystyle O(ms+s^{2}\log r)}$強多項式時間。特に、s = rの場合、実行時間は${\displaystyle O(mr+r^{2}\log r)}$重みが整数の場合、Thorup の方法を使用して実行時間を取得できます。${\displaystyle O(ms+s^{2}\log \log r)}$[ ^{1 ] : 6​}

The assignment problem can be solved by presenting it as a linear program. For convenience we will present the maximization problem. Each edge (i,j), where i is in A and j is in T, has a weight ${\textstyle w_{ij}}$. For each edge ⁠${\displaystyle (i,j)}$⁠ we have a variable ${\textstyle x_{ij}}$_. The variable is 1 if the edge is contained in the matching and 0 otherwise, so we set the domain constraints: $${\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}$$$${\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}$$

The total weight of the matching is: $\displaystyle \sum _{(i,j)\in A\times T}w_{ij}x_{ij}}$. The goal is to find a maximum-weight perfect matching.

To guarantee that the variables indeed represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i.e., $${\displaystyle {\begin{aligned}\sum _{j\in T}x_{ij}&=1{\text{ for }}i\in A\\\sum _{i\in A}x_{ij}&=1{\text{ for }}j\in T\end{aligned}}}$$

All in all we have the following LP:

$${\displaystyle {\begin{aligned}{\text{maximize}}&\sum _{(i,j)\in A\times T}w_{ij}x_{ij}\\{\text{subject to}}&\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T\\&0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T\\&x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T\end{aligned}}}$$ This is an integer linear program. However, we can solve it without the integrality constraints (i.e., drop the last constraint), using standard methods for solving continuous linear programs. While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values. This is because the constraint matrix of the fractional LP is totally unimodular – it satisfies the four conditions of Hoffman and Gale.

Other approaches for the assignment problem exist and are reviewed by Duan and Pettie^[10] (see Table II). Their work proposes an approximation algorithm for the assignment problem (and the more general maximum-weight matching problem), which runs in linear time for any fixed error bound.