Online Decision Making via Prophet Setting

dc.contributor.advisorHajiaghayi, MohammadTaghien_US
dc.contributor.authorEhsani Banafati, Soheilen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2018-01-23T06:44:42Z
dc.date.available2018-01-23T06:44:42Z
dc.date.issued2017en_US
dc.description.abstractIn the study of online problems, it is often assumed that there exists an adversary who acts against the algorithm and generates the most challenging input for it. This worst-case assumption in addition to the complete uncertainty about future events in the traditional online setting sometimes leads to worst-case scenarios with super-constant approximation impossibilities. In this dissertation, we go beyond this worst-case analysis of problems by taking advantage of stochastic modeling. Inspired by the prophet inequality problem, we introduce the prophet setting for online problems in which the probability distributions of the future inputs are available. This modeling not only considers the availability of statistical data in the design of mechanisms but also results in significantly more efficient algorithms. To illustrate the improvements achieved by this setting, we study online problems within the contexts of auctions and networks. We begin our study with analyzing a fundamental online problem in optimal stopping theory, namely prophet inequality, in the special cases of iid and large markets, and general cases of matroids and combinatorial auctions and discuss its applications in mechanism design. The stochastic model introduced by this problem has received a lot of attention recently in modeling other real-life scenarios, such as online advertisement, because of the growing ability to fit distributions for user demands. We apply this model to network design problems with a wide range of applications from social networks to power grids and communication networks. In this dissertation, we give efficient algorithms for fundamental network design problems in the prophet setting and present a general framework that demonstrates how to develop algorithms for other problems in this setting.en_US
dc.identifierhttps://doi.org/10.13016/M22F7JS7Q
dc.identifier.urihttp://hdl.handle.net/1903/20387
dc.language.isoenen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledApproximation Algorithmsen_US
dc.subject.pquncontrolledNetwork Modelingen_US
dc.subject.pquncontrolledOnline Decision Makingen_US
dc.subject.pquncontrolledProphet Inequalityen_US
dc.subject.pquncontrolledSecretary Problemen_US
dc.subject.pquncontrolledStochastic Modelingen_US
dc.titleOnline Decision Making via Prophet Settingen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
EhsaniBanafati_umd_0117E_18632.pdf
Size:
2.32 MB
Format:
Adobe Portable Document Format