you're reading...

SACT Seminar: Fair Resource Allocation for Heterogeneous Tasks

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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: