Research

My CV.

I am interested in algorithms, scheduling, large data analysis, online algorithms and algorithmic applications.


Notice: A paper below may not be the most recent version. Send me an e-mail if you are interested in an up to date copy. The copyright of the published papers below have been transferred to the respective publishers.


Unpublished Manuscripts:

  1. Speed Scaling for Total Stretch Plus Energy
    with: Daniel Cole, Sungjin Im and Kirk Pruhs
    Manuscript


  2. Bargaining on Trees
    with: Arpita Ghosh, Satyen Kale, and Kevin Lang
    Manuscript


  3. Scheduling to Minimize Energy and Flow Time in Broadcast Scheduling
    with:
    Manuscript


Publications:

  1. Scalable K-Means++
    with: Bahman Bahmani, Andrea Vattani, Ravi Kumar and Sergei Vassilvitskii
    International Conference on Very Large Data Bases (VLDB 2012)


  2. Handling Forecast Errors while Bidding for Display Advertising
    with: Kevin Lang and Sergei Vassilvitskii
    International Conference on World Wide Web (WWW 2012)


  3. Online Scheduling with General Cost Functions
    with: Sungjin Im and Kirk Pruhs
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)


  4. Scheduling Heterogeneous Processors Isn't As Easy As You Think
    with: Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy and Kirk Pruhs
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)


  5. A Tutorial on Amortized Local Competitiveness in Online Scheduling
    with: Sungjin Im and Kirk Pruhs
    A tutorial on the popular potential function technique for online scheduling problems.
    ACM SIGACT News (June 2011)


  6. Fast Clustering using MapReduce
    with: Alina Ene and Sungjin Im
    ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2011) Oral Presentation.


  7. Filtering: A Method for Solving Graph Problems in MapReduce
    with: Silvio Lattanzi, Siddharth Suri and Sergei Vassilvitskii
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011)


  8. On Scheduling in Map-Reduce and Flow-Shops
    with: Anirban Dasgupta, Ravi Kumar and Tamas Sarlos
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011)


  9. Online Scheduling on Identical Machines using SRPT
    with: Kyle Fox
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)


  10. Online Scalable Scheduling for the \ell_k-norms of Flow Time Without Conservation of Work
    with: Jeff Edmonds and Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)


  11. An Online Scalable Algorithm for Minimizing \ell_k-norms of Weighted Flow Time on Unrelated Machines
    with: Sungjin Im
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)


  12. New Models and Algorithms for Throughput Maximization in Broadcast Scheduling
    with: Chandra Chekuri, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen and Louiqa Raschid
    Workshop on Approximation and Online Algorithms (WAOA 2010)


  13. Scheduling Jobs with Varying Parallelizability to Reduce Variance
    with: Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy and Kirk Pruhs
    ACM Symposium on Parallelism in Algorithms and Architectures
    (SPAA 2010)


  14. An Online Scalable Algorithm for Average Flowtime in Broadcast Scheduling
    with: Sungjin Im
    Awarded Best Student Paper
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
    Journal Version: ACM Transactions on Algorithms


  15. Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
    with: Chandra Chekuri and Sungjin Im
    17th Annual European Symposium on Algorithms (ESA 2009)
    Journal Version (Combines the results of this paper and the SODA 2009 paper below):
    Theory of Computing: Special Issue in honor of Rajeev Motwani


  16. Longest Wait First For Broadcast Scheduling
    with: Chandra Chekuri and Sungjin Im
    7th Workshop on Approximation and Online Algorithms (WAOA 2009)


  17. Online Scheduling to Minimize the Maximum Delay Factor
    with: Chandra Chekuri
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)