d4-conf-aaai-2015-0012 (d4-conf-aaai-2015-0012)

Given a finite road graph with rational edge weights, rational type masses \(\mu_t\) summing to \(1\), fixed car capacity \(S\), and a type-level trust graph, find a minimum-cost allocation of commuters to car configurations and transit singletons. Each type records pickup and destination hubs, driver status, capacity, cost parameters, and trust class; linked classes have mutually eligible members. A car configuration is a multiset of at most \(S\) commuters satisfying the paper’s driver and connectivity constraints. Let \(d_C\) be its minimum valid route cost, computed by Theorem 1 under antimonotonic route costs, and let \(d_t\) be the transit cost for a non-driver singleton. Find configuration masses \(x_C \ge 0\) minimizing \(\sum_C d_C x_C\), subject to \(\sum_C a_{tC}x_C=\mu_t\) for every type \(t\), where \(a_{tC}\) counts type-\(t\) commuters in \(C\); return route witnesses for car configurations.

A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input includes a connected undirected road graph \(M=(P,Q)\) with positive rational edge lengths; write \(m=|P|+|Q|\) and let \(L\) be the total input bit length. Fix an integer capacity bound \(S\geq2\), independent of the input.
Each type specifies distinct pickup and destination hubs, driver status, a trust class, and capacity \(s_t\in\{1,\ldots,S\}\) for drivers or \(s_t=0\) otherwise. Driver mass is positive. Each driver type supplies a nonnegative, strictly increasing rational piecewise-linear function \(g_t\) of route length, encoded by breakpoints and affine coefficients; each non-driver type supplies a positive rational transit cost \(d_t\).
The undirected trust graph includes an explicit within-class eligibility flag for each class. In a configuration, distinct commuter occurrences are adjacent exactly when their classes are linked, or their common class has this flag; their induced graph must be connected.
A car configuration \(C\) is a nonempty multiset containing exactly one driver occurrence of type \(r\), with \(|C|\leq s_r\). Its valid routes are road walks beginning at that driver's pickup and ending at its destination, with a pickup occurrence strictly before a destination occurrence for every commuter; repeated hubs and repeated visits are allowed. Define \(d_C=\min_W g_r(\operatorname{length}(W))\) over valid routes.
Let \(\mathcal F\) consist of all valid car configurations and every non-driver transit singleton. With \(a_{tC}\) denoting multiplicity, find rational configuration masses minimizing \(\sum_{C\in\mathcal F}d_Cx_C\), subject to \(x_C\geq0\) and \(\sum_{C\in\mathcal F}a_{tC}x_C=\mu_t\) for each type, and return optimal route witnesses for cars with positive mass. Drivers cannot use transit; any optimal route may resolve a tie.

Is this exact continuous allocation problem solvable in polynomial time in \(m,\tau,L\) for every fixed \(S\), or is it NP-hard for some fixed \(S\)? State any dependence on \(S\) explicitly.

For discrete cars under antimonotonic signed route costs, shortest-path concatenation over admissible pickup–destination orders yields an optimal route; the order search is exponential in car size ([route characterization](https://doi.org/10.1609/aaai.v29i1.9242)).
A later discrete treatment retains exponential order enumeration and uses branch and bound for coalition allocation ([discrete extension](https://filippobistaffa.github.io/papers/2017aij.pdf)); no result settling this precise continuous formulation was identified.

Result

The exact continuous allocation problem is polynomial-time solvable in \(m,\tau,L\) for every fixed \(S\geq2\), including the required optimal route witnesses.

The polynomial degree may depend on \(S\). More explicitly, define
\[ K_S=\tau\binom{\tau+S-1}{S-1}+\tau. \]
An algorithm has bit complexity bounded by \((2S)!\operatorname{poly}(m,L,S,K_S)\), where the polynomial has degree independent of \(S\). Since \(K_S=O_S(\tau^S)\), this is polynomial for every fixed \(S\).

The proof enumerates bounded-size configurations, computes each configuration’s exact minimum route cost, and solves an explicitly encoded rational linear program.

1. Enumerating configurations

Let \(D\) be the number of driver types and \(N\) the number of non-driver types, so \(D+N=\tau\).

A car configuration contains one occurrence of a driver type \(r\) and a multiset of at most \(s_r-1\) non-driver occurrences. It cannot contain another driver occurrence, including another occurrence of type \(r\).

The number of multisets of at most \(S-1\) elements drawn from \(N\) types is
\[ \binom{N+S-1}{S-1}. \]
Indeed, their multiplicities are nonnegative integers with sum at most \(S-1\); adding a slack coordinate gives the usual stars-and-bars count. The formula also holds when \(N=0\).

Consequently, the number of candidate cars, together with all transit singletons, is at most
\[ D\binom{N+S-1}{S-1}+N\leq K_S. \]

For each candidate, check the driver’s capacity and construct its trust graph on its individual occurrences. For each pair of distinct occurrences, use their classes and the explicit within-class flag to determine adjacency. Test connectivity on this graph, which has at most \(S\) vertices.

This occurrence-level test handles repeated types correctly. In particular, repeated occurrences of the same class are not automatically adjacent.

Every candidate passing these tests has a valid route: start at the driver’s pickup, visit each passenger’s pickup and then its destination in turn, and finish at the driver’s destination. Connectedness of the road graph supplies the connecting walks. Each commuter’s distinct pickup and destination ensure strict pickup-before-destination precedence. Thus these tests enumerate exactly the valid car configurations.

2. Exact route optimization for one configuration

Fix a valid car configuration \(C\) of size \(k\leq S\), and label its occurrences \(1,\ldots,k\), with occurrence \(1\) the driver.

Write \(p_i\) and \(q_i\) for occurrence \(i\)’s pickup and destination. Let \(\delta(u,v)\) be the shortest-path distance between road vertices \(u\) and \(v\).

Introduce distinct labeled events \(P_i\) and \(D_i\), located respectively at \(p_i\) and \(q_i\). Let \(\Pi_C\) consist of all event orders satisfying:

• \(P_1\) is first and \(D_1\) is last;
• \(P_i\) precedes \(D_i\) for every passenger occurrence \(i\).

Different events may be located at the same hub. If \(h(e)\) denotes an event’s hub, define
\[ \ell(\pi)=\sum_{j=1}^{2k-1}\delta\bigl(h(\pi_j),h(\pi_{j+1})\bigr). \]

Route lemma. The minimum valid route length for \(C\) is
\[ \ell_C=\min_{\pi\in\Pi_C}\ell(\pi). \]

Here, as in the stated walk definition, different commuters may use the same visit to a hub. Each individual commuter must have its pickup visit strictly before its destination visit.

Lower bound

Take any valid road walk \(W=(v_0,\ldots,v_b)\). For each passenger occurrence, choose witnessing indices \(a_i<b_i\) with \(v_{a_i}=p_i\) and \(v_{b_i}=q_i\). For the driver, use the initial and final indices.

Sort these selected events by their visit indices. Break ties with the driver’s pickup first and its destination last, when applicable. No commuter’s own pickup and destination are tied, because their witnessing indices are strictly ordered. The resulting order \(\pi\) therefore belongs to \(\Pi_C\).

The subwalk between each consecutive pair of selected events has length at least the corresponding shortest-path distance. These subwalks partition \(W\), allowing zero-edge subwalks for tied indices. Hence
\[ \operatorname{length}(W)\geq\ell(\pi)\geq\min_{\pi'\in\Pi_C}\ell(\pi'). \]

Attainment

Conversely, take an order \(\pi\in\Pi_C\) and concatenate shortest paths between its consecutive event hubs. A connection from a hub to itself is the zero-edge walk.

Each event is realized at the appropriate concatenation boundary. Boundary visit indices are nondecreasing in event order. For any commuter, its pickup boundary precedes its destination boundary in the event order. These two boundaries cannot have the same visit index, because \(p_i\neq q_i\). Thus its pickup visit is strictly before its destination visit.

The concatenation is therefore valid and has length exactly \(\ell(\pi)\). This proves the lemma, including attainment of the minimum.

Repeated visits and incidental passage through other service hubs cause no problem: validity requires the existence of suitable service visits, and the designated boundaries provide them.

Cost and witness

Since \(g_r\) is strictly increasing,
\[ d_C=g_r(\ell_C). \]
Thus route optimization requires no convexity assumption on \(g_r\). Its piecewise-linear description is used only to evaluate it at the exactly computed rational length.

There are at most \((2k-2)!\leq(2S-2)!\) orders to inspect. Store a minimizing order and concatenate stored shortest-path witnesses.

Because road edge lengths are positive, shortest paths can be chosen simple. The resulting optimal route has at most
\[ (2k-1)(|P|-1)\leq(2S-1)(|P|-1) \]
edges. The witness can additionally record the service indices for all labeled occurrences.

3. Polynomial encoding length of the costs

Shortest paths and their witnesses can be computed in polynomial bit complexity, for example by running an exact shortest-path algorithm from every road vertex.

To check the numerical bounds explicitly, let \(H_Q\) be the product of the denominators of all road edge lengths. Its binary length is \(O(L)\). Scaling every edge length by \(H_Q\) produces integer lengths of binary length \(O(L)\).

A simple path contains at most \(|P|-1\) edges. Therefore every shortest-path distance has a rational representation of binary length \(O(L+\log m)\). Each candidate event-order length sums at most \(2S-1\) such distances, giving binary length
\[ O(L+\log m+\log S). \]

Locate \(\ell_C\) among the rational breakpoints of \(g_r\) by exact comparisons, then evaluate the applicable rational affine expression. Its coefficients are part of the input, so \(d_C\) also has binary length polynomial in \(L,\log m,\log S\). Transit costs already have their input encoding lengths.

Accordingly, all configuration costs and multiplicities can be encoded using a number of bits polynomial in \(m,L,S,K_S\). No population is expanded according to the denominators of its masses.

4. Exact continuous allocation

Having explicitly constructed \(\mathcal F\) and its costs, solve the rational linear program
\[ \min\left\{\sum_{C\in\mathcal F}d_Cx_C: \sum_{C\in\mathcal F}a_{tC}x_C=\mu_t\ \text{for every }t,\quad x_C\geq0\right\}. \]

It has \(\tau\) equality constraints, at most \(K_S\) variables, and the polynomial encoding length established above.

Feasibility and boundedness

Every driver singleton is a valid car: its occurrence graph is connected and a shortest path joins its distinct endpoints. Every non-driver has its transit singleton. Assigning mass \(\mu_t\) to each type’s corresponding singleton proves feasibility.

For any feasible allocation, sum the type constraints:
\[ \sum_{C\in\mathcal F}|C|x_C=\sum_t\mu_t=1. \]
Since every configuration is nonempty and \(x_C\geq0\), every coordinate satisfies \(0\leq x_C\leq1\). The feasible set is therefore nonempty and compact, so the linear objective attains its minimum.

Applying polynomial-time rational linear programming

The standard rational linear programming theorem provides an exact rational optimum in time polynomial in the binary encoding length of the explicitly given program. It applies to programs with equality constraints and lower-dimensional feasible sets; these require no interior-point assumption. Polynomial bit complexity follows from the ellipsoid theorem, including its reduction from optimization to feasibility. See the [MIT lecture on the ellipsoid method](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).

All hypotheses have been checked: the program has rational coefficients, polynomial encoding length for fixed \(S\), a nonempty feasible set, and an attained finite optimum.

For every car with positive mass in the returned optimum, output its stored optimal route. This meets the witness requirement because \(d_C\) is the attained cost of that route.

5. Additional bound on optimal allocations

An optimal allocation exists with at most \(\tau\) positive configuration masses, each having binary length \(O(L+\tau\log S)\).

To prove the support bound, choose an optimum \(x\) with the smallest possible number of positive coordinates. Let \(A=(a_{tC})\). If its positive-support columns were linearly dependent, there would be a nonzero vector \(v\), supported there, with \(Av=0\).

For sufficiently small positive \(\varepsilon\), both \(x+\varepsilon v\) and \(x-\varepsilon v\) remain feasible. Optimality forces \(d^\mathsf{T}v=0\), since otherwise one perturbation improves the objective.

Moreover,
\[ \sum_C|C|v_C=0. \]
Since every \(|C|\) is positive, \(v\) has both positive and negative coordinates. Moving along \(v\) until the first positive coordinate becomes zero therefore preserves feasibility and optimality while reducing support, a contradiction. The support columns are independent, so there are at most \(\tau\).

All type singleton columns occur in \(A\), so \(A\) has row rank \(\tau\). Extend the support columns to a square nonsingular matrix \(B\) using columns of \(A\). The associated coordinates solve \(Bx_B=\mu\), with zero coordinates on the added columns.

Let \(H_\mu\) be the product of the input mass denominators; its binary length is \(O(L)\). Cramer’s rule gives coordinate denominators dividing \(H_\mu|\det B|\). Each column of \(B\) has nonnegative entries summing to at most \(S\), hence Euclidean norm at most \(S\). Hadamard’s inequality yields
\[ 1\leq|\det B|\leq S^\tau. \]
Because the coordinates lie in the interval from zero to one, their numerators have the same size bound. This proves the claimed binary length.

6. Dependence on capacity and conclusion

Configuration enumeration and route evaluation take at most \(K_S(2S-2)!\operatorname{poly}(m,L,S)\) bit operations. Building and solving the allocation LP, and emitting the witnesses, take \(\operatorname{poly}(m,L,S,K_S)\) additional bit operations.

Thus the stated bound \((2S)!\operatorname{poly}(m,L,S,K_S)\) follows. It is polynomial in \(m,\tau,L\) for every fixed \(S\). It does not assert polynomial time when \(S\) varies with the input.

The exponential order enumeration and branch-and-bound allocation in the [discrete extension](https://filippobistaffa.github.io/papers/2017aij.pdf) do not obstruct this conclusion: fixed capacity bounds the order search, and the present allocation variables satisfy an explicit rational linear program.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct: the argument establishes polynomial-time solvability for every fixed \(S\), with exact rational allocation masses and optimal route witnesses. I found no mathematical errors or gaps requiring repair.

• Configuration enumeration is complete and correctly bounded.

Exactly one driver occurrence means that all remaining occurrences must be non-drivers; the prover correctly excludes additional occurrences of driver types.

The count \(\binom{N+S-1}{S-1}\) correctly counts non-driver multisets of total multiplicity at most \(S-1\), including the empty multiset. It remains valid when \(N=0\). Consequently, the stated upper bound \(D\binom{N+S-1}{S-1}+N\leq K_S\) is valid.

Checking capacity and connectivity on individual occurrences implements the task’s eligibility rule, including repeated types and classes without within-class eligibility. A single-vertex occurrence graph is connected, so driver singletons are included.

The sequential pickup–destination construction proves route existence for every candidate passing these tests. Road connectivity supplies all connecting walks, and distinct endpoints ensure strictly ordered pickup and destination visits. Thus no further route-feasibility restriction is omitted.

• The route lemma’s lower bound is valid.

Every valid walk supplies witnessing indices for each passenger. The initial and final visits supply witnesses for the driver, whose distinct endpoints ensure these indices differ.

Sorting the selected events by visit index preserves every commuter’s required precedence. The prescribed tie-breaking places the driver’s pickup first and destination last. Ties between different commuters are permitted by the task.

Because the selected events include both endpoints of the walk, the consecutive subwalks cover the entire walk without overlapping edges. Tied indices contribute zero-edge subwalks. Each subwalk’s length is at least the corresponding shortest-path distance, proving the stated lower bound.

• The route lemma’s attainment argument is valid.

Concatenating shortest paths produces the required start and end hubs. Event boundaries occur in nondecreasing visit-index order.

A commuter’s pickup and destination boundaries cannot have equal visit indices: that would place both events at the same road vertex, contradicting its distinct pickup and destination hubs. This verifies strict precedence even when other events share hubs or boundaries.

Incidental visits to service hubs impose no additional obligation under the task’s existential route-validity definition. The designated boundaries therefore suffice. The finite order search attains the minimum route length.

• Cost evaluation and route witnesses are correct.

Strict increase of \(g_r\) makes a minimum-length route a minimum-cost route. No convexity hypothesis is required, and exact evaluation of the supplied rational piecewise-linear function produces \(d_C\).

Fixing the driver’s first and last events leaves at most \((2k-2)!\) orders. Restricting those orders to passenger precedence can only reduce this count. The count also handles \(k=1\).

Positive edge lengths allow simple shortest-path witnesses. Therefore the concatenated witness has at most \((2k-1)(|P|-1)\) edges. Recording service indices verifies occurrence-level precedence, including repeated passenger types.

• The numerical encoding bounds are sound.

The product of the road-edge denominators has binary length \(O(L)\), since their individual encoding lengths contribute to the total input length. Scaling by this product gives integer edge lengths of binary length \(O(L)\).

Simple shortest paths contain at most \(|P|-1\) edges. All distances share the scaling denominator, so summing at most \(2S-1\) distances yields the claimed \(O(L+\log m+\log S)\) representation bound.

Exact breakpoint comparisons and rational affine evaluation preserve polynomial encoding length. Multiplicities are integers at most \(S\). Thus the explicitly constructed allocation LP has polynomial encoding length in the stated parameters, without expanding rational population masses.

• The allocation LP is feasible, bounded, and exactly solvable in polynomial time.

Assigning each type’s mass to its corresponding singleton satisfies every equality constraint. Drivers use car singletons, and non-drivers use transit singletons, as required.

Summing the type constraints gives \(\sum_C |C|x_C=1\). Since every configuration is nonempty and every coordinate is nonnegative, each coordinate lies in \([0,1]\). The finite-dimensional feasible set is closed, bounded, and nonempty, so the objective attains a finite minimum.

The prover states the applicable standard theorem: explicitly encoded rational linear programs admit exact polynomial-time optimization, including equality constraints and lower-dimensional feasible regions. All required hypotheses are verified. The cited lecture discusses arbitrary-polyhedron feasibility, finite-precision complexity, and optimization through a primal–dual feasibility system; its integer-data formulation is compatible with rational inputs through denominator clearing. [MIT ellipsoid-method lecture](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).

Returning the stored route for every positive-mass car satisfies the witness requirement.

• The additional support and mass-size bounds are valid.

A minimum-support optimum exists because support cardinalities range over a finite set. Dependence among its support columns gives a nonzero supported null vector. Small perturbations in both directions preserve nonnegativity, so optimality forces zero objective change.

The identity \(\sum_C |C|v_C=0\) forces the null vector to have both signs. Moving until a supported coordinate reaches zero preserves feasibility and optimality while strictly reducing support. This contradiction proves column independence and the support bound of \(\tau\).

Singleton columns give full row rank. Extending the support columns to a nonsingular square matrix is therefore justified. Cramer’s rule, the common mass denominator, and Hadamard’s inequality yield the stated denominator bound. Each column’s Euclidean norm is at most its entry sum, which is at most \(S\). Since the coordinates lie in \([0,1]\), their numerator lengths obey the same bound.

• The complexity conclusion matches the assignment.

Configuration enumeration, bounded event-order search, exact cost computation, LP optimization, and witness output all fit the stated \((2S)!\operatorname{poly}(m,L,S,K_S)\) bound. With \(K_S=O_S(\tau^S)\), this is polynomial in \(m,\tau,L\) for every fixed \(S\).

The prover explicitly allows the polynomial degree to depend on \(S\) and makes no polynomial-time claim for variable capacity. This answers the requested dependence on \(S\).

No corrective feedback is necessary.

⟨structured verdict parsed — rendered above⟩