We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its right, and the packet arrives at the next router one time step later. Packets are forwarded until they reach their destination. The flow time of a packet is the elapsed time between its release and its arrival at its destination. The goal is to minimize the maximum flow time. This problem was introduced by Antoniadis et al. in 2014, with a focus on line networks. They proposed several natural algorithms. For one, they proved that it is not O(1)-competitive; for others, they claimed analogous lower bounds, seemingly leaving no natural candidate for an O(1)-competitive algorithm. In this paper, we study a natural algorithm not considered in that work. Our algorithm, simply called Greedy, selects packets according to their projected flow time under the assumption that they are not delayed any further. We focus on the special case in which each packet needs to be forwarded by one or two routers; this case captures core difficulties. We show that Greedy achieves a competitive ratio of exactly 2-2^{1-k}, where k is the number of active routers in the network. We also give the first nontrivial general lower bound, which applies even to randomized algorithms: using the same type of instances as in our lower bound for Greedy, we show that no algorithm can be (4/3-ε)-competitive for any ε > 0.

We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: points with non-negative weights arrive online, and an algorithm can match an arriving point to one of the unmatched previously arrived points. In the classic model, the decision on how to match (if at all) a newly arriving point is irrevocable. The goal is to maximize the total weight of matched points under the constraint that straight-line segments corresponding to the edges of the matching do not intersect. The unweighted version of the problem was introduced in the offline setting by Atallah in 1985, and this problem became a subject of study in the online setting with and without advice in several recent papers. We observe that deterministic online algorithms cannot guarantee a non-trivial competitive ratio for the weighted problem, but we give upper and lower bounds on the problem with bounded weights. In contrast to the deterministic case, we show that using randomization, a constant competitive ratio is possible for arbitrary weights. We also study other variants of the problem, including revocability and collinear points, both of which permit non-trivial online algorithms, and we give upper and lower bounds for the attainable competitive ratios. Finally, we prove an advice complexity bound for obtaining optimality, improving the best known bound.

In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests, each consisting of pairs of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. We study a setting with a potentially erroneous prediction specifying the set of requests forming the input sequence and provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. We also present asymptotically tight trade-offs between consistency (competitive ratio with error-free predictions) and robustness (competitive ratio with adversarial predictions) of interval scheduling algorithms. Finally, we provide experimental results on real-world scheduling workloads that confirm our theoretical analysis.

Abstract With the developments in machine learning, there has been a surge in interest and results focused on algorithms utilizing predictions, not least in online algorithms where most new results incorporate the prediction aspect for concrete online problems. While the structural computational hardness of problems with regards to time and space is quite well developed, not much is known about online problems where time and space resources are typically not in focus. Some information-theoretical insights were gained when researchers considered online algorithms with oracle advice, but predictions of uncertain quality is a very different matter. We initiate the development of a complexity theory for online problems with predictions, considering minimization problems and one prediction bit per request. Based on the most generic hard online problem type, string guessing, we define a family of hierarchies of complexity classes (indexed by pairs of error measures) and develop notions of reductions, class membership, hardness, and completeness. Our framework contains all the tools one expects to find when working with complexity, and we illustrate our tools by analyzing problems with different characteristics. In addition, we show that known lower bounds for paging with discard predictions apply directly to all hard problems for each class in the hierarchy based on the canonical pair of error measures. This paging problem is not complete for these classes. Our work also implies corresponding complexity classes for classic online problems without predictions, with the corresponding complete problems.

We initiate the study of distributed graph algorithms with predictions in synchronous message passing systems. Each node in the graph is given a prediction, which is some extra information about the problem instance that may be incorrect. The better the prediction, the fewer rounds the algorithm should perform. We present a framework for evaluating distributed graph algorithms with predictions and some methods for transforming existing algorithms without predictions to effectively use predictions. Our approach is illustrated using the Maximal Independent Set problem.

Abstract A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio $$r=\frac{a}{\hat{a}}$$ r = a a ^ where a is the actual value for this average size and $$\hat{a}$$ a ^ is the prediction. We give an algorithm which is $$\frac{e-1}{e}$$ e - 1 e -competitive, if $$r=1$$ r = 1 , and this is best possible among online algorithms knowing a and nothing else. More generally, the algorithm has a competitive ratio of $$\frac{e-1}{e}r$$ e - 1 e r , if $$r \le 1$$ r ≤ 1 , and $$\frac{e-r}{e}r$$ e - r e r , if $$1 \le r < e$$ 1 ≤ r < e . Any algorithm with a better competitive ratio for some $$r<1$$ r < 1 will have a worse competitive ratio for some $$r>1$$ r > 1 . To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of $$\frac{1}{2r}$$ 1 2 r for $$r\ge 1$$ r ≥ 1 and $$\frac{r}{2}$$ r 2 for $$r\le 1$$ r ≤ 1 . We show that improving the result for any $$r< 1$$ r < 1 leads to a worse result for some $$r>1$$ r > 1 .

The priority model was introduced to capture “greedy-like” algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.

Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We develop algorithms satisfy all three desirable properties of learning-augmented algorithms – that is, they are consistent, robust and smooth – despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.

This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithm’s disadvantage.

We consider the problem of finding cheapest flight routes through free route airspaces in a 2D setting. We subdivide the airspace into regions determined by a Voronoi subdivision around the points from a weather forecast. This gives rise to a regular grid of rectangular regions (quads) with every quad having an associated vector-weight that represents the wind magnitude and direction. Finding a cheapest path in this setting corresponds to finding a piece-wise linear path determined by points on the boundaries of the quads. In our solution approach, we discretize such boundaries by introducing border points and only consider segments connecting border points belonging to the same quad. While classic shortest path graph algorithms are available and applicable to the graphs originating from these border points, we design an algorithm that exploits the geometric structure of our scenario and show that this algorithm is more efficient in practice than classic graph-based algorithms. In particular, it scales better with the number of quads in the subdivision of the airspace, making it possible to find more accurate routes or to solve larger problems.

Flight routes are paths calculated on a network of waypoints representing 3D-coordinates. A common approach is first to calculate a path in a 2D-network, taking into account feasibility constraints, and then to optimize the altitude of the flight.

We consider the online bin packing problem under the advice complexity model where the "online constraint" is relaxed and an algorithm receives partial information about the future requests. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with log(n)+o(log(n)) bits of advice, achieves a competitive ratio of 3/2 for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives 2n+o(n) bits of advice and achieves a competitive ratio of 4/3+e. Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.

Data structures with relaxed balance differ from standard structures in that rebalancing can be delayed and interspersed with updates. This gives extra flexibility in both sequential and parallel applications. We study the version of multi-way trees called (a,b)-trees (which includes B-trees) with the operations insertion, deletion, and group insertion. The latter has applications in for instance document databases, WWW search engines, and differential indexing. We prove that we obtain the optimal asymptotic rebalancing complexities of amortized constant time for insertion and deletion and amortized logarithmic time in the size of the group for group insertion. These results hold even for the relaxed version. This is an improvement over the existing results in the most interesting cases.

A new measure, the accommodating function, for the quality of on-line algorithms is presented. The accommodating function, which is a generalization of both the competitive ratio and the competitive ratio on accommodating sequences, measures the quality of an on-line algorithm as a function of the resources that would be sufficient for an optimal off-line algorithm to fully grant all requests. More precisely, if we have some amount of resources n, the function value at $\alpha$ is the usual ratio (still on some fixed amount of resources n), except that input sequences are restricted to those where the optimal off-line algorithm will not obtain a better result by having more than the amount $\alpha n$ of resources. The accommodating functions for three specific on-line problems are investigated: a variant of bin packing in which the goal is to maximize the number of items put in n bins, the seat reservation problem, and the problem of optimizing total flow time when preemption is allowed. We also show that when trying to distinguish between two algorithms, the decision as to which one performs better cannot necessarily be made from the competitive ratio or the competitive ratio on accommodating sequences alone. For the variant of bin-packing considered, we show that Worst-Fit has a strictly better competitive ratio than First-Fit, while First-Fit has a strictly better competitive ratio on accommodating sequences than Worst-Fit.