EF1 + MMS + Pareto-Optimal Service Allocation on a Path → Integral Minimum-Cost Flow Complexity open
Unsolved
Why this question matters
Moderate: it would settle the combined fairness/efficiency case left open for two-dimensional path service costs, with a concrete allocation algorithm for delivery or field-service work.
Fair Allocations of Service Tasks with Two-Dimensional Costs (2025, Table 1 and Theorems 1–3) proves EF1 alone and MMS+PO in P, and all three together under time- or distance-dominant costs. The general positive two-cost case has unknown existence and computation.
The reduction to construct
Input is an unweighted path with one hub, n identical agents, m−1≥n task vertices, and positive binary rational travel and service costs c_d,c_t. For a bundle S, cost is 2c_d(max(R(S),h)−min(L(S),h))+c_t|S|, with cost zero for empty S. Outputs are all complete allocations satisfying chores-EF1 (each nonempty own bundle can lose one task to cost no more than another bundle), cost at most the minimax-share threshold for every agent, and Pareto optimality; output NO-SOLUTION if none exists.
Input is a directed network with integral capacities, binary rational arc costs, and supplies/demands. Outputs are all integral feasible flows of minimum total cost, or NO-SOLUTION when infeasible.
Give deterministic polynomial-time F and G such that every optimal flow returns a valid triple-fair service allocation, or NO-SOLUTION exactly when no such allocation exists. A successful structural flow formulation would classify existence and construct witnesses in polynomial time.
High: the known dynamic program builds MMS plus Pareto-optimal allocations, but EF1 compares bundles after removing one owned task. Those global cross-bundle comparisons may not admit a polynomial flow state.
What a complete answer must include
Provide deterministic polynomial-time F and G with bit-size bounds. Prove correctness for every legal input and every valid target output, including NO-SOLUTION where defined; independently check recovered answers on representative instances. A generic SAT or ILP encoding alone does not meet the novelty goal.
References
Literature checked 2026-09-26. Web search 2026-09-26: "fair allocation service tasks EF1 MMS Pareto path 2025", "service tasks EF1 MMS PO path 2026", and board aliases. Read the primary model, Table 1, Proposition 2 and Theorems 1–3. No later matching resolution found in indexed results. Gate 5 route: extend the contiguous-bundle structure used for MMS+PO with a small set of EF1-critical boundary tasks, then encode allowed transitions as flow. The missing step is a polynomial state bound; untested. Gate 6 not assessed.