= Hall allocation model
{c}
In a unit-capacity <assignment problem>, left <vertices> represent demands and right <vertices> represent individually usable resources; an <edge> records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. <Hall's marriage theorem> decides feasibility. Costs belong to an additional <mathematical optimization> problem; precedence between jobs or requirements for consecutive slots need additional modelling.
The authored <Notes on the design of a conference scheduler by David R. MacIver> (Implementation, 7 August 2022) illustrates a <Hall obstruction> with four talks confined to three slots. With one talk per slot, that <subset> has size four and a <graph neighbourhood> of size three. An unused slot outside its <graph neighbourhood> does not remove the bottleneck. In the three-job example above, the same <scheduling> model instead has two complete assignments.
The allocation exercise in <Graph Theory by Reinhard Diestel> (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint <subsets> $D_i\subseteq A_i$ of prescribed nonnegative <integer> sizes $d_i$. Replace demand $i$ by $d_i$ left <vertices> with allowed resource <set> $A_i$. <Hall's marriage theorem> gives exactly the condition
$$
\left|\bigcup_{i\in I}A_i\right|\geq\sum_{i\in I}d_i\qquad\text{for every index subset }I.
$$
For a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ to two leaves both individual tests valid but demands four distinct resources from a <set union> of size three. This is the same collective obstruction with repeated demand <vertices>.
Back to article page
