Janardhan Kulkarni

Hi! I am a Ph.D. student in the department of Computer Science at Duke University. My adviser is Kamesh Munagala. I am interested in design of algorithms with provable performance guarantees. In particular, I study resource allocation and scheduling problems, with constraints on fairness, energy minimization, strategyproofness, that arise in large scale distributed data centers. My research involves using concepts and techniques from the fields of approximation algorithms, online algorithms and game theory. I am also broadly interested in the intersection of online algorithns, online learning and game theory. If you want to know more about my work, please take a look at my research statement.

Contact: kulkarni at cs dot duke dot edu

Here is my CV.

Research Interests:

Professional Activities:


Submitted Papers:

  1. Tight Bounds For Online Vector Scheduling
    with Sungjin Im, Nathaniel Kell, Debmalya Panigrahi
    (submitted to FOCS 2015)

  2. A Geometric Approach To Diverse Group Formation
    with Sreenivas Gollapudi, Arindam Khan, Kunal Talwar, Sadra Yazdanbod
    (submitted to APPROX 2015)

  3. Near-optimal Multi-unit Auctions with Ordered Bidders
    with S.Bhattacharya, E. Koutsoupias, S. Leonardi, T. Roughgarden and X.Xu
    (Submitted to SICOMP journal)


  1. Dynamic Coordination Games
    with Vahab Mirrokni
    NetEcon 2015

  2. Temporal Fairness of Round Robin
    with Sungjin Im and Ben Moseley
    SPAA 2015

  3. Minimizing Flow-Time for Unrelated Machines
    with Nikhil Bansal
    STOC 2015
    (The paper gives the first approximation algorithm for flow-time on unrelated machines.)

  4. Robust Price of Anarchy Bounds via LP and Fenchel Duality
    with Vahab Mirrokni
    SODA 2015

  5. SELFISHMIGRATE:A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
    with Sungjin Im, Kamesh Munagala, Kirk Pruhs
    FOCS 2014.
    (The paper gives the first non-clairvoyant algorithm for minimizing flow-time for unrelated machines.)

  6. Coordination Mechanisms for Selfish Routing Over Time on a Tree
    with Sayan Bhattacharya, Vahab Mirrokni
    ICALP 2014

  7. Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
    with Sungjin Im and Kamesh Munagla
    STOC 2014

  8. Coordination mechanisms from (almost) all scheduling policies
    with Sayan Bhattacharya, Sungjin Im and Kamesh Munagala
    ITCS 2014

  9. Near-optimal Multi-unit Auctions with Ordered Bidders
    with S.Bhattacharya, E. Koutsoupias, S. Leonardi, T. Roughgarden and X.Xu
    Electronic Commerce, EC'13

  10. Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
    with Sunjin Im, Kyle Fox and Benjamin Moseley
    APPROX 2013

  11. Cost Aware scheduling
    with Kamesh Munagala. WAOA 2011

  12. On Allocations with Negative Externalities
    with Sayan Bhattacharya, Kamesh Munagala and Xiaoming Xu
    WINE 2012

  13. Small Strong Epsilon Nets
    with Pradeesha Ashok, Sathish Govindarajan
    CCCG 2010

  14. New epsilon-net constructions
    with Satish Govindarajan
    CCCG 2010

Working Papers

  1. Greedy dispatch meets greedy jobs: Online scheduling of selfish jobs for unrelated machines
    with Sungjin Im

  2. Local Search Approach for Graph Deanonymization
    with Wuzhou Zhang, Bharath Chelepalli and Ashwin Machanavajjhala
    (Based on WSDM Data Challenge 2013. We were ranked 2nd overall)

Internships and Visits:

  1. Visited Professor Nikhil Bansal , University of Eindhoven, Fall 2014
  2. Microsoft Research, Bangalore, India. Summer 2014
    Host: Nikhil Devanur
  3. Visited Vahab Mirrokni , Google Research, NYC, April 2014, Oct 2014
  4. Microsoft Research, Silicon Valley, CA. Summer 2013
    Host: Sreenivas Gollapudi
  5. Visited professor Kirk Pruhs , University of Pittsburgh, April 2012

Academic Awards (selected):


  1. Invited Talk, Workshop on Online Algorithms and Learning, Lorentz Center, NL, Nov 2014 . Dual-Fitting Framework For Non-Clairvoyant Scheduling.
  2. FOCS 2014, Oct 2014. Non-Clairvoyant Scheduling To Minimize Weighted Flow-Time.
  3. Invited Talk, IISc, Bangalore, Sept 2014. Dual-Fitting Framework For Non-Clairvoyant Scheduling.
  4. Invited talk, China Theory Week, 2014. Non-Clairvoyant Scheduling To Minimize Weighted Flow-Time.
  5. Invited talk, IBM TJ Watson, NYC (June 2014).Non-Clairvoyant Scheduling To Minimize Weighted Flow-Time.
  6. ICALP 2014, Copenhagen, Denmark, July 2014. Temporal Routing over Tree Networks
  7. STOC 2014, NYC (June 2014).Competitive Algorithms From Competitive Equilibria.
  8. Invited talk, Google Research, NYC (April 2014). Dual Fitting Framework for Scheduling and Routing Games.
  9. ITCS 2014, Princeton University, Princeton (Jan 2014).Coordination Mechanisms From Almost All Scheduling Policies
  10. APPROX 2013,University of California,Berkeley (Aug 2013) Non-clairvoyant Scheduling to Minimize All Convex Functions
  11. MAPSP 2013, Pont à Mousson, France (Aug 2013). Coordination Mechanisms from (almost) all Scheduling Policies
  12. ALGO 2013, Ljubljana, Slovenia (Sept 2012). Coordination Mechanisms from (almost) all Scheduling Policies