Organizations: Department of Network Intelligence, Pengcheng Laboratory, Shenzhen, China · School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen Campus, Shenzhen, China
Short-interval wireless schedulers must return a complete, feasible beam-and-resource allocation before each execution deadline, and a late or invalid output gives no utility in the current control cycle. Searching longer can increase transmitted traffic, but it may also miss the deadline or leave only an infeasible intermediate solution. We propose Feasibility-Preserving Transactional Refinement (FPTR), which always keeps a validated feasible allocation, the incumbent. Each refinement stage builds a separate candidate and leaves the incumbent unchanged. A candidate replaces the incumbent only if it is complete, passes the feasibility validator before its stage cutoff, and strictly improves the objective; otherwise it is discarded. Four refinement stages use this rule: buffer-aware resource selection, compatibility-group (CG) user sharing, beam-mask rebuilding from remaining demand, and joint reassignment of two resources. On 150 fixed synthetic instances, the full pipeline (Full) raises traffic by 3.83% on average over a lightweight beam-first reference and by 1.79% over its Base constructor. In a separate suite with matched inputs, Full exceeds six independent search baselines (ALNS, tabu search, GA, simulated annealing, iterated local search, and GRASP) by 6.68-8.35%, where outputs later than 100 ms receive zero utility. All 750 Full runs in the internal suite returned feasible allocations, and none exceeded 100 ms. Separating mandatory output construction from optional refinement lets spare computation time improve the allocation without endangering the incumbent. The open-source implementation supports independent reproduction.
Figures & tables
Figure 1: Schematic overview of one scheduling interval. Beam activation, user assignment, finite demand, and resource sharing must be resolved before the execution deadline.
z
(−∞,−10]
(−10,0]
(0,3]
(3,10]
(10,15]
(15,20]
(20,∞)
q(z)
0
8
24
90
120
162
222
Table 1: Stepwise mapping from effective link value (dB) to traffic units.
Figure 2: Deadline-aware FPTR pipeline. (a) Stages use cumulative completion cutoffs under the 87-ms internal budget. (b) A candidate replaces the incumbent only after timely completion, validation, and strict improvement; otherwise the feasible incumbent is retained. Final validation and serialization use the reserved 3-ms tail.
1:
Initialize I←I0 , where I0 is the empty complete feasible allocation.
2:
for each stage j in the order Base,Global,CG,Remask,Pair do
3:
Record stage-entry time τin ; if τin≥tj then continue .
4:
Construct isolated candidate C←Rj(I) without modifying I .
If C is complete, strictly improving, and before tj , evaluate V(C)
and record τdone(C) when it returns.
5:
if C passes ( 9 ) then I←C ; otherwise discard C .
Algorithm 1 FPTR commit-or-discard refinement
Configuration
Cumulative stage added and purpose
Cutoff (ms)
BeamFirst
independent aggregate-mask reference
–
Base
diversified-mask feasible construction
45
Global
+ buffer-aware marginal selection
60
CG
+ CG-focused masks and valid sharing
70
Remask
+ remaining-demand masks and one-resource repair
78
Full
+ two-resource ruin-and-recreate
84
Table 2: Cumulative configurations and stage cutoffs for an 87-ms budget.
Regime
N
K
P
T
L
L/(PT)
Small balanced
20
18
8
4
14
0.44
Medium long-tail
50
36
16
9
46
0.32
Medium tight
50
36
16
9
26
0.18
Large mixed
100
72
32
18
127
0.22
Large nonadjacent
100
72
32
18
92
0.16
Table 3: Fixed main regimes; each contains 30 consecutive seeds.
Figure 3: Quality and runtime: (a) stage gains, (b) regime gains, (c) budget trade-off, and (d) empirical CDF of wall time; intervals are stratified 95% bootstrap estimates.
Baseline
W/T/L
Mean rel. gain (%)
95% CI (%)
Deadline misses (of 750 runs)
ALNS
134/5/11
7.80
7.03–8.56
74
Tabu
139/4/7
7.77
7.01–8.52
18
GA
127/2/21
6.68
5.91–7.47
44
SA
137/4/9
7.90
7.19–8.58
15
ILS
137/4/9
8.35
7.53–9.13
41
GRASP
140/2/8
7.61
6.88–8.33
27
Table 4: Matched external-baseline comparison at Γ=87 ms. Quality uses five-run instance medians and regime-stratified relative gains, equally weighted across regimes; W/T/L denotes wins/ties/losses of Full.
Figure 4: Stress and calibration: (a) co-varying CG size and coverage and (b) exact optimality gaps on 12 cases.
We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an Ω(1/γ) fraction of the optimal unfair allocation, where γ is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.
Christopher En, Yuri Faenza, Andrea Lodi +1
Columbia University, IEOR Department · Cornell Tech · Universidad de Chile
We study a sequential resource allocation problem motivated by adaptive network recruitment, in which a limited budget of identical resources must be allocated over multiple rounds to individuals with stochastic referral capacity. Successful referrals endogenously generate future decision opportunities while allocating additional resources to an individual exhibits diminishing returns. We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities. In the multi-round setting, the resulting Bellman recursion is intractable due to the stochastic, high-dimensional evolution of the frontier. To address this, we introduce a population-level surrogate value function that depends only on the remaining budget and frontier size. This surrogate enables an exact dynamic program via truncated probability generating functions, yielding a planning algorithm with polynomial complexity in the total budget. We further analyze robustness under model misspecification, proving a multi-round error bound that decomposes into a tight single-round frontier error and a population-level transition error. Finally, we evaluate our method on real-world inspired recruitment scenarios.
Yuqi Pan, Davin Choo, Haichuan Wang +3
Harvard University · University of Witwatersrand · Wits Health Consortium +1
Dynamic multi-resource allocation is a central problem in shared computing environments, where users' demands arrive sequentially and resources must be distributed fairly without knowledge of future demands. Existing methods emphasize fairness guarantees such as Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, but often overlook system utility. Moreover, these fairness criteria are mutually incompatible, preventing strict enforcement of them at the same time. We propose a neural allocation mechanism that reconciles fairness with utility through multi-objective optimization during sequential rollout. We first formalize fairness in the dynamic setting via stepwise loss functions for Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, enabling differentiable training. Leveraging non-wastefulness, we parameterized the solutions by constraining allocations to the subspace of demand while allowing elastic over-allocation when resources remain available. Empirical results demonstrate that our learned allocator achieves substantially higher utility at comparable levels of fairness, uncovering clear Pareto-frontier-like tradeoffs across metrics.
Kaiqi Jiang, Karim El Husseini, Wenzhe Fan +1
Computer Science Dept., University of Illinois Chicago, Chicago, Illinois, USA