Janardhan Kulkarni

I am a Ph.D. student in the department of Computer Science at Duke University. My adviser is Kamesh Munagala. I am interested design of algorithms with provable performance guarantee. In particular, I work in resource allocation and scheduling problems arising in large scale distributed data-centers with added constraints of energy minimization, fairness and strategyproofness. My research involves using concepts and techniques from the fields of approximation algorithms, online algorithms and game theory.

Contact: kulkarni at cs dot duke dot edu

Research Interests:

Education:

Publications:

  1. SELFISHMIGRATE:A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
    with Sungjin Im, Kamesh Munagala, Kirk Pruhs
    FOCS 2014. Paper available on arXiv.

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

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

  4. Coordination mechanisms from (almost) all scheduling policies
    with Sayan Bhattacharya, Sungjin Im and Kamesh Munagala
    Innovations in Theoretical Computer Science, ITCS '14

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

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

  7. Cost Aware scheduling
    with Kamesh Munagala. WAOA, 2011

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

  9. Online Scheduling with General Cost Functions
    with Pradeesha Ashok, Sathish Govindarajan
    CCCG, 2010

  10. New epsilon-net constructions
    with Satish Govindarajan
    CCCG,2010

Submitted Papers:

  1. Minimizing Flow-Time for Unrelated Machines
    with Nikhil Bansal
    (Gives the first approximation algorithm for flow-time on unrelated machines. Will be submitted to STOC 2015. Paper available on arXiv.)

  2. A Geometric Approach to Diverse Group Formation
    with Arindam Khan and Sreenivas Gollapudi

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

  4. Local Search Approach for Graph Deanonymization
    with Wuzhou Zhang, Bharath Chelepalli and Ashwin Machanavajjhala

Internships:

  1. Microsoft Research, Silicon Valley, CA. Summer 2013
    Host: Sreenivas Gollapudi
  2. Visited professor Kirk Pruhs , University of Pittsburgh, April 2012
  3. Visited Vahab Mirrokni , Google Research, NYC, April 2014

Academic Awards (selected):

Talks:

  1. Invited talk, IBM TJ Watson, NYC (June 2014).Non-Clairvoyant Scheduling To Minimize Weighted Flow-Time.
  2. STOC 2014, NYC (June 2014).Competitive Algorithms From Competitive Equilibria.
  3. Invited talk, Google Research, NYC (April 2014). Dual Fitting Framework for Scheduling and Routing Games.
  4. ITCS 2014, Princeton University, Princeton (Jan 2014).Coordination Mechanisms From Almost All Scheduling Policies
  5. APPROX 2013,University of California,Berkeley (Aug 2013) Non-clairvoyant Scheduling to Minimize All Convex Functions
  6. MAPSP 2013, Pont à Mousson, France (Aug 2013). Coordination Mechanisms from (almost) all Scheduling Policies
  7. ALGO 2013, Ljubljana, Slovenia (Sept 2012). Coordination Mechanisms from (almost) all Scheduling Policies

Industry Experience:

I worked as a (senior) software engineer from 2004 to 2008 at Huawei Technologies and Citrix Systems. At industry, I worked on Internet routing protocols, especially on multicast routing. During that period, I dabbled with some IETF standardization work.
  1. PIM-Ping: A Tool to Test the Convexity of Ping Domain
    with Archana Patel
  2. Equal cost route support for RIP/RIPNG
    with Naveen Anand