Back to search

Georgia Institute of Technology

Allocation problems with partial information

Abstract

dc:description.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 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.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tripathi, Pushkar
Advisor dc:contributor.advisor
  • Vazirani, Vijay V.
Committee members dc:contributor.committeemember
  • Balcan, Nina
  • Ergun, Ozlem
  • Tetali, Prasad
  • Ahmed, Shabbir

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/44789

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Tripathi, Pushkar. Allocation problems with partial information. Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44789