Sungjin Im

Research Interests:

Design and analysis of algorithms and their applications; approximation algorithms, online algorithms, combinatorial optimization, scheduling algorithms, game theory, inapproximability

Education:

• Ph.D. in Computer Science, Univ. of Illinois at Urbana Champaign, Fall 2006~Spring 2012 (expected)
• M.S. in Computer Science and Engineering, Seoul National Univ., Feb 2004
• B.S. in Computer Science and Engineering, Seoul National Univ. (Summa Cum Laude), Feb 2002
• Diploma, Seoul Science High School, Feb 1998

Publications (recent):

1. Minimum Latency Submodular Cover
   with Viswanath Nagarajan and Ruben Van Der Zwaan
   Manuscript

2. Preemptive and Non-preemptive Generalized Min Sum Set Cover
   with Maxim Sviridenko and Ruben Van Der Zwaan
   Symposium on Theoretical Aspects of Computer Science, STACS '12
   

3. Online Scheduling with General Cost Functions
   with Benjamin Moseley and Kirk Pruhs
   23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12
   

4. Scheduling Heterogeneous Processors Isn't As Easy As You Think
   with Anupam Gaupta, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs
   23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12
   

5. Signature Pattern Covering via Local Greedy Algorithm and Pattern Shrink
   Hyungsul Kim, David Sheridan, Sungjin Im, Shobha Vasudevan, Tarek Abdelzaher and Jiawei Han
   IEEE International Conference on Data Mining, ICDM '11
   

6. Fast Clustering using MapReduce
   with Alina Ene and Benjamin Moseley
   17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '11
   

7. A Tutorial on Amortized Local Competitiveness in Online Scheduling
   with Benjamin Moseley and Kirk Pruhs
   ACM SIGACT NEWS (June 2011)
   

8. Secretary Problems: Laminar Matroid and Interval Scheduling
   with Yajun Wang
   22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11
   

9. Online Scalable Scheduling for the \ell_k-norms of Flow Time Without Conservation of Work
   with Jeff Edmonds and Benjamin Moseley
   22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11
   

10. An Online Scalable Algorithm for Minimizing \ell_k-norms of Weighted Flow Time on Unrelated Machines
    with Benjamin Moseley
    22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11
    

11. Envy-free Pricing with General Supply Constraints (short paper)
    with Pinyan Lu and Yajun Wang
    6th Workshop on Internet and Network Economics, WINE '10
    

12. New Models and Algorithms for Throughput Maximization in Broadcast Scheduling
    with Chandra Chekuri, Avigdor Gal, Samir Khuller, Jian Li, Richard McCutchen, Benjamin Moseley and Louiqa Raschid
    8th Workshop on Approximation and Online Algorithms, WAOA '10
    

13. Scheduling Jobs with Varying Parallelizability to Reduce Variance
    with Anupam Gupta, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs
    22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '10
    

14. An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling
    Best Student Paper Award
    with Benjamin Moseley
    21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10
    

15. Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
    with Chandra Chekuri and Benjamin Moseley
    17th Annual European Symposium on Algorithms, ESA '09
    

16. Longest Wait First For Broadcast Scheduling
    with Chandra Chekuri and Benjamin Moseley
    7th Workshop on Approximation and Online Algorithms, WAOA '09
    

Research and Working Experience (recent):

• IBM T. J. Watson Research Center, Yorktown Heights, NY USA
  Summer Internship, Mentor: Dr. Viswanath Nagarajan, Summer 2011
  

• Microsoft Research Asia, Beijing, China
  Summer Internship, Supervisor: Dr. Wei Chen and Dr. Yajun Wang, Summer 2010
  

• University of Pittsburgh, Pittsburgh, PA
  Visiting Researcher, Host: Prof. Kirk Pruhs, Nov 2009, Dec 2010, Apr 2011
  

Honors & Awards (selected):

• Feng Chen Memorial Award, UIUC, 2011
• Best Student Paper Award, SODA 2010
• Samsung Fellowship for Ph.D., 2006
• Scholarship for grads, Korea Foundation for Advanced Studies, 2002, 2003
• Scholarship for undergrads, Korea Foundation for Advanced Studies, 2000, 2001
• Gold Medal, Korea High School Math Competition, 1997
• Gold Medal, Korea Math Olympiad, 1996, 1997
• Silver Medal, International Math Olympiad, 1996

Professional Activities:

• External Reviewer: J. of Scheduling, IPCO, SODA, SUSCOM, Discrete Optimization, WAOA
• Organizer of theory seminar at UIUC, Spring / Fall 09
• Grad Admissions (FAA) committee for Fall 10

Personal:

• A great charitable orginazation: Smile Train
• Hobby: playing the piano, Lake Louise (played on a digital piano in 2010)

Contact:

• 3240 Siebel Center, 201 N. Goodwin ave, Urbana IL 61801
• Email: im3 at uiuc dot edu