Show simple item record

dc.contributor.authorHou, Ashley Mimi
dc.date.accessioned2020-01-16T21:12:02Z
dc.date.available2020-01-16T21:12:02Z
dc.date.issued2019
dc.identifier.urihttp://digital.library.wisc.edu/1793/79591
dc.description.abstractWe consider at the problem of optimal budget allocation, where we are given a fixed budget to distribute amongst sources in order to maximally influence targeted individuals. In practice, situations may arise where the influence process is unknown to us, motivating us to look at the robust budget allocation problem. In this setting, influence functions, which capture the expected number of influenced targets, are known only up to an uncertainty set and the goal is to find an allocation that maximizes the worst-case influence function. We extend the results of previous work on the related problem of robust submodular maximization to the integer lattice domain, formulating a polynomial-time algorithm approximation algorithm, SaturateDR. We prove hardness of approximation results for both the robust budget allocation problem as well as the bi-criteria approximation obtained by SaturateDR. Finally, we present experimental results that demonstrate our robust solution performs favorably in comparison to non-robust methods, with respect to influence obtained as well as runtime.en_US
dc.language.isoen_USen_US
dc.titleRobust Budget Allocationen_US
dc.typeThesisen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record