University of Illinois Urbana-Champaign

Optimal stopping problems and combinatorial optimization under uncertainty

Livanos, Vasileios

Content Files
LIVANOS-DISSERTATION-2024.pdf

Permalink

https://hdl.handle.net/2142/124363

Description

Title
Optimal stopping problems and combinatorial optimization under uncertainty
Author(s)
Livanos, Vasileios
Issue Date
2024-04-23
Director of Research (if dissertation) or Advisor (if thesis)
  • Mehta, Ruta
  • Chekuri, Chandra
Doctoral Committee Chair(s)
Mehta, Ruta
Committee Member(s)
  • Har-Peled, Sariel
  • Singla, Sahil
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • prophet inequalities
  • contention resolution schemes
  • online selection
  • combinatorial optimization
  • extreme value theory
Abstract
This thesis studies optimal stopping and combinatorial optimization problems in an uncertain environment. Optimal stopping captures many natural scenarios in which decisions have to be made without knowledge of the future and cannot be amended later on. In combinatorial optimization settings the objective is to optimize a function over distinct elements subject to certain feasibility constraints. Combinatorial optimization has been classically studied in the full-information setting where the entire input is known a priori. Combining combinatorial optimization with an uncertain environment leads to settings in which algorithms have only partial knowledge of the input, which is revealed element-by-element and all decisions of an algorithm have to be immediate and irrevocable. Such settings of optimization under uncertainty arise naturally in applications in which knowledge of the future cannot be obtained, either inherently or due to prohibiting costs or noise. In this thesis we focus on two settings. The first is a classical model in optimal stopping theory, the prophet inequality, in which an algorithm has to pick one of many random variables whose realizations are observed sequentially and compares against a prophet who knows all realizations in advance. The second setting is rounding a solution to a linear program in an online manner via the use of an Online Contention Resolution Scheme (OCRS) which is very useful in settings of combinatorial optimization under uncertainty. We initiate the study of prophet inequalities for independent and identically distributed (I.I.D.) random variables for cost minimization, showing distribution-dependent constant-factor guarantees for the competitive ratio that are qualitatively different from the maximization setting. In addition, we unify the maximization and minimization I.I.D. prophet inequalities via the theory of extreme values and show that the competitive ratio of both settings is governed by a single function that depends only on the extreme value index. We also obtain similar results for the objective of competition complexity, which captures how many more random variables an algorithm needs to observe in order to beat the prophet. We then ask how our guarantees change if we allow our algorithms the ability to ask simple questions to an oracle that has knowledge of the future. Motivating this, we establish an equivalence between this setting and the top-1-of-m setting in which the algorithm can select m values but is judged only for the best one among them. For the oracle-augmented model, we obtain guarantees on the competitive ratio and the probability of selecting the maximum realization that are almost tight asymptotically with respect to the number of oracle calls, for both the I.I.D. case and the case of non-identical random variables whose arrival order is controlled by an adversary. Afterwards, we turn to more general combinatorial optimization settings where multiple elements can be selected. We design optimal greedy OCRSs for special cases of matroids and provide matching upper bounds to show their optimality. We then use greedy OCRSs to obtain algorithms with significantly improved guarantees on the competitive ratio for prophet inequalities with a submodular objective function under several combinatorial feasibility constraints such as matroids, matchings and knapsacks.
Graduation Semester
2024-05
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/124363
Copyright and License Information
Copyright 2024 Vasilis Livanos

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois