Answer: The decision problem is \(\mathrm{NP}\)-complete already for \(m=3\). Minimization admits a deterministic polynomial-time \(2\)-approximation and is \(\mathrm{APX}\)-hard. Under the Unique Games Conjecture, no polynomial-time \((2-\varepsilon)\)-approximation exists for any fixed \(0<\varepsilon<1\) when \(m\) is unrestricted. Exact minimization is polynomial-time solvable for \(m\le2\).
Theorem 7.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf ∀k, c(fk) = 0 and each agent is only allowed to use one facility, then computing the optimum solution s∗is NP-Hard, but there exists a poly-time 2-approximation algorithm.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) facilities and \(\tau\) complete types with rational masses \(\mu_t\), connection costs \(a_{tk}\), and symmetric nonnegative pair costs \(d_{tu}\), choose fractions \(q_{tk}\ge 0\) for \(k=0,\ldots,m\), with \(\sum_{k=0}^{m}q_{tk}=1\), to minimize \(J(q)=\sum_t\mu_t\sum_{k=1}^{m}q_{tk}a_{tk}+\sum_{t,u}\mu_t\mu_u d_{tu}\left(1-\sum_{k=1}^{m}q_{tk}q_{uk}\right)\). Here \(q_{t0}\) is the unassigned fraction, the pair sum is ordered to count both agents' disconnection costs, and facility opening costs are zero. What are the exact and approximation complexities as functions of \(m\), \(\tau\), and the input bit length?
A society is given by its support: a list of \(\tau\ge1\) complete types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). The parameter \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) facilities. Input costs are binary rationals \(a_{tk}\ge0\) and \(d_{tu}=d_{ut}\ge0\); a complete type specifies its connection costs and its pair costs with every supported type. Diagonal costs \(d_{tt}\) describe interactions between distinct individuals of the same type and may be positive.
Choose real fractions \(q_{tk}\ge0\), for \(k=0,\ldots,m\), satisfying \(\sum_{k=0}^{m}q_{tk}=1\). Each individual uses at most one facility; \(q_{t0}\) is unassigned mass, with zero connection cost. Two unassigned individuals remain disconnected. Facility opening costs are zero, and no stability constraint is imposed.
Minimize \(J(q)=\sum_t\mu_t\sum_{k=1}^{m}q_{tk}a_{tk}+\sum_{t,u}\mu_t\mu_u d_{tu}\left(1-\sum_{k=1}^{m}q_{tk}q_{uk}\right)\). The pair sum includes all ordered type pairs, including \(t=u\), and counts both individuals' disconnection costs.
For the decision problem, a binary rational threshold \(B\ge0\) is also input. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\) and any approximation parameters.
Is deciding whether \(\min_q J(q)\le B\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
What polynomial-time multiplicative approximation guarantees and inapproximability bounds hold for minimizing \(J\)?
For finite agents using at most one facility and zero opening costs, exact social-cost minimization is \(\mathrm{NP}\)-hard and admits a polynomial-time \(2\)-approximation ([discrete result](https://cdn.aaai.org/ojs/16644/16644-13-20138-1-2-20210518.pdf)).
No published result settling this precise mass objective was located in the searches.
For the objective in the question:
The central fact is that fractional assignments never improve the optimum, including when diagonal costs are positive.
Call an assignment pure if, for each supported type \(t\), one coordinate of \((q_{t0},\ldots,q_{tm})\) equals \(1\).
Fix every assignment vector except that of type \(t\). Set
\(h_t=\mu_t^2d_{tt}\).
Using symmetry of the pair costs, the part of \(J\) depending on this vector is
\[ C+\sum_{k=1}^{m} \left(\mu_ta_{tk}-2\mu_t\sum_{u\ne t}\mu_ud_{tu}q_{uk}\right)q_{tk} -h_t\sum_{k=1}^{m}q_{tk}^{\,2}, \]
where \(C\) is independent of the vector being changed.
Since \(h_t\ge0\), this is a concave function on the simplex. Write \(e_k\) for its vertex corresponding to assignment \(k\), including \(k=0\). Concavity gives
\[ J(q)\ge \sum_{k=0}^{m}q_{tk}\, J(q_1,\ldots,q_{t-1},e_k,q_{t+1},\ldots,q_\tau). \]
The right side is a convex combination. Therefore some vertex replacement has objective at most \(J(q)\).
Apply this replacement successively to all \(\tau\) types. The resulting assignment is pure and has no larger objective. Furthermore, the feasible set is compact and \(J\) is continuous, so a minimum exists. Applying the replacements to a minimizer proves
\[ \min_qJ(q)=\min_{\text{pure }q}J(q). \]
This argument also gives a polynomial-time purification procedure for rational assignments: evaluate the \(m+1\) vertex replacements for each type and choose a cheapest one.
In particular, a pure assignment is a certificate for a yes-instance of the decision problem. It has \(\tau\) labels, and its rational objective can be evaluated and compared with \(B\) in polynomial bit complexity. Thus the decision problem belongs to \(\mathrm{NP}\).
Define
\[ c_{tk}=\mu_ta_{tk},\qquad h_t=\mu_t^2d_{tt},\qquad w_{tu}=2\mu_t\mu_ud_{tu}\quad(t<u). \]
For a pure assignment \(s_t\in\{0,1,\ldots,m\}\), its objective is
\[ J(s)= \sum_{t:s_t\ne0}c_{t,s_t} +\sum_{t:s_t=0}h_t +\sum_{t<u}w_{tu} \left(1-\mathbf 1_{\{s_t=s_u\ne0\}}\right). \]
The factor \(2\) in \(w_{tu}\) accounts for the two ordered off-diagonal pairs. The diagonal contribution is exactly \(h_t\) when type \(t\) is unassigned, and zero otherwise.
To represent unassignment correctly, introduce one private label \(p_t\) for each type. The label set consists of the \(m\) facility labels and these \(\tau\) private labels. Type \(t\) may use its own private label to represent being unassigned.
Give type \(t\) unary costs \(c_{tk}\) for facility labels and \(h_t\) for \(p_t\). Put edge weight \(w_{tu}\) between types \(t\) and \(u\), with edge cost zero for equal labels and \(w_{tu}\) for different labels.
Because different types have different private labels, two unassigned types pay their full disconnection cost, as required.
The private-label restrictions can be enforced with finite nonnegative costs. Let
\[ U=\sum_th_t+\sum_{t<u}w_{tu}, \qquad M=2U+1. \]
Here \(U\) is the cost of assigning every type to its own private label. Assign unary cost \(M\) when type \(t\) uses \(p_u\) with \(u\ne t\).
Every labeling violating a private-label restriction costs at least \(M>U\). Hence an optimal labeling satisfies the restrictions, and its optimum equals \(\min_qJ(q)\).
We use the following established theorem: uniform metric labeling with arbitrary nonnegative unary costs and edge weights admits a deterministic polynomial-time \(2\)-approximation. The deterministic version is obtained by derandomizing LP rounding. [Kleinberg–Tardos, Sections 3 and 5](https://www.cs.cornell.edu/home/kleinber/focs99-mrf.pdf).
All hypotheses hold for the instance constructed above: the label metric is the uniform metric, and every unary cost and edge weight is a finite nonnegative rational.
The algorithm returns a labeling of cost at most
\[ 2\,\mathrm{OPT}\le2U<M. \]
Consequently, it cannot violate a private-label restriction. Translating its labels back gives a pure feasible assignment satisfying
\[ J(s)\le2\min_qJ(q). \]
There are \(\tau\) vertices, \(m+\tau\) labels, and at most \(\binom{\tau}{2}\) edges. All transformed coefficients have polynomial bit length. Construction and approximation therefore take \((m+\tau+L)^{O(1)}\) time. No approximation parameter is required.
The guarantee includes the case \(\mathrm{OPT}=0\): the returned objective must then be zero.
Consider list uniform labeling. Its input is an undirected graph \(G=(V,E)\), nonnegative rational edge weights \(w_e\), a label set \(\{1,\ldots,m\}\), and a nonempty allowed-label list \(A_v\) for each vertex. Its objective is
\[ F(\ell)=\sum_{\{u,v\}\in E}w_{uv}\, \mathbf 1_{\{\ell_u\ne\ell_v\}}, \qquad \ell_v\in A_v. \]
Write \(n=|V|\), \(W=\sum_{e\in E}w_e\), and \(H=W+1\).
Construct a society with one supported type per vertex and masses \(\mu_v=1/n\). Set
\[ a_{vk}= \begin{cases} 0,&k\in A_v,\\ nH,&k\notin A_v, \end{cases} \qquad d_{vv}=n^2H, \]
and, for distinct vertices, set
\[ d_{uv}= \begin{cases} n^2w_{uv}/2,&\{u,v\}\in E,\\ 0,&\{u,v\}\notin E. \end{cases} \]
These coefficients satisfy every required sign and symmetry condition.
For a pure assignment:
Every valid list labeling therefore gives a pure assignment with exactly the same cost. Every pure assignment containing an unassigned type or a forbidden facility costs at least \(H\).
Conversely, choosing any allowed label for each vertex gives a valid labeling costing at most \(W<H\). Thus no optimal pure assignment is invalid. Section 1 now proves
\[ \min_qJ(q)=\min_\ell F(\ell). \]
There is also a polynomial-time solution conversion preserving approximation ratios. Purify any rational fractional solution first. If the resulting assignment is valid, retain it. Otherwise replace it by any valid list labeling. This replacement costs at most \(W\), whereas the invalid assignment costs at least \(H>W\). Hence the final list-labeling cost never exceeds the original mass-objective cost.
The construction uses \(O(nm+n^2)\) rational entries and polynomial bit length. Its diagonal costs exceed all off-diagonal costs, so the supported types are distinct.
If “binary rational” is intended to require dyadic rationals, first pad the graph with isolated vertices having unrestricted lists until \(n\) is a power of two. This preserves the optimum and allows equal dyadic masses. Integer-weight hardness instances then produce dyadic costs as well.
Three-terminal edge multiway cut is the special case with three labels: each terminal has its own singleton list, and every other vertex permits all three labels. Labelings and terminal-separating cuts have the same optimum: crossing edges separate the terminals; conversely, components remaining after a separating cut can be labeled according to their terminal, with terminal-free components labeled arbitrarily.
Three-terminal multiway cut is \(\mathrm{NP}\)-hard and \(\mathrm{MAX\ SNP}\)-hard. [Dahlhaus et al., *The Complexity of Multiterminal Cuts*](https://doi.org/10.1137/S0097539792225297); the approximation hardness is also recalled in [Bérczi et al., Section 1](https://karthik.ise.illinois.edu/pubs/multiway-cut-integrality-gap.pdf).
The reduction above preserves the optimum and converts solutions without increasing cost. It therefore proves:
A stronger established result applies to list uniform labeling:
Assuming the Unique Games Conjecture, for every fixed \(k\ge3\), approximation within \(2-2/k-\delta\) is hard for every fixed \(\delta>0\) for which this factor exceeds \(1\).
This follows from the fixed-metric hardness theorem and the uniform-metric integrality-gap bound in [Manokaran–Naor–Raghavendra–Schwartz, Theorem 1.3 and its accompanying table](https://people.eecs.berkeley.edu/~prasad/Files/mlpaper.pdf). Their restricted metric-labeling formulation uses allowed-label lists, exactly as required here.
Apply Section 3 with \(m=k\). It preserves both the optimum and approximation ratios, so the same conditional hardness holds for the mass objective.
For any fixed \(0<\varepsilon<1\), choose a fixed \(k>4/\varepsilon\) and set \(\delta=\varepsilon/2\). Then
\[ 2-\frac2k-\delta>2-\varepsilon. \]
A \((2-\varepsilon)\)-approximation would consequently contradict that conditional hardness. Thus the polynomial-time factor \(2\) is optimal for unrestricted \(m\), assuming the Unique Games Conjecture.
This does not establish factor-\(2\) hardness from \(\mathrm{P}\ne\mathrm{NP}\) alone.
The pure-optimum result also exposes a tractable boundary.
Encode the three possibilities by binary variables:
\[ s_t=1:\ (X_t,Y_t)=(0,0),\qquad s_t=0:\ (X_t,Y_t)=(1,0),\qquad s_t=2:\ (X_t,Y_t)=(1,1). \]
The allowed encodings are exactly those satisfying \(Y_t\le X_t\). Put \(z_t=X_t-Y_t\), which indicates unassignment.
For all nine ordered pairs of states, the disconnection indicator satisfies
\[ 1-\mathbf 1_{\{s_t=s_u\ne0\}} = \frac{|X_t-X_u|+|Y_t-Y_u|+z_t+z_u}{2}. \]
Indeed, equal facility states give zero; two unassigned states give one; and each pair of distinct states gives one.
Define
\[ b_t=h_t+\frac12\sum_{u\ne t}w_{tu}. \]
Substitution into the pure objective gives
\[ J= \sum_tc_{t1} +\sum_t(b_t-c_{t1})X_t +\sum_t(c_{t2}-b_t)Y_t +\frac12\sum_{t<u}w_{tu} \bigl(|X_t-X_u|+|Y_t-Y_u|\bigr). \]
This expression can be minimized by a single minimum cut:
A feasible encoding exists, so the last choice excludes every violating cut from optimality. The network has \(2\tau+2\) vertices and \(O(\tau^2)\) arcs, with polynomial-length rational capacities. Exact minimization takes \((\tau+L)^{O(1)}\) time.
Let \(X_t=1\) mean assigned and \(X_t=0\) mean unassigned. The corresponding identity is
\[ 1-X_tX_u = \frac{|X_t-X_u|+(1-X_t)+(1-X_u)}2. \]
Substitution again gives unary terms plus nonnegative absolute-difference terms, hence a minimum-cut formulation of polynomial size.
An exact algorithm also runs in
\[ 2^{O(\tau\log(\tau+1))}(m+\tau+L)^{O(1)}. \]
To prove this, enumerate the unassigned subset and a partition of the remaining types into nonempty facility groups. Different groups must receive different facilities.
For a fixed pattern, all diagonal and disconnection costs are determined. Assigning group \(G\) to facility \(k\) has connection cost
\[ \sum_{t\in G}\mu_ta_{tk}. \]
The cheapest injective assignment of groups to facilities is a polynomial-time minimum-cost bipartite matching problem. Patterns with more than \(m\) groups are infeasible.
The number of patterns is the Bell number \(\operatorname{Bell}(\tau+1)\): introduce one distinguished element whose block contains exactly the unassigned types. This number is at most \((\tau+1)^{\tau+1}\), proving the stated bound.
Thus every fixed support size permits polynomial-time exact minimization, while hardness occurs as \(\tau\) grows.
⟨structured verdict parsed — rendered above⟩
The output resolves the task in substance. Its reductions and algorithms are correct, and the cited approximation theorems support the claims made. I found one minor notation gap, no false central step, and no missing substantive argument.
1. Existence of a pure optimum and membership in NP
The expression obtained by fixing every type except \(t\) is correct:
Because \(d_{tt}\ge0\), this expression is concave on the entire assignment simplex. The displayed concavity inequality has the correct direction. Its convex-combination argument guarantees a vertex replacement with no larger cost.
Successive replacements preserve previously purified coordinates. Thus, after \(\tau\) replacements, the assignment is pure and its objective has not increased. Compactness and continuity justify applying this procedure to an actual minimizer. This establishes equality of the continuous and pure optima, including positive diagonal costs.
The rational purification procedure is valid and polynomial in the combined bit length of the instance and the rational assignment supplied to it. A pure assignment provides a polynomial-size certificate, and exact rational evaluation has polynomial bit complexity. The NP-membership conclusion is justified.
2. Conversion to uniform metric labeling
The pure-assignment formula correctly accounts for every term:
Private labels correctly represent unassignment. In particular, distinct unassigned types receive different labels and consequently pay the required edge cost.
The penalty argument is sound. Assigning every type its own private label costs \(U\). All labeling costs are nonnegative, so any forbidden private-label use costs at least \(M>U\). Hence an optimal labeling respects the restrictions.
The stronger inequality \(M>2U\) also ensures that the approximation algorithm respects those restrictions. This remains valid when \(U=0\).
3. Deterministic multiplicative approximation
The cited theorem is applicable. Kleinberg–Tardos establish a factor-\(2\) approximation for uniform metric labeling and provide deterministic rounding in Section 5.1, specifically Theorem 5.2. The construction supplies a uniform label metric, nonnegative unary costs, and nonnegative edge weights, as required. [Kleinberg–Tardos](https://www.cs.cornell.edu/home/kleinber/focs99-mrf.pdf)
The returned labeling has cost at most \(2\,\mathrm{OPT}\le2U<M\), so translating it back preserves both feasibility and objective value. Therefore the claimed multiplicative factor is correct.
The construction has polynomially many vertices, labels, edges, and rational coefficient bits. The stated running time \((m+\tau+L)^{O(1)}\) is justified. The zero-optimum case is handled correctly: the guarantee forces a zero-cost output.
4. Reduction from list uniform labeling
The reduction’s scaling is correct:
Every valid list labeling has exactly its original objective value. Every invalid pure assignment costs at least \(H\), while some valid labeling costs at most \(W<H\). Together with purification, these observations establish equality of the optima.
The solution conversion also preserves approximation guarantees. Purification cannot increase cost. If its output is invalid, replacing it by any valid list labeling decreases cost, since that labeling costs at most \(W<H\).
The construction’s size and bit complexity are polynomial. The distinct-type assertion is justified: diagonal entries are strictly larger than off-diagonal entries, so different types have different pair-cost rows.
The optional padding argument correctly addresses dyadic masses for integer-weight hardness instances. Under the usual interpretation of binary-encoded rationals, padding is unnecessary.
5. NP-completeness and unconditional approximation hardness
The identification of three-terminal multiway cut with the stated list-labeling special case is correct. Crossing edges of a labeling separate the terminals. Conversely, a separating cut yields components containing at most one terminal; assigning component labels as described gives a labeling whose crossing cost is no greater than the cut cost. These directions establish equality of the optimal values.
The cited hardness applies to a fixed number of terminals, including three. Dahlhaus et al. establish NP-hardness for three terminals; the cited Bérczi et al. introduction explicitly recalls APX-hardness for every fixed number of terminals at least three. [Dahlhaus et al.](https://doi.org/10.1137/S0097539792225297), [Bérczi et al.](https://karthik.ise.illinois.edu/pubs/multiway-cut-integrality-gap.pdf)
Because the society reduction preserves optimal values, the decision reduction uses the original threshold unchanged. Its polynomial-size pure certificates establish NP-completeness.
The approximation-preserving solution conversion supports the APX-hardness conclusion and the consequent constant-factor gap above \(1\). The claimed exclusion of a PTAS unless \(\mathrm{P}=\mathrm{NP}\) is justified.
6. Conditional hardness approaching factor \(2\)
The cited result applies to the correct labeling problem. Manokaran–Naor–Raghavendra–Schwartz define restricted metric labeling using allowed-label lists in Definition 3.1. Their Theorem 1.3 transfers fixed-metric earthmover integrality gaps to UGC-based hardness, and the accompanying table gives the uniform-metric bound \(2-2/k\). Thus the prover is using list labeling, rather than incorrectly importing the same bound from terminal-only multiway cut. [Manokaran et al.](https://people.eecs.berkeley.edu/~prasad/Files/mlpaper.pdf)
The reduction therefore transfers hardness at every fixed factor \(2-2/k-\delta>1\).
The final parameter calculation is correct. Choosing \(k>4/\varepsilon\) and \(\delta=\varepsilon/2\) gives
\(2-2/k-\delta>2-\varepsilon>1\).
An algorithm with the smaller approximation factor would contradict the cited conditional hardness.
The output correctly keeps this conclusion conditional on UGC and does not assert unconditional hardness approaching \(2\).
7. Exact algorithms for one or two facilities
For two facilities, the three encodings and the constraint \(Y_t\le X_t\) are correct. Checking the state pairs confirms the disconnection identity, including the easily mishandled case of two unassigned types.
The resulting unary coefficients and absolute-difference coefficients are correct. Negative unary coefficients are represented with the stated constant adjustment. With value \(1\) on the source side, an arc from \(Y_t\) to \(X_t\) penalizes precisely the forbidden encoding.
A capacity greater than the sum of all other capacities excludes violating cuts: a feasible cut exists with ordinary cut capacity no greater than that sum. The stated network size and polynomial bit complexity are correct.
For one facility, the displayed binary identity is also correct. The diagonal contribution is a unary term, so the claimed minimum-cut formulation follows by routine substitution.
Minor issue: Section 2 defines \(w_{tu}\) only for \(t<u\), but Section 5 uses \(\sum_{u\ne t}w_{tu}\). As written, some summands are undefined. The intended symmetric convention is immediate, and the calculation is sound under it.
Minimum clarification needed: State that \(w_{ut}=w_{tu}\) whenever \(t<u\). No additional mathematics is needed.
8. Exact running time for small support
The enumeration correctly distinguishes unassigned types from facility groups. Requiring different groups to use different facilities matches the meaning of those groups.
For each fixed pattern, diagonal and pair costs are determined independently of facility identities. The connection costs are exactly those supplied to the minimum-cost matching problem. Rejecting patterns with more than \(m\) groups handles feasibility.
The correspondence with partitions of \(\tau+1\) elements is valid, including the cases where every type is assigned or every type is unassigned. The Bell-number bound implies the claimed running time
\(2^{O(\tau\log(\tau+1))}(m+\tau+L)^{O(1)}\).
The unresolved sharp approximation threshold under only \(\mathrm{P}\ne\mathrm{NP}\) is explicitly acknowledged. It does not undermine the results actually claimed.
⟨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.