Computer Science

CS Colloquium Seminar: Dr. Sungjin Im from UC Merced

Title: Competitive Scheduling Algorithms from Competitive Equilibria

Host: Dave Doty

When: Thursday, January 12th, 2017, at 3:10pm
Where: 1131 Kemper Hall


Scheduling jobs is a fundamental problem that arises in numerous forms and in various situations. In this talk, we introduce and study a general scheduling problem that we term the Packing Scheduling Problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates at which a scheduler can process jobs are subject to arbitrary packing constraints. We show that the PSP framework captures a variety of scheduling problems, including the classical problems of heterogeneous machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from multi-core computer architectures to data centers. More concretely, PSP models multidimensional resource and network bandwidth requirements arising in scheduling jobs on shared clusters. We design online algorithms for PSP that are constant competitive for minimizing the standard QoS metrics of total weighted completion time and total delay. Surprisingly, we achieve these results by applying the well-known Proportional Fairness algorithm from economics literature to allocate resources each time instant. Proportional Fairness has been extensively studied in the context of maximizing fairness in resource allocation; however, we present the first unifying analyses in the context of optimizing job latency in scheduling contexts. Our results yield the first constant competitive algorithms for the completion times and delay metrics for several classical scheduling problems.
Joint work with Janardhan Kulkarni (Microsoft Research) and Kamesh Munagala (Duke University), which appeared in STOC 2014 and FOCS 2015.



Sungjin Im is currently an assistant professor at University of California, Merced. He obtained his BS and MS in computer science at Seoul National University in 2002 and 2004, respectively. He received his PhD in computer science from the University of Illinois at Urbana-Champaign in 2012. He was a postdoctoral associate at Duke University until 2013. His PhD study was mainly supported by the Samsung Fellowship. His work on broadcast scheduling won the Best Student Paper Award at the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010. His main research interests are in design and analysis of algorithms and their applications, particularly in approximation algorithms, online algorithms, scheduling algorithms, and big data algorithms.

1131 Kemper Hall

Loading Map....