cloud resource schedulers

Abstract: The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm. On a single machine, PF coincides with weighted Round-Robin, which is $2$-competitive for weighted completion time with uniform release dates (optimal for nonclairvoyant algorithms) and $(2+\varepsilon)$-speed $O(1/\varepsilon)$-competitive for weighted flow time. Known guarantees beyond a single machine are weaker. This raises a central question: Are these heterogeneous environments intrinsically harder than a single machine under nonclairvoyance? We show that they are not: PF retains both single-machine guarantees on the novel class of support-submodular polytopes, which includes unrelated machines and polymatroids. On unrelated machines, this refutes a belief (JACM'18, SODA'25) that PF is not $O(1)$-speed $O(1)$-competitive for weighted flow time. Our main technical contribution is an equivalent characterization: a polytope is support submodular if and only if, for all job weights, the optimal weighted completion time is concave in the processing requirements. This structural insight underlies both guarantees. For general PSP, the picture changes: we give the first lower bound above $2$, showing that every randomized nonclairvoyant algorithm has a competitive ratio of at least $2+10^{-5}$ for weighted completion time, even with uniform release dates. On the positive side, we substantially improve the best known guarantee for weighted completion time from $27$ (SICOMP'26) to $4$ via a new dual-fitting analysis of PF. For weighted flow time, we show that PF achieves the first $O(1)$-speed $O(1)$-competitive nonclairvoyant guarantee for graph scheduling.

Abstract: We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\eps$ is achievable with robustness $\eps^{-1/2}+\frac16+O(\sqrt\eps)$, whereas all previous algorithms required robustness $Θ(1/\eps)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions.

Abstract: Smith's rule orders jobs by their weight-to-processing-time ratios. We study the robustness of its list schedule on identical parallel machines when job $j$ is ordered using a nominal processing time $μ_j$ and its true processing time satisfies $μ_j\leq p_j\leqαμ_j$, where $α\geq1$. We determine the exact worst-case approximation ratio against the clairvoyant optimum, taking the supremum over machine counts. The ratio is an explicit continuous piecewise-algebraic function of $α$. It equals the Kawaguchi--Kyan constant $(1+\sqrt{2})/2$ at $α=1$ and is exactly $\sqrtα$ for $α\geq4$. On one machine the exact ratio is $\sqrtα$. For every fixed machine count, no deterministic nonpreemptive algorithm can improve on this guarantee, even with knowledge of $α$. The proof reduces to a common nominal Smith ratio and endpoint errors. Cutting the list schedule at its minimum final machine load yields a prefix--suffix certificate; two packings of matching lower-bound instances explain the branches below $α=4$. We also prove a nominal-to-robust transfer: any fixed schedule ordered by nominal Smith ratios on each machine, with nominal approximation ratio $1+δ$, has realized ratio at most $\sqrtα+αδ$. A nominal approximation scheme then gives, for every fixed $\varepsilon>0$, a deterministic polynomial-time algorithm independent of $α$ with ratio $(1+\varepsilon)\sqrtα$ simultaneously for $1\leqα\leq4$.

Abstract: We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve $1-e/e^e\approx0.8206$, matching the upper bound of Chierichetti, Giacchini, Panconesi, and Vattani [ICALP 2025]. For exactly $n$ i.i.d.~arrivals, we obtain the same guarantee up to an additive $O(n^{-1/2})$ loss. Our key technical contribution is an exact correspondence between Poisson matching and exponential scheduling, preserving both online performance and the expected offline optimum. To prove the latter, we show that the distribution of the maximum of a random supermodular set function is determined by its joint distributions along chains of nested sets, a result of independent interest. This reduces the analysis to chains, where classical Poisson--exponential duality applies. The offline equivalence extends to arbitrary nonnegative edge weights. We then design a posterior allocation policy for exponential scheduling and use the correspondence to transfer its optimal competitive guarantee to online matching. Additionally, we show that the optimal competitive ratio under an unknown arrival law is strictly lower than $1-e/e^e$, establishing a strict separation between the known and unknown arrival models.

Abstract: We study the online fair division of indivisible goods. In the standard model, where assignments are irrevocable, no algorithm can guarantee any positive fraction of the maximin share (MMS). Reassigning earlier goods can restore fairness, but it may take value away from agents who already hold them. We ask how much fairness can be maintained if every reassignment must leave each affected agent at least as well off. We consider two forms of such upgrade recourse. Under item-level upgrades, each good an agent holds must be kept or replaced by a distinct good she values at least as much; under bundle-level upgrades, only her total value must not decrease. For item-level upgrades, we show that the optimal MMS factor is essentially $1/H_n \approx 1/\ln n$, where $H_n$ is the $n$-th harmonic number, and that fixed picking sequences nearly attain it. Since these sequences use only the agents' rankings of individual goods, knowing the actual values cannot improve the optimal factor for up to 33 agents, and improves it by at most a vanishing margin as $n$ grows. Bundle-level upgrades allow substantially stronger guarantees. By permitting several-for-one exchanges, they turn this vanishing factor into a constant: we achieve exact MMS for two agents and more than half of MMS for any number of agents, in both cases together with relaxations of envy-freeness. Finally, we show that predictions about future goods let online algorithms inherit any offline MMS guarantee, losing only an additive term bounded by the prediction error. Under item-level upgrades, however, insisting on exact MMS when predictions are correct leaves no positive guarantee when they are wrong.

Abstract: Pandora's problem is a fundamental model of sequential search in which opening each box incurs a cost. We study the variant with deadlines, where each box has a publicly known deadline for both opening and selection. We prove that a simple threshold strategy achieves a $1/2$-approximation to the optimal expected utility, improving the previous guarantee of $(e-1)/(4e)\approx0.158$ due to Berger et al. (AAAI 2024).

Abstract: We establish near-optimal regret bounds for budget-constrained online learning against arbitrary classes of budget-pacing experts in the adversarial setting. In particular, given any class of $F$ experts and a candidate budget pacing schedule, we provide a full-information algorithm which obtains regret $O(D \sqrt{\log F}+ \sqrt{T\log F})$ against all experts whose cumulative spending stays within distance $D$ of this schedule, matching lower bounds established by Braverman et al. (2025). We additionally show that our technique extends to various problems in online resource allocation, where the learner gets to see the rewards and costs of the current options available to them, and establish $O(D\sqrt{\log F})$ regret bounds when fractional allocation is allowed. This is the first algorithm we are aware of which can achieve $o(\sqrt{T})$ guarantees for such tasks.

Abstract: For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a $6$-competitive online algorithm, improving on the previous best $O(\log\!\log m)$-competitive online algorithm due to Dütting, Kesselheim, and Lucier (FOCS 2020), where $m$ is the number of items. However, Correa and Cristi's result is existential, and it was left open whether a constant competitive ratio is attainable via an efficient online algorithm that uses a polynomial number of demand oracle queries. In this work, we answer this affirmatively, giving an expected-polynomial-time $(6 + ε)$-competitive online algorithm for any constant $ε> 0$. Our techniques also recover, in the offline setting, the $(2 + ε)$-approximation result of Feige (STOC, 2006). Finally, when the buyers' valuations are drawn from identical distributions, we exploit symmetry to obtain an improved $(60/11+ε)$-competitive algorithm. Starting with the natural configuration LP relaxation for the problem, our main technical contribution is a recursive Bundle Score Generator (BSG) that resolves item conflicts by assigning correlated scores to the items requested by each buyer. Unlike the Random Score Generator whose existence is shown by Correa and Cristi, our BSG is efficiently computable in expected polynomial time. Moreover, it satisfies a stochastic dominance property that is sufficient to recover both Feige's offline result and Correa and Cristi's online result.

Abstract: We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

Abstract: We study online bipartite matching with unit-inventory reusable resources, where requests arrive in an adversarially fixed order, and each use of a resource makes it unavailable for an independent duration drawn from a resource-dependent distribution. The benchmark knows all requests in advance but cannot observe a duration before choosing the corresponding use. The classical Ranking algorithm of Karp, Vazirani, and Vazirani (STOC 1990) fixes a uniformly random priority order of the resources and matches each arriving request to its highest-priority available neighbor. It achieves the optimal competitive ratio $1-1/e$ for unweighted nonreusable resources, but whether it beats $1/2$ for reusable resources has remained open. We prove that, for unweighted resources with resource-dependent stochastic durations, Ranking achieves a competitive ratio of $(5-2\sqrt3)/3\approx0.511966$. We also give a black-box reduction from unweighted Ranking to resource-weighted matching: any unweighted competitive ratio $α>1/2$ yields a weighted ratio strictly above $1/2$. With independent sampling access to the duration distributions, the reduction gives a weighted ratio of $0.500034$. These results resolve two questions left open by Delong et al. (MOR 2024): whether Ranking beats $1/2$, and whether one can beat $1/2$ under stochastic durations. We analyze Ranking resource by resource, rather than request by request. For deterministic durations, this gives a reduction to random-order greedy for a coverage function. We then extend the analysis to stochastic durations by comparing the residual schedules of Ranking and a greedy algorithm, and apply a finer analysis of the random ranks to obtain the stated $0.511$ bound. For the weighted reduction, we apply Ranking within groups of similar weights and uses weighted greedy to control the loss between groups.

Abstract: We study the classical single-machine scheduling problem of minimizing the sum of completion times of jobs in a non-clairvoyant setting, where the processing time of each job remains unknown until its completion. This is a hard problem for which no constant competitive algorithm is possible. Inspired by robust optimization and learning-augmented algorithms, we introduce a novel robustness framework that leverages structural information provided by a classification model to overcome this limitation. Specifically, we assume that jobs are partitioned into classes and we have access to the confusion matrix of the classifier, whose entry $(k,\ell)$ indicates the number of jobs predicted to belong to class~$k$ but that actually belong to class~$\ell$. In this manner, we are able to characterize uncertainty as a set of permutations within each predicted class, rather than as a collection of discrete numerical scenarios, avoiding the computational difficulty of classical robust metrics, such as Min-Max and Min-Max Regret. In addition to these worst-case metrics, we also consider the expected objective over all scenarios. We first propose an optimal non-adaptive strategy that is oblivious with respect to all three robust criteria. We then investigate adaptive and randomized algorithms, showing that they can outperform the optimal non-adaptive strategy when the matrix exhibits particular structural properties.

Abstract: In the classical i.i.d. prophet-inequality problem, a single item is allocated to one of $n$ agents who arrive sequentially, with values drawn independently from a known distribution. When an agent arrives, their value is revealed, and the algorithm must immediately allocate the item or continue. The usual objective is utilitarian welfare: the expected value of the recipient. Guarantees for this objective extend to allocating $m$ indivisible items to sequentially arriving agents with i.i.d.\ additive values. Utilitarian welfare, however, ignores how expected utility is distributed across agents. Motivated by a rich literature in fair division, we instead evaluate an online rule by its generalized $p$-mean welfare, which includes utilitarian welfare at $p=1$, Nash welfare (the geometric mean of utilities) at $p=0$, and egalitarian welfare (the minimum utility) as $p\to-\infty$. When the number of items is large, we show that this many-item fair-division problem is captured exactly by a single-item prophet problem evaluated by the $p$-mean of agents' expected utilities. We characterize this single-item problem: every online rule is weakly Pareto dominated by a quantile-threshold rule, and an optimal egalitarian rule equalizes agents' expected utilities. We prove that for every $n$, the online optimum is at least $Γ\approx0.7059$ times the prophet's egalitarian welfare; by monotonicity of generalized means, the same guarantee holds for every $p\le1$. Further, for egalitarian welfare, the optimal ratio converges to $Γ$ as $n\to\infty$. Thus, asymptotically, optimizing egalitarian rather than utilitarian welfare costs only about four percentage points relative to the classical utilitarian ratio of $0.7451$. Finally, when $m=n$, the worst-case competitive ratio converges to zero as $n\to\infty$ for every $p\le0$, showing that the large-item assumption is necessary.

Abstract: We study learning-augmented online bipartite allocation with multiple stages. In the $k$-stage vertex-weighted fractional bipartite matching problem, demand vertices arrive in $k$ stages, and the algorithm receives possibly inaccurate predictions of the allocation in each stage. While tight consistency-robustness tradeoffs were known for the two-stage case, no nontrivial tradeoff was known for an arbitrary number of stages. Our main result is the first consistency-robustness tradeoff for $k$-stage vertex-weighted fractional bipartite matching with predictions, for every $k\ge2$. Let $R_k=1-(1-1/k)^k$. For every $R\in[0,R_k]$, our algorithm is $R$-robust and $C_k(R)$-consistent, where $C_k(R)=k(1-R)^{1/k}+R-(k-1)$. This simultaneously recovers the known tight two-stage tradeoff and the optimal prediction-free $k$-stage competitive guarantee $R_k = C_k(R_k)$, while strictly dominating the natural randomized coin-flip baseline between these endpoints. We also present an algorithm for the classical online setting, where demands arrive one by one and the number of demands is unknown in advance. It has a consistency ratio of at least $C_\infty(R)=1+R+\ln(1-R)$ for a given robustness $R\in[0,1-1/e]$, improving the best previously known tradeoff for this problem. Finally, we extend the framework to fractional AdWords and fractional predictions. Our algorithms are based on stage-wise convex programs with carefully calibrated vertex-dependent penalties. The penalties maintain a dynamic safety reserve for each supply vertex, balancing protection against adversarial future arrivals with the ability to exploit the predicted allocation.

Abstract: Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study deterministic online allocation among $n$ agents with nonnegative additive valuations, where the number of goods is unknown and the adversary can adapt to previous allocation decisions. We focus on proportionality up to one good (PROP1) and examine how advance future information affects the achievable guarantees. In the setting without additional information, we answer an open question in Choo et al. that asks whether a nontrivial deterministic approximation for PROP1 can be obtained. In particular, we present a deterministic algorithm that guarantees $Ω(1/\log(nm))$-PROP1, where $m$ is the number of goods. Moreover, we complement this result by showing that, for every fixed $n$ and all sufficiently large $m$, every deterministic algorithm has an instance with $m$ goods on which its PROP1 factor is $O(\log\log m/\log m)$. We also study the setting where the algorithm knows in advance the maximum item value (MIV) for every agent. With MIV information, we give a deterministic algorithm with competitive ratio 1/2, improving the $1/n$ guarantee in Choo et al. We also show that no deterministic algorithm can achieve a competitive ratio arbitrarily close to one, even for two agents with exact MIV information.

Abstract: We study the fair allocation of $m$ indivisible chores to $n$ agents with subadditive cost functions arriving online in an arbitrary order. Upon an agent's arrival, we are informed of her cost function and must irrevocably assign her a set of chores. We focus on the Maximin Share (MMS) fairness notion and aim to compute an allocation in which all items are assigned, and no agent incurs a cost more than $α$ times her MMS. Without any prior information about the instance (other than $n$ and $m$), we design an algorithm with a competitive ratio of $O(\min\{n, k\log^{1+ε}k, \log m\})$ for any constant $ε> 0$, where $k$ denotes the number of cost function types. Our bound matches the best known offline approximation guarantees for MMS under subadditive costs and is nearly optimal with respect to all three parameters: we show that even for binary additive cost functions, no online algorithm can achieve a competitive ratio of $o(\min\{n, k\log k, \log m\})$. We then consider the setting in which the $k$ cost function types are known in advance (though the realized types of arriving agents are not). For additive cost functions, we provide an algorithm with a competitive ratio of $O(\min\{\log k, \log(kn)/\log\log(kn)\})$, and show that constant-competitive algorithms do not exist for general $k$, even for the binary additive setting. For binary additive functions when $k \le n$, we propose a $3$-competitive algorithm and establish a lower bound of $2$.