-
Department Info
-
-
Admissions
-
-
Academics
-
-
-
Research
-
-
-
Main navigation | Main content
Wednesday, September 26, 2012
| Presenter: | Barna Saha |
|---|---|
| Affiliation: | |
| Time: | 13:30 - 14:30 |
| Location: | Keller Hall 5-212 |
| Host: | Volkan Isler |
| Schedule: | View Extended Schedule Details |
Resource allocation problems refer to the distribution of scarce resources among competing agents maintaining certain optimization criteria. They are ubiquitous in computer science and appear in many flavors. Examples include scheduling jobs on limited number of machines maintaining system performance, finding assignment of advertisements to few available slots to maximize profits, distributing items to persons to ensure social fairness, allocating servers or channels satisfying networking requirements etc. Majority of these problems are NP-hard in nature and therefore, the goal herein is to develop efficient polynomial time algorithms that approximate the optimal solution as best as possible.
In this talk, I will present a new linear programming rounding technique based on random walks in polytope that leads to improved approximation algorithms and integrality gaps for several resource allocation problems. I will emphasize on the generality of this approach with an overview of its varied applications. Finally, I will elaborate on two specific applications, namely, designing algorithms for energy efficient scheduling and the generalized assignment problem.
Barna Saha is a Senior Member of Research at the AT&T Shannon Laboratories. She obtained her Ph.D. in Computer Science from University of Maryland College Park in 2011. Her Research interest spans the areas of theoretical computer science and database management system, such as design and analysis of algorithms, probabilistic methods, graph theory and big data analysis. She is the co-winner of the best paper award in VLDB 2009, one of the premier conferences in databases, for her work on probabilistic ranking algorithms. She is also the recipient of Deans Fellowship Award, University of Maryland, 2010, for her dissertation research.
