*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Allocation Problems with Partial Information
Pushkar Tripathi
Algorithms, Combinatorics, and Optimization College of Computing Georgia Institute of Technology
Date: Friday, May 25th, 2012
Time: 3:30 pm EDT
Location: Skiles 005
Committee:
Abstract:
Allocation 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 a 0.56 factor randomized algorithm for the maximum matching problem in this model. Our algorithm is a variant of the greedy algorithm and uses correlated randomness to attain a factor better than 0.5. We also study the maximum matching, and the adwords problem in a stochastic variant of this model and present constant factor algorithms.
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.
