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, University of Illinois at Urbana Champaign, Fall 2006~Summer 2012.
• M.S. in Computer Science and Engineering, Seoul National University, Feb 2004
• B.S. in Computer Science and Engineering, Seoul National University (Summa Cum Laude), Feb 2002
• Diploma, Seoul Science High School, Feb 1998

Publication:

1. Optimized Scheduling of Multi-IMA Partitions with Exclusive Region for Synchronized Real-Time Multi-Core Systems
   Jung-Eun Kim, Man-Ki Yoon, Sungjin Im, Richard Bradford and Lui Sha
   Design, Automation & Test in Europe, DATE '13
   

2. Energy Efficient Schedulig of Parallelizable Jobs
   with Kyle Fox and Benjamin Moseley
   24th ACM-SIAM Symposium on Discrete Algorithms , SODA '13
   

3. Shortest-Elapsed-Time-First on a Multiprocessor
   with Neal Barcelo, Benjamin Moseley and Kirk Pruhs
   Mediterranean Conference on Algorithms, MedAlg '12
   

4. Online Scheduling Algorithms for Average Flow Time and its Variants
   Ph.D. thesis
   

5. Speed scaling for stretch plus energy
   with Daniel Cole, Benjamin Moseley and Kirk Pruhs
   Operations Research Letters
   

6. Minimum Latency Submodular Cover
   with Viswanath Nagarajan and Ruben Van Der Zwaan
   39th International Colloquium on Automata, Languages and Programmig, ICALP '12
   

7. 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
   

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

9. 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
   

10. 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
    

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

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

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

14. 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
    

15. 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
    

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

17. 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
    

18. 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
    

19. 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
    

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

21. 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:

• D224, Levine Science Research Center, Research Drive, Duke University, Durham NC 27708.
• Email: "first name" at cs dot duke dot edu