Answer: \(\mathrm{NP}\)-hard, even with \(\tau=3\), \(C=1\), \(R=0\), and constant edge traversal times.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere is no PTIME algorithm that can approx- imate Prob. 2 within any constant factor c, where 0 < c ≤1, unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a directed road network, a horizon, worker types with masses μ_d, and order types with per-worker demands ν_q, find a feasible allocation minimizing the range of time-normalized worker incomes. Each feasible schedule π assigns whole orders, respects routing, timing, and capacity constraints, and serves k_q(π) orders of type q. Choose schedule masses z_{d,π}≥0 such that Σ_π z_{d,π}=μ_d for each worker type and Σ_{d,π} z_{d,π}k_q(π)=ν_q for each order type; minimize ess sup_{z_{d,π}>0} I(d,π) minus ess inf_{z_{d,π}>0} I(d,π), where I(d,π) is the schedule’s driving and waiting income divided by available time.
A society is given by its support: the list of the \(\tau\) worker types with positive masses \(\mu_d\), each a binary rational, with \(\sum_d\mu_d=1\); \(\tau\) is the support size, not the number of possible types.
Input comprises a directed network \(G=(V,E)\), horizon \(T>0\), common capacity \(C\in\mathbb N_{>0}\), and payment rates \(w_1>w_2\ge0\). Edge traversal times are positive, explicitly represented piecewise-constant functions with rational breakpoints and values, evaluated when entering an edge.
Worker type \(d\) specifies an initial node and an availability interval \([s_d,e_d]\subseteq[0,T]\) of length \(a_d=e_d-s_d>0\). Each of the \(m\) order types specifies a restaurant, customer, release time \(r_q\ge0\), preparation duration \(p_q\ge0\), and positive binary-rational demand \(\nu_q\) per unit worker mass; demands need not sum to one.
A schedule \(\pi\) for type \(d\) assigns finitely many whole order copies after their release, completes them within the availability interval, and never has more than \(C\) assigned but undelivered copies. Each copy is picked up no earlier than \(r_q+p_q\) and is delivered after pickup.
After each assignment, the worker follows a route minimizing total driving time through the pending pickup and delivery visits, respecting pickup precedence and already completed visits, with quickest paths between visits; any minimizing route is permitted. Travel and restaurant waiting proceed as soon as possible; idle workers stay put, and gratuitous travel or waiting is forbidden. No additional proximity bound or delivery deadline is imposed.
Let \(k_q(\pi)\) count delivered copies and let \(D(d,\pi)\) and \(W(d,\pi)\) be total driving and restaurant waiting times. Set \(I(d,\pi)=(w_1D(d,\pi)+w_2W(d,\pi))/a_d\); an empty schedule has income zero.
An allocation consists of nonnegative real schedule masses satisfying \(\sum_\pi z_{d,\pi}=\mu_d\) and \(\sum_{d,\pi}z_{d,\pi}k_q(\pi)=\nu_q\). Its gap is \(\operatorname*{ess\,sup}_{z_{d,\pi}>0}I(d,\pi)-\operatorname*{ess\,inf}_{z_{d,\pi}>0}I(d,\pi)\), so fairness concerns individual schedules rather than type-average incomes. Schedules are implicit, not supplied as an enumerated list.
Is deciding whether such an allocation has gap at most a given binary-rational \(R\ge0\) solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), total input bit length \(L\), network size, and \(C\).
The discrete income-gap minimization problem is NP-hard and admits no polynomial-time finite constant-factor multiplicative approximation unless \(\mathrm P=\mathrm{NP}\). [Source](https://arxiv.org/abs/2203.08849)
A related max-min food-delivery problem has a fractional-server offline MILP formulation, but uses a different objective and fractional routing model; it does not settle this schedule-mass problem. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/29969/31697)
The decision problem is \(\mathrm{NP}\)-hard, even when \(\tau=3\), \(C=1\), \(R=0\), \(w_1=1\), \(w_2=0\), and all edge traversal times are constant. The reduction uses dyadic masses and demands.
Consequently, unless \(\mathrm P=\mathrm{NP}\), there is no algorithm whose running time is polynomial in \(m,\tau,L,|V|,|E|,C\). Hardness persists with the support size and capacity fixed.
The proof below directly addresses fractional masses of whole schedules.
We use the standard \(\mathrm{NP}\)-complete problem Exact Cover by 3-Sets. Its input consists of a universe \(U=\{0,\ldots,3k-1\}\), where \(k\ge1\), and a list \(S_1,\ldots,S_M\) of three-element subsets, where \(M\ge1\). The question is whether some subcollection covers every element exactly once.
Define
\[ b=k+1,\qquad H=\sum_{j=0}^{3k-1}b^j,\qquad A=(k+1)H+1. \]
For each set define
\[ h_i=\sum_{j\in S_i}b^j,\qquad t_i=A+h_i, \]
and let \(B=kA+H\).
Encoding lemma. There exist nonnegative integers \(x_1,\ldots,x_M\) satisfying \(\sum_i x_i t_i=B\) if and only if the exact-cover instance is a yes-instance. Every such solution satisfies \(\sum_i x_i=k\) and selects an exact cover.
Proof. Suppose \(\sum_i x_i t_i=B\), and put \(n=\sum_i x_i\).
Since every \(t_i\ge A\) and \(H<A\), we have
\[ nA\le B=kA+H<(k+1)A, \]
so \(n\le k\). On the other hand, if \(n\le k-1\), then \(h_i\le H\) gives
\[ \sum_i x_i t_i \le(k-1)(A+H) <kA <B. \]
The strict middle inequality follows from \((k-1)H<A\). Thus \(n=k\), and subtracting \(kA\) yields
\[ \sum_i x_i h_i=H. \]
For each \(j\in U\), let \(c_j=\sum_{i:j\in S_i}x_i\). The last equality becomes
\[ \sum_{j=0}^{3k-1}c_j b^j = \sum_{j=0}^{3k-1}b^j. \]
Each \(c_j\) is an integer satisfying \(0\le c_j\le n=k<b\). Therefore both sides are base-\(b\) representations without carries. Uniqueness of that representation gives \(c_j=1\) for every \(j\).
In particular, no \(x_i\) can exceed one: otherwise every element of \(S_i\) would have multiplicity at least two. The selected sets consequently form an exact cover.
Conversely, an exact cover consists of \(k\) sets, whose corresponding \(h_i\) sum to \(H\). Their \(t_i\) therefore sum to \(B\). \(\square\)
This lemma explicitly allows repeated copies before proving that a target-sum solution cannot repeat a set.
Let \(K=\max_i t_i\). Construct nodes consisting of a hub \(v\), restaurant nodes \(\ell_1,\ldots,\ell_M\), an auxiliary starting node \(u\), and two anchor nodes \(x,y\).
The only edges, with constant traversal times, are:
| Edge | Traversal time |
|---|---:|
| \(v\to\ell_i\) | \(t_i/2\) |
| \(\ell_i\to v\) | \(t_i/2\) |
| \(u\to\ell_i\) | \(K-t_i/2\) |
| \(x\to y\) | \(1\) |
All traversal times are positive, since \(K-t_i/2\ge t_i/2>0\). There are no edges between the anchor component and the other nodes, and no edges entering \(u\).
For each \(i\), order type \(q_i\) has restaurant \(\ell_i\) and customer \(v\). There is also an anchor order \(q_\ast\), with restaurant \(x\) and customer \(y\). Every order has release time and preparation duration zero.
Set \(C=1\), \(w_1=1\), \(w_2=0\), and \(R=0\).
The following route properties will be used:
These routes satisfy the prescribed minimization rule. For example, the direct path from \(u\) to \(\ell_i\) takes \(K-t_i/2\). Any alternative must first reach \(v\) through some restaurant, taking \(K\), and then reach \(\ell_i\), taking another \(t_i/2\); positive cycles only increase its duration. The direct path is therefore uniquely quickest. The analogous hub-to-restaurant and delivery paths are also uniquely quickest.
Set the horizon to \(T=1+B\). There are exactly three worker types:
| Type | Initial node | Availability interval |
|---|---|---|
| Main | \(v\) | \([1,1+B]\) |
| Auxiliary | \(u\) | \([1,1+K]\) |
| Anchor | \(x\) | \([1,2]\) |
All intervals lie within the horizon because \(t_i\le A+H\le B\), hence \(K\le B\).
Define dyadic numbers
\[ \eta=2^{-\lceil\log_2(2M)\rceil}, \qquad \varepsilon=2^{-\lceil\log_2(8Mk)\rceil}. \]
Assign worker masses
\[ \mu_{\mathrm{main}}=\varepsilon,\qquad \mu_{\mathrm{aux}}=\beta=M\eta-\varepsilon k,\qquad \mu_{\mathrm{anchor}}=\gamma=1-\varepsilon-\beta. \]
These masses are positive and sum to one. Indeed,
\[ \frac1{4M}<\eta\le\frac1{2M}, \qquad 0<\varepsilon k\le\frac1{8M}. \]
Consequently, \(\beta>1/8\), while
\[ \gamma=1-M\eta+\varepsilon(k-1)\ge\frac12. \]
Set the demands to
\[ \nu_i=\eta\quad\text{for every }q_i, \qquad \nu_\ast=\gamma. \]
All masses and demands are positive dyadic rationals.
For a main worker, capacity one prevents assignment of a second copy before the current copy is delivered. Each delivery returns the worker to \(v\). Since gratuitous travel is forbidden, every completed schedule \(\pi\) therefore satisfies
\[ D(\mathrm{main},\pi)=\sum_{i=1}^M t_i k_i(\pi), \qquad W(\mathrm{main},\pi)=0. \]
Any idle time before assignments does not change this identity. Its income is consequently
\[ I(\mathrm{main},\pi) =\frac{\sum_i t_i k_i(\pi)}B. \]
An auxiliary worker can deliver at most one copy. Its first delivery takes the entire availability length \(K\), and no anchor order is reachable. Each nonempty auxiliary schedule has income \(K/K=1\).
An anchor worker can deliver at most one anchor copy, cannot reach any other order, and has income one when it delivers that copy. Neither of the other worker types can reach the anchor order.
All schedules used below assign immediately when capacity becomes available, travel along the quickest paths, and incur no waiting.
Suppose \(x_i\in\{0,1\}\) select an exact cover. The encoding lemma gives
\[ \sum_i x_i=k, \qquad \sum_i x_i t_i=B. \]
Assign the entire main-worker mass \(\varepsilon\) to a schedule serving these \(k\) orders successively. It starts at time one, finishes at \(1+B\), and has income one.
For each \(i\), assign auxiliary mass
\[ z_i=\eta-\varepsilon x_i \]
to the singleton schedule delivering \(q_i\). These masses are positive because \(\varepsilon x_i\le\varepsilon k<\eta\). Moreover,
\[ \sum_i z_i =M\eta-\varepsilon\sum_i x_i =M\eta-\varepsilon k =\beta. \]
Thus all auxiliary-worker mass is allocated. Demand for every \(q_i\) is met exactly:
\[ \varepsilon x_i+z_i=\eta=\nu_i. \]
Assign all anchor mass \(\gamma\) to its singleton delivery schedule, meeting demand \(\nu_\ast=\gamma\).
Every positively weighted schedule has income one. The allocation therefore has gap zero.
Conversely, suppose an allocation with gap at most \(R=0\) exists.
Only anchor workers can deliver \(q_\ast\), and each can deliver at most one copy. Their total mass and the required anchor demand are both \(\gamma\). The demand equality therefore forces all anchor mass to use schedules delivering one copy: assigning positive mass to an empty anchor schedule would strictly reduce delivered anchor demand below \(\gamma\).
Hence a positive mass of schedules has income one. Gap zero forces every positively weighted schedule to have income one.
The main-worker mass is \(\varepsilon>0\), so at least one main schedule \(\pi\) receives positive mass. For that schedule,
\[ 1=I(\mathrm{main},\pi) =\frac{\sum_i t_i k_i(\pi)}B, \]
and therefore
\[ \sum_i t_i k_i(\pi)=B. \]
The counts \(k_i(\pi)\) are nonnegative integers because each schedule serves whole order copies. The encoding lemma now supplies an exact cover.
Thus the constructed society admits a zero-gap allocation if and only if the original exact-cover instance is a yes-instance. \(\square\)
The construction has
\[ m=M+1,\qquad \tau=3,\qquad |V|=M+4,\qquad |E|=3M+1,\qquad C=1. \]
Every edge function has a single constant piece. The integers \(H,A,t_i,B\) have \(O(k\log(k+1))\) bits. The masses and demands require \(O(\log(Mk))\) bits each. Consequently, the total constructed input length satisfies
\[ L=O\!\left(Mk\log(k+1)+M\log(Mk)\right). \]
The numbers and network can be constructed in polynomial bit time in the explicitly represented exact-cover input.
Therefore an algorithm running in \(\operatorname{poly}(m,\tau,L,|V|,|E|,C)\) would solve Exact Cover by 3-Sets in polynomial time. More generally, a running time \(f(\tau,C)\operatorname{poly}(m,L,|V|,|E|)\), for any fixed finite function \(f\), would have the same consequence because the reduction fixes \(\tau=3\) and \(C=1\).
This proves the requested hardness alternative without requiring a complexity-class membership claim for the unrestricted time-dependent model.
[FairFoody](https://arxiv.org/abs/2203.08849) establishes hardness for its discrete fairness problem. The argument above separately proves hardness for the specified schedule-mass model. The [fractional-server formulation](https://ojs.aaai.org/index.php/AAAI/article/download/29969/31697) uses a max-min objective and permits fractional server routing; it does not replace whole-schedule income constraints with an equivalent polynomial formulation.
⟨structured verdict parsed — rendered above⟩
The reduction is correct and resolves the requested hardness alternative. I found no major or minor issues requiring repair. It establishes \(\mathrm{NP}\)-hardness for fractional masses of whole schedules, with support size and capacity fixed.
The encoding lemma is valid in both directions.
The boundary case \(k=1\) causes no failure. The argument explicitly handles integer multiplicities rather than assuming that schedules cannot repeat order types.
The constructed instance satisfies the task’s input restrictions.
All edge times are positive rational constants. In particular, \(K-t_i/2\ge t_i/2>0\). Constant edge functions are permitted instances of the specified piecewise-constant representation.
The directed network has the claimed node and edge counts. Its disconnected anchor component and absence of edges entering \(u\) are permitted; the task imposes no connectivity requirement.
The availability intervals have positive lengths and lie inside the horizon. The inequality \(t_i\le A+H\le B\) holds for every \(k\ge1\), including equality in the second inequality when \(k=1\).
Release and preparation times are zero, while the constructed schedules assign at time one or later. Pickup and delivery timing therefore satisfy the stated restrictions.
The claimed shortest-path properties are correct.
For an auxiliary worker, a route from \(u\) through any restaurant to \(v\) costs exactly \(K\). Reaching the target restaurant afterward adds \(t_i/2\), so such an alternative is strictly slower than the direct edge from \(u\). Positive cycles cannot improve this comparison. The hub-to-restaurant and restaurant-to-hub paths likewise have the claimed minimum durations.
With \(C=1\), the main worker must complete a delivery before assigning the next copy. Each delivery ends at \(v\), and the prohibition on gratuitous travel excludes additional driving. Therefore the displayed identity for driving time, and hence the displayed income formula, are valid.
The auxiliary worker’s first completed order consumes its entire availability length. The anchor worker can deliver one anchor copy and cannot return to its restaurant. Neither can complete additional copies. The reachability assertions separating the anchor order from the other worker types are also correct.
There is no restaurant waiting because all orders are prepared before any constructed pickup.
The dyadic bounds and positivity checks are correct:
\(\eta>1/(4M)\), \(\eta\le1/(2M)\), and \(0<\varepsilon k\le1/(8M)\).
These imply \(\beta>1/8\). The identity \(\gamma=1-M\eta+\varepsilon(k-1)\) implies \(\gamma\ge1/2\). Together with their defining equations, these establish that all three worker masses are positive and sum to one.
Every demand is positive and dyadic. The construction does not assume that demands sum to one, consistent with the task.
Given an exact cover, the main schedule is feasible: its successive trips take total time \(B\), and it finishes exactly at its availability endpoint.
Each auxiliary schedule takes exactly \(K\). Its assigned mass \(z_i=\eta-\varepsilon x_i\) is positive because \(\varepsilon x_i\le\varepsilon k<\eta\).
The displayed calculations correctly verify:
Thus the constructed allocation has gap zero. Fractional masses do not entail fractional order copies within any schedule.
The anchor argument correctly forces the common income.
Only anchor workers can deliver the anchor order, and each anchor schedule delivers at most one copy. Since anchor mass and anchor demand both equal \(\gamma\), all anchor mass must use schedules delivering that copy. Those schedules have income one.
A positively weighted schedule contributes positive allocation mass and therefore cannot be discarded by the essential supremum or essential infimum. Consequently, gap zero forces every positively weighted schedule to have income one.
The main mass is positive. Under the task’s allocation definition using sums of schedule masses, at least one main schedule therefore has positive weight. Its income equation yields the integer target-sum equation required by the encoding lemma.
This establishes the reverse implication without substituting type-average income for individual schedule income.
The size estimates are correct. The integers used in the construction have \(O(k\log(k+1))\) bits, and the dyadic masses and demands have \(O(\log(Mk))\) bits. Including the network, order descriptions, and worker descriptions, the stated bound on \(L\) is valid.
For the explicitly represented exact-cover source instance, the construction takes polynomial bit time. Hence an algorithm with running time \(\operatorname{poly}(m,\tau,L,|V|,|E|,C)\) would imply \(\mathrm P=\mathrm{NP}\). The same conclusion holds for the stated parameterized running time because \(\tau=3\) and \(C=1\) throughout the reduction.
The proof establishes hardness, not membership in \(\mathrm{NP}\), strong hardness, or an approximation theorem for this continuous model. None of those additional claims is needed to answer the task.
The contextual source descriptions are consistent with [FairFoody](https://arxiv.org/abs/2203.08849) and the [fractional-server paper](https://ojs.aaai.org/index.php/AAAI/article/download/29969/31697). Neither source is used as a substitute for the reduction.
Required feedback: No repair or additional clarification is necessary.
⟨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.