University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Online Decision Making via Prophet Setting

    Thumbnail
    View/Open
    EhsaniBanafati_umd_0117E_18632.pdf (2.317Mb)
    No. of downloads: 212

    Date
    2017
    Author
    Ehsani Banafati, Soheil
    Advisor
    Hajiaghayi, MohammadTaghi
    DRUM DOI
    https://doi.org/10.13016/M22F7JS7Q
    Metadata
    Show full item record
    Abstract
    In 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.
    URI
    http://hdl.handle.net/1903/20387
    Collections
    • Computer Science Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility