d4-conf-ecai-2022-0007

The strongest case is a continuous mode utility OSAP for a large market of standardized satellite booking requests.

The anchor is Theorem 1 (NP-hardness), proved in this paper. It says that deciding whether an OSAP has a feasible allocation with mode utility at least \(U\) is NP-complete; checking a proposed allocation is polynomial. The proof reduces RCPSP with disjunctive resources, activities using at most one resource, and no precedence constraints: each resource becomes a satellite, and each activity becomes a global request with one mode of reward \(1\), minimum slot duration equal to the activity’s duration, and a reservation window \([0,C_{\max}]\). All activities can be scheduled within \(C_{\max}\) exactly when the OSAP can achieve utility at least the number of activities. The paper cites [15] for the source problem’s hardness and gives the reduction here.

Here is the mirror I would put to a prover. Call it Continuous Mode-Utility OSAP. An instance has a finite set of satellites, a finite rational time grid, and a support of \(\tau\) request types with rational masses \(\mu_t\), summing to \(1\). A type is a complete OSAP request template: it includes the request kind, reservation windows and eligible satellites, minimum slot duration, time references if any, modes and their rewards, and any other feature affecting its feasible allocations. Each client assigned to type \(t\) must receive one ordinary, valid OSAP allocation for that type.

Let \(Q_t\) be the set of such single-client allocations. Choose nonnegative masses \(x_{tq}\), where \(x_{tq}\) is the share of type \(t\) receiving allocation \(q\). Require
\[ \sum_{q\in Q_t}x_{tq}=\mu_t. \]
For each satellite-time cell \((s,j)\), let \(\kappa_{sj}\) be its available booking capacity per unit of population mass, and let \(a_{q,sj}\) indicate how much of that cell allocation \(q\) uses. Require
\[ \sum_t\sum_{q\in Q_t} a_{q,sj}x_{tq}\le \kappa_{sj} \quad\text{for every }(s,j). \]
The \(\kappa_{sj}\) values describe a regime where satellite opportunities scale with the client cohort—for example, repeated standardized booking cycles across a growing constellation. The question is whether the maximum
\[ \sum_t\sum_{q\in Q_t}\Omega(q)x_{tq} \]
is at least \(U\), where \(\Omega(q)\) is the mode reward from the paper. A solution is a finite list of type-allocation pairs and rational masses satisfying these constraints and reaching the threshold. Each infinitesimal client gets a whole allocation; only the aggregate mass assigned to each allocation is fractional.

A plausible regime is a large constellation marketplace serving thousands or millions of clients through a comparatively small catalogue of booking products. Clients within a type share their target region or visibility class, timing template, duration requirements, mode ladder, and reward structure. Thus \(N\) can greatly exceed \(\tau\), while the replicated orbit opportunities keep per-capita capacity meaningful. This is a specific regime, not a claim that every OSAP order book has few types.

I expect this mirror to be Class A, provisionally. Its mode choice and resource use become a linear allocation problem over request configurations, inviting column generation. The key algorithmic question is whether the pricing problem for one type—choosing its best valid mode and slot pattern given satellite-time prices—is polynomial. Time-tagged requests look promising; global requests with a total-duration threshold may make pricing more difficult. If pricing is hard even for one or a few types, that could instead reveal continuum-specific hardness. A second question is how the continuous optimum relates quantitatively to a finite high-multiplicity OSAP with the same type proportions: does it give an additive approximation, and how does the gap depend on \(\tau\) and the grid?

This mirror covers Theorem 1’s mode-utility allocation question. It does not claim a complexity result for leximin fairness or the secondary window utility objective.

The soft spot is the resource scaling: positive population mass cannot keep receiving exclusive, fixed-duration reservations on a fixed finite collection of satellite windows. The mirror therefore co-scales the supply of opportunities, an assumption the authors would need to accept for this regime. The hardness reduction also uses a collection of activities whose distinct scheduling constraints may require many types, so Theorem 1 alone says little about hardness at moderate \(\tau\). Those limits are real, but the mirror retains the paper’s request modes, valid per-client schedules, and satellite-time conflicts while making the per-capita version of the same allocation question explicit.