Optimal stopping problems and combinatorial optimization under uncertainty

Livanos, Vasileios

Permalink

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

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

Copyright and License Information

Copyright 2024 Vasilis Livanos

Owning Collections