Petety, A. (CSE) – New Algorithmic Methods for Uncertain Inputs

This dissertation focuses on designing and proving performance guarantees on algorithms when there is uncertainty in the input. The uncertainty could be from the user being unsure or future inputs that have not arrived yet. We look at different methods in which algorithms can be designed to be competitive against the optimal. One of the assumptions that helps in this is to assume that the input arrival order is completely random. We study the online load/graph balancing problem when the input arrival order is uniformly random. We show lower bounds for the greedy algorithm and the general case. In the next part, we study the online scheduling problem under the assumption that the online algorithm has an additional ϵ speed compared to the machines in offline optimal. We show a meta algorithm generalizing Shortest Remaining Processing Time that gives a scalable algorithm for minimizing total weighted flow time. We show that it achieves scalability for minimizing total weighted flow time when the residual optimum exhibits supermodularity. In the final part we look at the online caching problem when the algorithm has access to ML-augmented predictions. We propose an algorithm that achieves a O(logb k) competitive ratio even when using just b predictions per cache miss. We also prove its robustness and consistency.

Event Host: Aditya Petety, Ph.D. Student, Computer Science and Engineering

Advisor: Sungjin Im