Algorithmic Solutions for Interval and Rectangle Scheduling: Fairness, Prediction, and Beyond

Abstract

In the interval scheduling problem, the input is a set of intervals with integer endpoints, and the objective is to accept a maximum number of non-overlapping intervals. In the two-dimensional variant, namely rectangle scheduling, the input consists of a set of rectangles, and the goal is to select a maximum number of non-overlapping rectangles. One may consider these problems in both online and offline settings. In the offline setting, the input set is available at the beginning, and an algorithm makes a decision about selecting an interval (or rectangle) with complete information about the input. In the online setting, however, the input appears sequentially, and an online algorithm must accept an interval (or a rectangle) upon its arrival without any information about forthcoming intervals (or rectangles). The decisions of an algorithm for accepting/rejecting an item in its selected set are final and irrevocable. Online interval scheduling has received considerable attention in the past few decades, and various algorithmic solutions have been proposed under different settings and models. In comparison, two-dimensional variants of the problem have been less studied. In this thesis, we study the online rectangle scheduling problems under the any-order arrival setting. Previous work on this topic has been limited to random-order arrival (where rectangles are generated in parallel, but their ordering is random) or under restrictions like square scheduling. In comparison, we study the worst-case performance of online algorithms in the most generic setting of the problem and establish the tight upper and lower bounds of Theta((log T)^2) on the competitive ratio of the best online algorithms. Here, T is a parameter that defines the maximum length of intervals. Furthermore, we consider an online rectangle scheduling setting where (possibly erroneous) predictions are provided to the online algorithm. Here, predictions specify the presence or absence of rectangles in the input. Under this setting, we study an algorithm whose competitive ratio depends explicitly on the prediction error. In particular, our algorithm performs optimally when the predictions are perfect, and its performance degrades as the error increases. To make this algorithm robust against adversarial predictions (where error is large), we also propose a hybrid approach that combines it with a purely online algorithm and prove that this combined approach allows a trade-off between "consistency" and "robustness", which define the performance in scenarios where predictions are perfect and adversarial, respectively. In addition, we initiate the study of the fairness aspects of the interval scheduling problem, where each interval belongs to a group, and the objective is to achieve a notion of fairness in which a "fair" number of intervals from each group are accepted. We study this problem under both absolute and asymptotic settings. In the asymptotic setting, the number of intervals in optimal solutions for each group is arbitrarily large, whereas this assumption is absent in the absolute setting. For each of these two settings, we study the power of offline and online algorithms, as well as deterministic and randomized algorithms.