Algorithms for Allocation Problems in Online Settings
A fundamental computational challenge that arises in the operation of online systems, services, and platforms is that of resource allocation. Broadly defined, a resource allocation problem is one where a set of users generate demands, which then have to be satisfied using a limited set of resources. In many of these scenarios, demands arrive in an online sequence, meaning they arrive over time and must be irrevocably satisfied or assigned without knowledge of future requests.
In this thesis, we examine resource allocation problems in online settings, focusing on problems in data-center scheduling and internet advertising. Our results are summarized as follows.
-Vector Scheduling: We resolve the complexity of the vector scheduling problem, a variant of the classic load balancing problem first considered by Graham, where jobs have vectors loads (as opposed to a single scalar). We study the problem in the three classical settings---identical, unrelated, and related---giving competitive algorithms for optimizing generic q-norms of the machines loads as well as asymptotically matching lower bounds. Also as a consequence of these results, we give the first constant competitive algorithm for optimizing q-norms on related machines in the scalar setting.
-Budgeted Allocation: We study a variant of the online budgeted allocation (also called Adwords) problem where advertising budgets are expressed over multiple tiers of user-attribute granularity. We show that, unlike in the single-budget Adwords problem, obtaining a constant competitive ratio is impossible and give asymptotically tight upper and lower bounds. However, we then observe that in many real-world scenarios, multi-tier budgets would likely have a laminar structure. In the laminar setting, we obtain a competitive ratio of e/(e-1) in the small bids case, which matches the best known Adwords result for single budgets.