Show simple item record

dc.contributor.authorTripathi, Pushkaren_US
dc.date.accessioned2012-09-20T18:19:25Z
dc.date.available2012-09-20T18:19:25Z
dc.date.issued2012-06-28en_US
dc.identifier.urihttp://hdl.handle.net/1853/44789
dc.description.abstractAllocation problems have been central to the development of the theory of algorithms and also find applications in several realms of computer science and economics. In this thesis we initiate a systematic study of these problems in situations with limited information. Towards this end we explore several modes by which data may be obfuscated from the algorithm. We begin by investigating temporal constraints where data is revealed to the algorithm over time. Concretely, we consider the online bipartite matching problem in the unknown distribution model and present the first algorithm that breaches the 1-1/e barrier for this problem. Next we study issues arising from data acquisition costs that are prevalent in ad-systems and kidney exchanges. Motivated by these constraints we introduce the query-commit model and present constant factor algorithms for the maximum matching and the adwords problem in this model. Finally we assess the approximability of several classical allocation problems with multiple agents having complex non-linear cost functions. This presents an additional obstacle since the support for the cost functions may be extremely large entailing oracle access. We show tight information theoretic lower bounds for the general class of submodular functions and also extend these results to get lower bounds for a subclass of succinctly representable non-linear cost functions.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectApproximation algorithmsen_US
dc.subjectAllocation problemsen_US
dc.subjectOptimizationen_US
dc.subjectOnline algorithmsen_US
dc.subjectMatchingen_US
dc.subject.lcshAlgorithms
dc.titleAllocation problems with partial informationen_US
dc.typeDissertationen_US
dc.description.degreePhDen_US
dc.contributor.departmentComputingen_US
dc.description.advisorCommittee Chair: Vijay Vazirani; Committee Member: Nina Balcan; Committee Member: Ozlem Ergun; Committee Member: Prasad Tetali; Committee Member: Shabbir Ahmeden_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record