Scheduling

Heuristics on what online algorithms should do at any given time can give large improvements to the performance of the algorithm. Today, such heuristics are mostly generated by some machine learning algorithm that was trained on what is hoped to be a similar input. We consider the online packets scheduling problem where unit size packets arrive over time, each is associated with a value and a deadline. The goal is to schedule the packets to maximize the value of the packets transmitted by their deadline. We consider an arbitrary algorithm (heuristic) and robustify it without loss. Specifically, we provide an algorithm that is at least as good as the heuristic for any input, while proving $O(1)$ competitiveness no matter how bad the heuristic is. For subclass of certain algorithms (called prediction upon arrival heuristic), we even provide a better robustness bound that provably cannot be achieved for general heuristics. Finally, we show that it is not possible to be as good as the prediction and remain $O(1)$ competitive if we consider the asynchronous model.

In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility’s placement in their favor. The aim is to design truthful mechanisms, ensuring agents cannot gain by misreporting. This problem was recently revisited through the learning-augmented framework, aiming to move beyond worst-case analysis and design truthful mechanisms that are augmented with (machine-learned) predictions. In this talk, I will focus on recent results for the egalitarian social cost objective, where the goal is to minimize the distance between the facility and the location of the agent who is the farthest from the facility.

In this talk, I will focus on the MaxMinDegree Arborescence (MMDA) problem in layered directed graphs of depth $\mathrm{\ell }\le O(\log n/\log \log n)$, which is a key special case of the Santa Claus problem. The only way we have to solve the MMDA problem within a polylogarithmic factor is via an elegant recursive rounding of the ${(\mathrm{\ell }-1)}^{th}$ level of the Sherali-Adams hierarchy. However, it remains plausible that one could obtain a polylogarithmic approximation in polynomial time by using the same rounding with only 1 round of the Sherali-Adams hierarchy. As a main result, we rule out this possibility by constructing an MMDA instance of depth 3 for which a polynomial integrality gap survives 1 round of the Sherali-Adams hierarchy. This result is tight since it is known that after only 2 rounds the gap is at most polylogarithmic on depth-3 graphs. I will conclude the talk by related open problems.

In strategic classification, agents manipulate their features, at a cost, to receive a positive classification outcome from the learner’s classifier. The goal of the learner in such settings is to learn a classifier that is robust to strategic manipulations. While the majority of works in this domain consider accuracy as the primary objective of the learner, in this work, we consider learning objectives that have group fairness guarantees in addition to accuracy guarantees. We work with the minimax group fairness notion that asks for minimizing the maximal group error rate across population groups. Motivating examples will be focused on situations where agents are competing for resources and the classification decision influences allocation policies.

We consider the Demand Strip Packing problem (DSP), in which we are given a set of jobs, each specified by a processing time and a demand. The task is to schedule all jobs such that they are finished before some deadline $D$ while minimizing the peak demand, i.e., the maximum total demand of tasks executed at any point in time. DSP is closely related to the Strip Packing problem (SP), in which we are given a set of axis-aligned rectangles that must be packed into a strip of fixed width while minimizing the maximum height. DSP and SP are known to be NP-hard to approximate to within a factor below $\frac{3}{2}$.

To achieve the essentially best possible approximation guarantee, we prove a structural result. Any instance admits a solution with peak demand at most $\left(\frac{3}{2}+\epsilon \right)\text{Opt}$ satisfying one of two properties. Either (i) the solution leaves a gap for a job with demand Opt and processing time $𝒪(\epsilon D)$ or (ii) all jobs with demand greater than $\frac{\text{Opt}}{2}$ appear sorted by demand in immediate succession. We then provide two efficient algorithms that find a solution with maximum demand at most $\left(\frac{3}{2}+\epsilon \right)\text{Opt}$ in the respective case. A central observation, which sets our approach apart from previous ones for DSP, is that the properties (i) and (ii) need not be efficiently decidable: We can simply run both algorithms and use whichever solution is the better one.

Eight among the most competitive high schools of the New York City Department of Education (NYC DOE) admit students only based on their score on a test, called SHSAT. 20$\%$ of these seats are reserved for students that the NYC DOE classifies, mostly following economic criteria, as disadvantaged. We show that the mechanism currently employed by the NYC DOE to assign these reserved seats creates a significant incentive for disadvantaged students to underperform, and we study alternatives. In particular, we highlight the superiority of one such alternative under the new ex-post hypothesis of High competitiveness (HC) of the market. We also give sufficient ex-ante conditions under which the HC hypothesis is satisfied with high probability. To prove such results, we rely on generalizations of Gale and Shapley’s marriage model involving choice functions, and on the classical occupancy problem. Using 12 years of data, we show that the NYC DOE market that originated our work satisfies the HC hypothesis.

Fairness in resource allocation is a fundamental problem that arises in a variety of domains, including healthcare, hiring, admissions, infrastructure development, recommendation systems, disaster management, and emergency response. Different ethical theories provide distinct lenses through which fairness can be understood and operationalized. In this talk, I will discuss (i) what it means to be fair in static and dynamic settings, depending on the application context, (ii) theoretical models for understanding noise and bias in data, and (iii) connections with law and policy. Through some of my recent work, I will discuss challenges related to differences in fairness objectives (e.g., how to find some “good” enough solutions across all objectives), navigating the space of human-AI collaboration (e.g., what should AI optimize?), and deviations from theoretical assumptions (e.g., of clean group memberships, discrimination models, etc).

In this talk, I will show how a generalization of the shortest remaining time first (SRPT) scheduling algorithm can be effectively used for various scheduling problems to minimize total weighted flow time. Essentially, SRPT can be interpreted as gradient descent on an estimate of the remaining jobs’ cost. In particular, we show that gradient descent is effective when the residual estimate possesses supermodularity, and that this supermodularity can be achieved when the scheduling constraints induce gross substitute valuations in the Walrasian Market.

Matching problems with one-sided preferences are seen in many applications such as campus housing allocation in universities. Popularity is a well-studied notion of fairness that captures collective welfare. This talk will be on some simple algorithms to find popular solutions for matching problems in this model.

Many classic scheduling problems can be understood as minimizing a norm objective: Most prominently, the Makespan is nothing but the ${\mathrm{\ell }}_{\mathrm{\infty }}$ norm of the vector of machine loads. Every additive objective, like for example in Set Cover, can also be understood as an ${\mathrm{\ell }}_1$ norm. Over the years, a lot of results have been generalized to ${\mathrm{\ell }}_p$ norms.

In this talk, we discuss techniques and results to go beyond ${\mathrm{\ell }}_p$ norms. With a particular focus on online problems, we identify supermodularity—often reserved for combinatorial set functions and characterized by monotone gradients—as a defining feature. Every ${\mathrm{\ell }}_p$-norm is $p$-supermodular, meaning that its $p^{th}$ power function exhibits supermodularity. The association of supermodularity with norms offers a new lens through which to view and construct algorithms.

For a large class of problems $p$-supermodularity is a sufficient criterion for developing good algorithms. Moreover, we show that every symmetric norm can be $O(\log m)$-approximated by an $O(\log m)$-supermodular norm, resulting in $O(\mathrm{poly}\log m)$-competitive algorithms for load balancing and covering with respect to an arbitrary monotone symmetric norm.

We study the computational complexity of fairly allocating indivisible, mixed-manna items. For basic measures of fairness, this problem is hard in general. The paradigm of fixed-parameter tractability (FPT) has led to new insights and improved algorithms for a variety of fair allocation problems. Our focus is designing FPT time algorithms for finding a best solution w.r.t. the fairness measure maximin shares (MMS). Furthermore, our techniques extend to finding allocations that optimize alternative objectives, such as minimizing the additive approximation, and maximizing some variants of global welfare. Our algorithms are actually designed for a more general MMS problem in machine scheduling. Here, each mixed-manna item (job) must be assigned to an agent (machine) and has a processing time and a deadline.

We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Shortest Remaining Processing Time (SRPT) algorithm is optimal (i.e., $1$-competitive) when the job sizes are known up-front [Schrage, 1968]. But in the non-clairvoyant setting where job sizes are revealed only when the job finishes, no algorithm can be constant-competitive [Motwani, Phillips, and Torng, 1994].

We consider the $\epsilon$-clairvoyant setting, where $\epsilon \in [0,1]$, and each job’s processing time becomes known once its remaining processing time equals an $\epsilon$ fraction of its processing time. This captures settings where the system user uses the initial $(1-\epsilon )$ fraction of a job’s processing time to learn its true length, which it can then reveal to the algorithm. The model was proposed by Yingchareonthawornchai and Torng (2017), and it smoothly interpolates between the clairvoyant setting (when $\epsilon =1$) and the non-clairvoyant setting (when $\epsilon =0$). In a concrete sense, we are asking: how much knowledge is required to circumvent the hardness of this problem?

We show that a little knowledge is enough, and that a constant competitive algorithm exists for every constant $\epsilon >0$. More precisely, for all $\epsilon \in (0,1)$, we present an deterministic $\lceil 1/\epsilon \rceil$-competitive algorithm, which is optimal for deterministic algorithms. We also present a matching lower bound (up to a constant factor) for randomized algorithms.

Our algorithm to achieve this bound is remarkably simple and applies the “optimism in the face of uncertainty” principle. For each job, we form an optimistic estimate of its length, based on the information revealed thus far and run SRPT on these optimistic estimates. The proof relies on maintaining a matching between the jobs in OPT’s queue and the algorithm’s queue, with small prefix expansion. We achieve this by by carefully choosing a set of jobs to arrive earlier than their release times without changing the algorithm, and possibly helping the adversary. These early arrivals allow us to maintain structural properties inductively, giving us the tight guarantee.

We propose new abstract problems that unify a collection of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider the weighted sum of completion times over groups of entities (jobs, vertices, or edges), which generalizes two important objectives in scheduling: makespan and sum of weighted completion times.

We study these problems in both online and offline settings. In the non-clairvoyant online setting, we give a novel $O(\log g)$-competitive algorithm, where $g$ is the size of the largest group. This is the first non-trivial competitive bound for many problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. Notably, this bound is asymptotically best-possible. For offline scheduling, we provide powerful meta-frameworks that lead to new or stronger approximation algorithms for our new abstract problems and for previously well-studied special cases. In particular, we improve the approximation ratio from $13.5$ to $10.874$ for non-preemptive related machine scheduling and from $4+\epsilon$ to $2+\epsilon$ for preemptive unrelated machine scheduling (MOR 2012), and we improve the approximation ratio for sum coloring problems from $10.874$ to $5.437$ for perfect graphs and from $11.273$ to $10.874$ for interval graphs (TALG 2008).

Adaptive submodularity is a fundamental concept in stochastic optimization, with numerous applications such as sensor placement, hypothesis identification and viral marketing. We consider the problem of covering an adaptive-submodular function at minimum expected cost, which generalizes the classic set cover and submodular cover problems to the stochastic setting. We show that the natural greedy policy has an approximation ratio of $4\cdot (1+\ln Q)$, where $Q$ is the goal value. In fact, we consider a significantly more general objective of minimizing the $p^{th}$ moment of the coverage cost, and show that the greedy policy simultaneously achieves a ${(p+1)}^{p+1}\cdot {(\ln Q+1)}^p$ approximation guarantee for all $p\ge 1$. All our approximation ratios are best possible up to constant factors (assuming $P\ne NP$). We also show that the greedy policy for minimizing expected cost has an approximation ratio at least $1.3\cdot (1+\ln Q)$ even when $Q=1$, which invalidates a prior result on adaptive submodular cover. Moreover, our results extend to the setting where one wants to cover multiple adaptive-submodular functions, for which we obtain the same approximation guarantees.

Phase change memory (PCM) is a promising memory technology known for its speed, high density, and durability. However, each PCM cell can endure only a limited number of erase and subsequent write operations before failing, and the failure of a single cell can limit the lifespan of the entire device. This vulnerability makes PCM particularly susceptible to adversarial attacks that induce excessive writes to accelerate device failure. To counter this, wear-leveling techniques aim to distribute write operations evenly across PCM cells.

In this paper we study the online PCM utilization problem, which seeks to maximize the number of write requests served before any cell reaches the erase limit. While extensively studied in the systems and architecture communities, this problem remains largely unexplored from a theoretical perspective. We bridge this gap by presenting a novel algorithm that leverages cell wear information to optimize PCM utilization. We prove that our algorithm achieves near-optimal worst-case guarantees and outperforms state-of-the-art practical solutions both theoretically and empirically, providing an efficient approach to prolonging PCM lifespan.

A common theme in stochastic optimization problems is that, theoretically, stochastic algorithms need to “know” relatively rich information about the underlying distributions. This is at odds with most applications, where distributions are rough predictions based on historical data. Thus, commonly, stochastic algorithms are making decisions using imperfect predicted distributions, while trying to optimize over some unknown true distributions.

We consider the fundamental problem of scheduling stochastic jobs preemptively on a single machine to minimize expected mean completion time in the setting where the scheduler is only given imperfect predicted job size distributions. If the predicted distributions are perfect, then it is known that this problem can be solved optimally by the Gittins index policy.

The goal of our work is to design a scheduling policy that is robust in the sense that it produces nearly optimal schedules even if there are modest discrepancies between the predicted distributions and the underlying real distributions. Our main contributions are:

• $\mathrm{■}$

  We show that the standard Gittins index policy is not robust in this sense. If the true distributions are perturbed by even an arbitrarily small amount, then running the Gittins index policy using the perturbed distributions can lead to an unbounded increase in mean completion time.

• $\mathrm{■}$

  We explain how to modify the Gittins index policy to make it robust, that is, to produce nearly optimal schedules, where the approximation depends on a new measure of error between the true and predicted distributions that we define.

Looking forward, the approach we develop here can be applied more broadly to many other stochastic optimization problems to better understand the impact of mispredictions, and lead to the development of new algorithms that are robust against such mispredictions.

Online convex paging models a broad class of cost functions for the classical paging problem. In particular, it naturally captures fairness constraints: e.g., that no specific page (or groups of pages) suffers an unfairly high number of evictions by considering ${\mathrm{\ell }}_p$ norms of eviction vectors for $p>1$. The case of the ${\mathrm{\ell }}_{\mathrm{\infty }}$ norm has also been of special interest, and is called min-max paging.

In this talk, I will discuss tight upper and lower bounds for the convex paging problem for a broad class of convex functions. Prior to our work, only fractional algorithms were known for this general setting. Moreover, our new results settle the competitive ratio for min-max paging and ${\mathrm{\ell }}_p$-norm paging for all values of $p>1$.

Santa Claus cannot accept that even a single child is unhappy on Christmas. Therefore, when he distributes his gifts, he maximizes the total value of gifts that the least happy child gets. This is a non-trivial task, especially when each gift $j$ has a different value $v_{ij}$ for each child $i$. This very natural problem, sometimes under the more serious name of max-min fair allocation, has seen significant attention in the last two decades. Yet, many questions about it remain widely open. We will survey developments on the problem using three different perspectives that demonstrate its versatile nature: First, we view it as a fair allocation problem, then as a scheduling problem, and finally as a network design problem.

We prove that there exists an online algorithm that for any sequence of vectors $v_1,\mathrm{\dots },v_T\in {ℝ}^n$ with ${\Vert v_i\Vert }_2\le 1$, arriving one at a time, decides random signs $x_1,\mathrm{\dots },x_T\in \{-1,1\}$ so that for every $t\le T$, the prefix sum ${\sum }_{i=1}^t{x}_i{v}_i$ is $O(1)$-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums $O(\sqrt{\log (nT)})$-subgaussian. Our proof combines a generalization of Banaszczyk’s prefix balancing result to trees with a cloning argument to find distributions rather than single colorings.

This paper addresses the problem of computing a scheduling policy that minimizes the total expected completion time of a set of $N$ jobs with stochastic processing times on $m$ parallel identical machines. When all processing times follow Bernoulli-type distributions, Gupta et al. (SODA ’23) exhibited approximation algorithms with an approximation guarantee $\tilde{\text{O}}(\sqrt{m})$, where $m$ is the number of machines and $\tilde{\text{O}}(\cdot )$ suppresses polylogarithmic factors in $N$, improving upon an earlier $\text{O}(m)$ approximation by Eberle et al. (OR Letters ’19) for a special case. The present paper shows that, quite unexpectedly, the problem with Bernoulli-type jobs admits a PTAS whenever the number of different job-size parameters is bounded by a constant. The result is based on a series of transformations of an optimal scheduling policy to a “stratified” policy that makes scheduling decisions at specific points in time only, while losing only a negligible factor in expected cost. An optimal stratified policy is computed using dynamic programming. Two technical issues are solved, namely (i) to ensure that, with at most a slight delay, the stratified policy has an information advantage over the optimal policy, allowing it to simulate its decisions, and (ii) to ensure that the delays do not accumulate, thus solving the trade-off between the complexity of the scheduling policy and its expected cost. Our results also imply a quasi-polynomial $\text{O}(\log N)$-approximation for the case with an arbitrary number of job sizes.

The ideal of proportional representation in social choice theory is easy to state yet challenging to formalize: any $\alpha$-fraction of the population should have a say in determining an $\alpha$-fraction of the outcome. This principle has gained significant attention in recent years and is arguably the most studied fairness notion in social choice theory today.

This talk explores proportional representation in the context of budget allocation—a broad framework capturing various models with wide-ranging applications, including apportionment, participatory budgeting, and committee elections. We will examine several formalizations of proportionality, introduce algorithms designed to achieve proportional outcomes, and highlight key open questions in the field. Beyond that, I hope to inspire discussion on how proportional representation might be relevant in settings beyond social choice theory.

Graph Burning models information spreading in a given graph as a process such that in each step one node is infected (informed) and also the infection spreads to all neighbors of previously infected nodes. Formally, given a graph $G=(V,E)$, possibly with edge lengths, the burning number $b(G)$ is the minimum number $g$ such that there exist nodes $v_0,\mathrm{\dots },v_{g-1}\in V$ satisfying the property that for each $u\in V$ there exists $i\in \{0,\mathrm{\dots },g-1\}$ so that the distance between $u$ and $v_i$ is at most $i$.

We present a simple deterministic $2.314$-approximation algorithm for computing the burning number of a general graph, even with arbitrary edge lengths. This complements our previous more complicated randomized algorithm with the same approximation ratio.

We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph $G$ with $n$ nodes according to an adaptive adversary. Our goal is to maintain an orientation $H$ of $G$ that keeps the discrepancy, defined as ${\max }_{v\in V}|{\mathrm{deg}}_H^{+}(v)--{\mathrm{deg}}_H^{-}(v)|$, small at all times.

We present a simple algorithm and analysis for this problem with recourse based on cycles that simplifies and improves on a result of Gupta et al. [SODA ’22].

Given an election of n voters with preference lists over m candidates, Elkind, Lang, and Saffidine (2011) defined a Condocet winning set to be a collection of candidates that the majority of voters prefer over any individual candidate. Condocet winning sets of cardinality one (a Condorcet winner) or cardinality two need not exist. We prove however that a Condocet winning set of cardinality at most six exists in any election.

In the Dynamic Bin Packing problem, $n$ items arrive and depart the system in an online manner, and the goal is to maintain a good packing throughout. We consider the objective of minimizing the total active time, i.e., the sum of the number of open bins over all times. An important tool for maintaining an efficient packing in many applications is the use of migrations; e.g., transferring computing jobs across different machines. However, there are large gaps in our understanding of the approximability of dynamic bin packing with migrations. Prior work has covered the power of no migrations and $>n$ migrations, but we ask the question: What is the power of limited ($\le n$) migrations?

Our first result is a dichotomy between no migrations and linear migrations: Using a sublinear number of migrations is asymptotically equivalent to doing zero migrations, where the competitive ratio grows with $\mu$, the ratio of the largest to smallest item duration. On the other hand, we prove that for every $\alpha \in (0,1]$, there is an algorithm that does $\approx \alpha n$ migrations and achieves competitive ratio $\approx 1/\alpha$ (in particular, independent of $\mu$); we also show that this tradeoff is essentially best possible. This fills in the gap between zero migrations and $>n$ migrations in Dynamic Bin Packing.

Finally, in light of the above impossibility results, we introduce a new model that more directly captures the impact of migrations. Instead of limiting the number of migrations, each migration adds a delay of $C$ time units to the item’s duration; this commonly appears in settings where a blackout or set-up time is required before the item can restart its execution in the new bin. In this new model, we prove a $O(\min (\sqrt{C},\mu ))$-approximation, and an almost matching lower bound. We also present preliminary experiments that indicate that our theoretical results are predictive of the practical performance of our algorithms.