d4-conf-atal-2016-0243 (d4-conf-atal-2016-0243)

Given a finite set of source and receiver types \(T\), rational masses \(\mu_t\) summing to \(1\), rational type-interaction coefficients \(K_{t,s}\), a global quota \(p\), local caps \(p_s\), and linear benefit and damage rates \(b_t,d_s\), choose open mass \(y_t\in[0,\mu_t]\) to maximize \(R(y)=\sum_t b_t y_t-\sum_s\mu_s d_s E_s(y)\), where \(E_s(y)=\sum_t K_{t,s}y_t\), subject to \(\sum_t y_t\le p\) and \(E_s(y)\le p_s\) for every \(s\).

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type is both a source and a receiver. The rational interaction matrix satisfies \(K_{t,t}=1\) and \(0\le K_{t,s}\le1\) for distinct types. The digraph with arcs \((t,s)\) whenever \(t\ne s\) and \(K_{t,s}>0\) has a planar underlying undirected graph; let \(m\) be its number of arcs.
The input also contains nonnegative rational benefit and damage rates \(b_t,d_t\), a rational global quota \(p\in[0,1]\), and nonnegative rational local caps \(p_s\). Let \(L\) be the total binary input length.
Choose divisible open masses \(y_t\in[0,\mu_t]\). Define \(E_s(y)=\sum_{t\in T}K_{t,s}y_t\) and maximize \(R(y)=\sum_{t\in T}b_ty_t-\sum_{s\in T}\mu_sd_sE_s(y)\), subject to \(\sum_{t\in T}y_t\le p\) and \(E_s(y)\le p_s\) for every \(s\in T\).
Does this continuous optimization problem admit an EPTAS with running time \(f(1/\varepsilon)\operatorname{poly}(m,\tau,L)\), or can such a scheme be excluded assuming \(\mathrm{FPT}\ne\mathrm{W}[1]\)?
For discrete pollution optimization with binary opening decisions and linear benefit and damage functions, no EPTAS exists on directed planar graphs, assuming \(\mathrm{FPT}\ne\mathrm{W}[1]\), even without a global quota. [Discrete result](https://link.springer.com/article/10.1007/s00453-018-0435-4).
The underlying two-dimensional knapsack lower bound has the same assumption. [Knapsack result](https://csaws.cs.technion.ac.il/~hadas/PUB/multi_knap.pdf). No result for this precise mass formulation was identified in these sources.

1. Result

The stated continuous problem is exactly solvable in polynomial time, and consequently admits an EPTAS unconditionally. The proof applies to arbitrary interaction graphs; planarity is unnecessary.

Here “divisible” means that each \(y_t\) may take any real value in \([0,\mu_t]\), as stipulated in the task.

2. Exact linear-programming formulation

For each \(t\in T\), define the rational coefficient

\[ c_t=b_t-\sum_{s\in T}\mu_s d_s K_{t,s}. \]

Interchanging two finite sums gives

\[ R(y)=\sum_{t\in T}b_ty_t-\sum_{s\in T}\sum_{t\in T}\mu_s d_sK_{t,s}y_t =\sum_{t\in T}c_ty_t. \]

Thus the problem is precisely the rational linear program with objective \(\max\sum_{t\in T}c_ty_t\) and inequalities

\[ -y_t\le0,\qquad y_t\le\mu_t\quad(t\in T), \]

\[ \sum_{t\in T}y_t\le p, \qquad \sum_{t\in T}K_{t,s}y_t\le p_s\quad(s\in T). \]

There are \(\tau\) variables and \(3\tau+1\) inequalities. This reformulation preserves every feasible solution and its objective value.

The feasible set is nonempty because \(y=0\) satisfies all constraints: the global quota and all local caps are nonnegative. It is closed, being an intersection of finitely many closed half-spaces, and bounded, being contained in \(\prod_{t\in T}[0,\mu_t]\). Therefore it is compact. The linear objective is continuous, so its maximum is finite and attained. Moreover, writing this maximum as \(\mathrm{OPT}\), we have \(\mathrm{OPT}\ge R(0)=0\), even if some coefficients \(c_t\) are negative.

3. Polynomial bit complexity

The relevant standard theorem is exact polynomial-time solvability of rational linear programming: given an explicitly encoded rational linear program with a nonempty feasible set and finite attained optimum, an exact rational optimal solution can be computed in time polynomial in its binary encoding length. This is polynomial time in the Turing model, including dependence on coefficient bit lengths. See Khachiyan’s [polynomial algorithms](https://www.mathnet.ru/eng/zvmmf5239) and [exact-solution result](https://www.mathnet.ru/eng/zvmmf5684).

We verify that constructing our linear program causes only polynomial growth in encoding length.

Every input rational has numerator and denominator bit lengths bounded by \(L\). A product \(\mu_s d_s K_{t,s}\) therefore has bit length \(O(L)\). Each \(c_t\) combines at most \(\tau+1\) rational terms. Using the product of their positive denominators as a common denominator gives denominator bit length \(O((\tau+1)L)\); the resulting numerator has bit length \(O((\tau+1)L+\log(\tau+1))\). Consequently, all coefficients \(c_t\) can be computed exactly in polynomial time and have polynomial encoding length.

The constraint coefficients are input entries of \(K\), input bounds, or constants. Even writing the constraint matrix densely produces only \(O(\tau^2)\) entries, so its encoding length is polynomial in \(\tau\) and \(L\). In a sparse representation, the constraint matrix has \(m+4\tau\) nonzero entries.

All hypotheses of the rational linear-programming theorem are therefore satisfied. It returns an exact feasible optimizer \(y^\star\) in time \(\operatorname{poly}(m,\tau,L)\). In particular, this is a bit-complexity bound, with no expansion of the masses into individual agents.

For every \(0<\varepsilon<1\), run this same exact algorithm. Since \(\mathrm{OPT}\ge0\),

\[ R(y^\star)=\mathrm{OPT}\ge(1-\varepsilon)\mathrm{OPT}. \]

The runtime is independent of \(\varepsilon\), hence has the required form \(f(1/\varepsilon)\operatorname{poly}(m,\tau,L)\), with \(f\equiv1\).

4. Why the discrete lower bounds do not transfer

The cited pollution lower bound concerns binary decisions, and its proof encodes two-dimensional knapsack using those decisions. ([Pollution paper, Theorem 4](https://link.springer.com/article/10.1007/s00453-018-0435-4).) The cited knapsack problem likewise selects a subset of items. ([Kulik–Shachnai](https://csaws.cs.technion.ac.il/~hadas/PUB/multi_knap.pdf).) Divisible variables change this essential restriction.

Indeed, fractional and endpoint-restricted optima can differ even on a planar instance with a redundant global quota. Take \(T=\{1,2\}\), masses \(\mu_1=\mu_2=1/2\), all entries of \(K\) equal to \(1\), benefits \(b_1=b_2=1\), damages \(d_1=d_2=0\), quota \(p=1\), and caps \(p_1=p_2=3/4\). The underlying graph is one edge. Both local constraints say \(y_1+y_2\le3/4\), and the objective is \(y_1+y_2\).

The divisible optimum is \(3/4\), attained at \((1/2,1/4)\). If each type must instead be entirely closed or open, so \(y_t\in\{0,\mu_t\}\), opening both violates the caps and the optimum is \(1/2\).

Thus the discrete hardness results are compatible with the unconditional exact polynomial-time algorithm proved here.

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly: the continuous problem is exactly solvable in polynomial time and therefore admits an EPTAS unconditionally. No mathematical gaps or false statements were found.

• Objective reformulation. Substituting the definition of \(E_s(y)\) and interchanging finite sums gives the stated coefficient

\(c_t=b_t-\sum_{s\in T}\mu_s d_sK_{t,s}\).
The indices are consistent: \(t\) denotes the source and \(s\) the receiver. The objective is linear, and every coefficient is rational.

• Constraints and equivalence. The LP reproduces every original constraint without introducing an integrality restriction or dropping a condition. It has \(\tau\) variables and \(3\tau+1\) inequalities: two bounds per variable, one global quota, and one cap per receiver. Feasible solutions and objective values are preserved exactly.

• Feasibility and attainment. The nonnegativity of \(p\) and all \(p_s\) makes \(y=0\) feasible. The feasible region is closed and contained in the bounded box \(\prod_{t\in T}[0,\mu_t]\), so it is compact. The continuous linear objective therefore attains a finite maximum. The conclusion \(\mathrm{OPT}\ge0\) follows from the feasible zero solution, including when some \(c_t\) are negative.

• Coefficient bit lengths. The bounds are valid. Multiplying three input rationals produces numerator and denominator bit lengths \(O(L)\). Combining at most \(\tau+1\) such terms using a product denominator yields denominator bit length \(O((\tau+1)L)\); summation adds at most \(O(\log(\tau+1))\) bits to the numerator bound. These are bounds on binary encoding lengths, so exponentially large numerical denominators do not invalidate the polynomial-time claim. Computing all coefficients uses polynomially many arithmetic operations on numbers of polynomial bit length.

• Constraint encoding. A dense matrix has \(O(\tau^2)\) entries of polynomial bit length. The sparse count \(m+4\tau\) is also correct: the local constraints contribute \(m+\tau\) entries, the variable bounds contribute \(2\tau\), and the global quota contributes \(\tau\). This count concerns the constraint matrix, excluding right-hand sides and the objective.

• Exact LP theorem. The prover states the required theorem precisely enough: an explicitly encoded rational LP with a nonempty feasible region and finite attained optimum admits an exact rational optimizer in polynomial time in its binary encoding length. All its hypotheses have been verified. The cited [Khachiyan exact-solution paper](https://www.mathnet.ru/eng/zvmmf5684) supports exact optimization with polynomial arithmetic and bit bounds. The application requires neither a strictly feasible point nor positive objective coefficients, so zero quotas, zero caps, and lower-dimensional feasible regions cause no gap.

• EPTAS conclusion. For every \(0<\varepsilon<1\), exact optimality and \(\mathrm{OPT}\ge0\) give

\(R(y^\star)=\mathrm{OPT}\ge(1-\varepsilon)\mathrm{OPT}\).
This also covers \(\mathrm{OPT}=0\). The algorithm can ignore \(\varepsilon\), giving the requested runtime with \(f\equiv1\). Planarity is unused throughout, so the claim for arbitrary interaction graphs is justified.

• Discrete lower bounds and example. The description of the cited discrete results is accurate: [pollution Theorem 4](https://link.springer.com/article/10.1007/s00453-018-0435-4) uses binary decisions and a two-dimensional knapsack reduction; the [knapsack paper](https://csaws.cs.technion.ac.il/~hadas/PUB/multi_knap.pdf) selects subsets of items. The example satisfies all task assumptions. Its divisible optimum is \(3/4\), whereas its endpoint-restricted feasible objective values are \(0\) and \(1/2\), since opening both types violates both caps. The example correctly illustrates the distinction; the polynomial-time conclusion rests on the LP argument.

Actionable feedback: No additional lemma, clarification, or repair is needed.

⟨structured verdict parsed — rendered above⟩