Answer: Polynomial-time solvable in \(m,\tau,L\), including exact lexicographic tie-breaking and polynomial-size rational output.
Theorem 5.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximate$\match$ can be executed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set \(T\) of complete hospital templates, rational masses \(\mu_t\), and a split \(q_{t,b}\) of each type across the two sides of a fixed bipartition, compute a feasible mass matching of maximum total matched-pair mass. Each template specifies finitely many client slots, its internal compatibility graph, and its slot compatibilities with every other template; each unit of hospital mass uses an internal maximum matching, and external matches join only compatible slots on opposite sides, with each slot used at most once per unit. Break ties by a fixed order on types.
A society is given by its support: a list \(T\) of \(\tau\) hospital types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible templates.
Each type has a finite labeled slot set \(S_t\), a simple undirected internal compatibility graph on \(S_t\), and explicitly listed symmetric slot compatibilities between distinct hospitals of every pair of types, including equal types. Put \(m=\sum_t|S_t|\); let \(L\) be the total input bit length.
The fixed bipartition is supplied as binary-rational masses \(q_{t,b}\geq0\), where \(b\in\{1,2\}\) and \(q_{t,1}+q_{t,2}=\mu_t\). Each hospital belongs wholly to one side; hospital mass is nonatomic.
A feasible mass matching partitions each cell \((t,b)\) into finitely many nonnegative rational submasses, each labeled by an actual maximum-cardinality matching of the internal graph. These internal matchings are chosen jointly with the external matches.
External matches are nonnegative rational pair masses between compatible slot classes on opposite sides, including opposite-side hospitals of the same type. For each slot class, total incident external mass cannot exceed its mass left uncovered by the chosen internal matchings; no slot is used twice in any hospital unit.
The objective is total internal matched-pair mass plus total external matched-pair mass, counting each pair once. Among maximizers, lexicographically maximize matched-slot mass in each cell, ordering side \(1\) before side \(2\) and types within each side by a supplied fixed order; any remaining tie is allowed. Represent a solution by its nonzero internal submasses and external pair masses.
Is computing an optimal feasible mass matching with this tie-breaking solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite hospitals, maximizing matching cardinality subject to maximum internal matchings and opposite-side external edges, with serial hospital-utility tie-breaking, is polynomial-time computable ([source](https://eprints.gla.ac.uk/131324/7/131324.pdf)).
No result settling this exact continuous problem was located in the literature search.
Computing the required optimal mass matching, including the lexicographic tie-breaking and the specified output representation, is polynomial-time solvable in \(m,\tau,L\).
The key is that rational mixtures of internal matchings are permitted. Their feasible marginal vectors form matching polytopes, for which both optimization and constructive decomposition are polynomial-time operations.
We use the following standard results.
The latter two are the rational-polyhedral oracle and constructive decomposition results of [Grötschel, Lovász, and Schrijver](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf). We verify their encoding and oracle hypotheses below.
For each type \(t\), write its internal graph as \(G_t=(S_t,E_t)\), and let \(k_t\) be its maximum matching cardinality. Compute \(k_t\) using a maximum-cardinality matching algorithm.
Define its matching polytope by
\(\displaystyle P_t=\operatorname{conv}\{\chi^M:M\text{ is a matching of }G_t\}.\)
Here \(\chi^M\in\{0,1\}^{E_t}\) is the edge-incidence vector of \(M\). Define
\(\displaystyle F_t=\left\{p\in P_t:\sum_{e\in E_t}p_e=k_t\right\}.\)
Claim. \(F_t\) is exactly the convex hull of the incidence vectors of maximum-cardinality internal matchings.
Proof. Every matching \(M\) satisfies \(|M|\leq k_t\). If
\(\displaystyle p=\sum_j\lambda_j\chi^{M_j},\qquad \lambda_j\geq0,\qquad \sum_j\lambda_j=1,\)
then
\(\displaystyle \sum_{e\in E_t}p_e=\sum_j\lambda_j|M_j|\leq k_t.\)
Equality holds only if every \(M_j\) with \(\lambda_j>0\) has cardinality \(k_t\): otherwise the weighted average is strictly smaller. Conversely, every convex combination of maximum-cardinality matchings has edge sum \(k_t\). This proves the claim.
For cell \(c=(t,b)\), let \(z_{c,e}\) denote the mass internally matched along edge \(e\). The exact condition for an allowable internal distribution is therefore
\(\displaystyle z_c\in q_{t,b}F_t.\)
When \(q_{t,b}=0\), this means \(z_c=0\).
For \(q_{t,b}>0\), a rational decomposition
\(\displaystyle \frac{z_c}{q_{t,b}}=\sum_j\lambda_{c,j}\chi^{M_{c,j}}\)
gives the required internal submasses \(y_{c,j}=q_{t,b}\lambda_{c,j}\), each labeled by an actual maximum-cardinality matching.
Let \(\mathcal A\) be the set of allowed external pairs. Each element has one endpoint \(v=(t,1,s)\) and the other \(w=(u,2,r)\). Include precisely the explicitly compatible pairs, including \(t=u\).
Introduce a nonnegative variable \(x_a\) for each \(a\in\mathcal A\). For slot class \(v=(t,b,s)\), define
\(\displaystyle I_v(z)=\sum_{\substack{e\in E_t\\s\in e}}z_{(t,b),e},\qquad X_v(x)=\sum_{\substack{a\in\mathcal A\\v\in a}}x_a.\)
Consider the polytope \(Q\) specified by
\(\displaystyle z_{(t,b)}\in q_{t,b}F_t\quad\text{for every cell},\)
\(\displaystyle x_a\geq0\quad\text{for every }a\in\mathcal A,\)
\(\displaystyle I_{(t,b,s)}(z)+X_{(t,b,s)}(x)\leq q_{t,b}\quad\text{for every slot class}.\)
The last inequality says exactly that external mass cannot exceed the mass of that slot left uncovered internally.
Given internal submasses \(y_{c,j}\) labeled by maximum internal matchings \(M_{c,j}\), put
\(\displaystyle z_{c,e}=\sum_{j:e\in M_{c,j}}y_{c,j}.\)
The internal distribution satisfies the scaled-face constraint from Section 2. The supplied external masses satisfy the slot-capacity constraints by feasibility. Thus the resulting \((z,x)\) belongs to \(Q\).
For each positive-mass cell, decompose \(z_c/q_c\) into maximum internal matchings, obtaining rational submasses \(y_{c,j}\).
We must also check that aggregate slot capacities suffice for actual simultaneous external matching. Choose a common positive integer denominator \(D\) for all \(q_c,y_{c,j},x_a\). Represent cell \(c\) by \(Dq_c\) hospital copies, each carrying mass \(1/D\), and assign matching \(M_{c,j}\) to \(Dy_{c,j}\) copies.
The number of exposed copies of slot class \(v=(t,b,s)\) is
\(\displaystyle D\bigl(q_{t,b}-I_v(z)\bigr).\)
For each incident external pair \(a\), allocate \(Dx_a\) exposed copies of this slot to \(a\). The allocations can be disjoint because
\(\displaystyle \sum_{a\ni v}Dx_a\leq D\bigl(q_{t,b}-I_v(z)\bigr).\)
For each external pair \(a=\{v,w\}\), pair its allocated endpoints bijectively. Every slot is used at most once. Its endpoints belong to opposite sides, so they belong to distinct hospitals, including when their types agree.
The allocations for different slot labels can be made independently: a hospital may use several distinct slots, and the prohibition concerns reusing a slot. Interpreting each copy as a nonatomic submass of size \(1/D\) proves realizability.
The algorithm outputs rational masses directly; this denominator construction is an existence proof of their simultaneous feasibility.
Because every internal matching assigned to type \(t\) has cardinality \(k_t\), the internal matched-pair mass is the constant
\(\displaystyle C=\sum_{t\in T}\sum_{b=1}^2k_tq_{t,b}=\sum_{t\in T}k_t\mu_t.\)
Consequently, maximizing the primary objective is equivalent to maximizing
\(\displaystyle H(x)=\sum_{a\in\mathcal A}x_a.\)
For cell \(c=(t,b)\), its matched-slot mass is
\(\displaystyle U_c(z,x)=2k_tq_{t,b}+\sum_{s\in S_t}X_{(t,b,s)}(x).\)
The internal term counts both endpoints of every internal pair. The external term counts each external endpoint belonging to the cell. Thus \(U_c\) is exactly the requested utility.
Let \(c_1,\ldots,c_{2\tau}\) be the supplied cell order. Apply sequential exact linear optimization:
At each stage the feasible region is the set of maximizers of the preceding objectives. Therefore the final point has precisely the required lexicographic tie-breaking. Any residual tie is allowed.
There are at most
\(\displaystyle 2\sum_t|E_t|+|\mathcal A|=O(m^2)\)
variables: \(\sum_t|E_t|\leq m(m-1)/2\), and there are at most \(m^2\) opposite-side slot pairs.
We now verify the oracle hypotheses.
Edmonds’s description of \(P_t\) consists of nonnegativity, degree constraints, and odd-set constraints:
\(\displaystyle p_e\geq0,\qquad \sum_{e\ni s}p_e\leq1,\)
\(\displaystyle \sum_{e\in E_t[W]}p_e\leq\frac{|W|-1}{2}\quad\text{for every odd }W\subseteq S_t.\)
Scaling by \(q_{t,b}\) multiplies the right-hand sides by this input rational. Add the maximum-cardinality equality
\(\displaystyle \sum_{e\in E_t}z_{(t,b),e}=q_{t,b}k_t.\)
Every individual inequality has polynomial encoding length in \(m,\tau,L\), despite the potentially exponential number of odd-set inequalities. The remaining constraints of \(Q\) also have polynomial encoding length.
Moreover, \(Q\) is nonempty: choose any maximum internal matching in each cell and set every external mass to zero. It is bounded, since every coordinate is nonnegative and at most \(1\).
Linear optimization over \(P_t\) is maximum-weight matching in \(G_t\), hence polynomial-time computable. The rational optimization–separation equivalence gives a polynomial-time strong separation oracle for \(P_t\).
For a positive-mass cell, test \(z_c/q_c\) against this oracle and separately test its cardinality equality. If the oracle returns
\(\displaystyle a^\top p\leq\beta\)
violated by \(z_c/q_c\), then
\(\displaystyle a^\top z_c\leq q_c\beta\)
is a violated valid inequality for the scaled polytope. Division and scaling have polynomial bit complexity because \(q_c\) is an input rational. Zero-mass cells are checked directly.
Together with direct checks of external nonnegativity and slot capacities, these procedures give strong separation for \(Q\). The rational-polyhedral oracle theorem therefore solves its linear optimization problems exactly in polynomial time.
The sequentially optimized regions are faces of \(Q\). Each optimal objective value is attained at a vertex of the current face, hence at a vertex of \(Q\).
Vertex coordinates of \(Q\) have a uniform polynomial encoding bound: choose a full-rank collection of active defining constraints and apply Cramer’s rule, using the polynomial bounds on dimension and constraint encoding length. Evaluating any \(H\) or \(U_c\) at such a vertex likewise produces a rational of polynomial encoding length.
Thus the added equalities retain polynomial encoding lengths throughout all \(1+2\tau\) optimization stages.
Take a rational point \((z^\star,x^\star)\) in the final face.
For every positive-mass cell \(c=(t,b)\), apply the constructive decomposition theorem to
\(\displaystyle z_c^\star/q_{t,b}\in F_t.\)
The polytope \(F_t\) has the separation oracle and polynomial inequality-encoding bound established above. The theorem returns, in polynomial time,
\(\displaystyle z_c^\star/q_{t,b}=\sum_{j=1}^{r_c}\lambda_{c,j}\chi^{M_{c,j}},\qquad r_c\leq |E_t|+1.\)
All coefficients are rational with polynomial encoding length. Since \(F_t\) is a face of the matching polytope, its vertices are incidence vectors of actual maximum-cardinality matchings.
Output the positive submasses
\(\displaystyle y_{c,j}=q_{t,b}\lambda_{c,j}\)
with their matching labels, and the positive external masses \(x_a^\star\).
There are at most
\(\displaystyle 2\sum_t(|E_t|+1)=O(m^2+\tau)\)
internal submasses and \(O(m^2)\) external masses. Empty internal graphs cause no difficulty: their unique matching is the empty matching.
The output is feasible by Section 3 and satisfies every optimization criterion by Section 4. Both its encoding length and the time to compute it are polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated continuous problem, including exact lexicographic tie-breaking and recovery of the required rational representation. I found no major or minor mathematical issues.
The definition of \(F_t\) selects precisely the maximum-cardinality matching vectors and their convex combinations. The weighted-average argument correctly excludes positive weight on any matching of cardinality below \(k_t\).
Consequently, \(z_c\in q_{t,b}F_t\) correctly describes the internal edge marginals of a cell. Positive-mass cells are handled by normalization, and zero-mass cells are correctly forced to have zero internal marginals. Rational decomposition, needed for the specified output, is addressed constructively in Section 6.
The nonnegativity, degree, and odd-set inequalities stated in Section 5 are the correct description for a simple undirected graph. Including singleton odd sets merely adds trivial inequalities. Maximum-weight matching provides the required optimization oracle for arbitrary rational objectives. These facts agree with [Edmonds’s cited paper](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf).
The rational-polyhedral results invoked are applicable. GLS Theorem 6.4.9 gives the strong optimization–separation equivalence for well-described polyhedra, including lower-dimensional ones. Theorem 6.5.11 supplies constructive rational decomposition into affinely independent vertices; the separation-oracle formulation used by the prover follows through the preceding equivalence. Thus the stated bound by dimension plus one is justified. See [GLS, Chapter 6](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).
Every feasible mass matching yields the stated internal marginals and satisfies the slot-capacity inequalities. No constraint required by the task is omitted: external pairs are restricted to supplied compatibilities and opposite sides, and equal-type external pairs are included.
Conversely, the denominator construction establishes simultaneous realizability of every rational point in \(Q\). All copy counts are integers after multiplication by \(D\). For each slot class, the capacity inequality ensures that allocations among incident external pair classes can be disjoint. The bijections then consume every allocated endpoint exactly once.
Independence across distinct slot labels is legitimate under the task: a hospital can participate through multiple distinct slots, provided no individual slot is reused. Opposite-side endpoints necessarily belong to distinct hospitals, even for equal types. Therefore the construction respects the hospital-level restrictions.
The potentially large numerical value of \(D\) does not undermine polynomial runtime: the prover explicitly uses this construction only to establish existence, not as the algorithm that produces the output.
Each hospital unit of type \(t\) receives exactly \(k_t\) internal pairs. Hence the total internal matched-pair mass is the constant \(C=\sum_t k_t\mu_t\), regardless of the selected internal mixtures.
Maximizing \(\sum_{a\in\mathcal A}x_a\) therefore maximizes the specified total pair mass. Each external pair is counted once.
The formula \(U_c=2k_tq_{t,b}+\sum_{s\in S_t}X_{(t,b,s)}(x)\) correctly counts internal matched slots and external matched endpoints in that cell. It introduces neither omitted endpoints nor double counting within the cell utility.
Fixing the primary optimum and then fixing each successive cell-utility optimum leaves exactly the maximizers of all preceding criteria. Following the supplied order therefore implements the requested lexicographic tie-breaking. There are \(1+2\tau\) optimization stages, and the allowance of any remaining tie is respected.
The variable count is \(O(m^2)\): internal edges contribute at most \(2\sum_t|E_t|\), and external pairs contribute at most \(m^2\).
Scaling the matching inequalities and adding the cardinality equalities preserves polynomial encoding lengths. The exponential number of odd-set inequalities does not invalidate this bound, which concerns each individual inequality.
The separation procedure correctly handles positive-mass cells by normalization and rescales any separating inequality. Division by a small positive rational mass increases bit length only polynomially. Zero-mass cells and the remaining linear constraints are checked directly.
Nonemptiness and boundedness are correctly established. The Cramer’s-rule argument also justifies a uniform polynomial bound on vertex encodings, including lower-dimensional cases. Since each successive region is a face of \(Q\), its vertices are vertices of \(Q\); optimal utility values therefore have polynomial encoding length. The additional equalities do not cause uncontrolled growth.
Constructive decomposition applies to each normalized positive-mass internal vector. Every returned vertex of \(F_t\) represents an actual maximum-cardinality internal matching, so the labels satisfy the task rather than merely recording marginal coverage.
The bounds on the number of internal submasses and external pair masses are correct. Matching labels themselves also have polynomial size. Multiplying rational coefficients by input cell masses preserves polynomial encoding length.
Zero-mass cells require no positive submasses. Empty internal graphs have the unique empty matching, as stated. Empty external compatibility sets and cells without slots introduce no obstruction.
Required feedback: none. The argument establishes the claimed polynomial-time algorithm without relying on the finite-hospital result or an unproved extension of it.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.