PhD Proposal: Economics of Assignment Problems

Assignment problems are fundamental combinatorial optimization problems. In high level, an assignment problem is the problem of assigning some jobs (or goods) to some agents in the "bast" way. Indeed, an assignment problem consist of two parts, an underlying structure which indicate feasible assignments and an objective function to mature how "good" an assignment is. Assignment problems attract many researchers in computer science, optimization, operations research and mathematics. However, most of the works are based on the classical model, where we have direct access to the whole information and aim to find an optimum solution.
In the recent decade, real word applications such as online advertisements, online marketing and large networks raised up many new challenges in this domain. The real world circumstances such as lack of information, dealing with real agents or dealing with extremely large graphs, makes classical algorithm inefficient or inappropriate.
In this proposal we discuss about some recent challenges in assignment problems, and present state of the art and our current results on them. In fact, these problems and models are some samples of assignment problems.
There are lots of other well motivated and hot challenges that fit in this interesting domain of problems. Since all of these problems deals with the same structure, studying each of them leads us to a better understanding of assignment problems and empowers us with some tools to attack other problems in this context. Defiantly, considering these problems will have a large positive effect on both theory and application sides of computer science.
Examining Committee:
Committee Chair: - Dr. Mohammad Taghi Hajiaghayi
Dept's Representative - Dr. V.S. Subrahmanian
Committee Member(s): - Dr. Vahab S. Mirrokni