Time: 2:00pm Wednesday, 12th August.
Location: SIT 459
Speaker: Koyel Mukherjee.
Title: Fair Resource Allocation for Heterogeneous TasksAbstract: We consider the problem of fair resource allocation for tasks in a heterogeneous system, where resources may have different sizes and costs, and tasks may have different resource demands. Due to the heterogeneity, the cost of allocating a task in isolation, when other competing task are absent, may differ significantly from its allocation cost when the task is allocated along with other tasks. In this context, we consider the problem of fairly allocating resources to all tasks, such that the allocation cost incurred by any task is not very high compared to the cost incurred by it in isolation. Such a fair resource allocation problem arises in various contexts, such as, allocating computing resources for reservations requests from tenants in a data center, allocating resources to computing tasks in grid computing, or allocating personnel for tasks in service delivery organizations. We show that this problem is strongly NP-Hard even when the resources are of unit size by a reduction from 3-partition. We give a 2 +O(epsilon) approximate algorithm based on LP rounding for unit size resources and a near-optimal greedy algorithm for a more restricted version.
(this work appeared in IPDPS 2015)
Speaker Bio: Koyel Mukherjee is a Research Scientist with Xerox Research Center India since January, 2014. Prior to this, she completed her Ph.D. in Computer Science from the University of Maryland, College Park in December, 2013. Her research interests are in design and analysis of approximation algorithms, with a focus on scheduling and resource allocation problems. In Xerox, she is primarily working on problems related to transportation, specifically, on demand based scheduling and routing public and private modes of transportation for improving performance metrics. She is also interested in algorithmic game theory and explore-exploit mechanisms.