My research interests are in theoretical computer science - particularly algorithms - and combinatorics. I mainly work on approximation algorithms for graph problems; other broad areas of interest are graph theory, randomized algorithms and the probabilistic method, and game theory.
Recently on my mind:
- Matchings
- Covering and Packing LPs
- Packing Steiner Trees and Forests
- Auctions with competing groups of bidders.
- Connectivity problems.
Papers:
Online Stochastic Ad Allocation: Efficiency and Fairness.
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab Mirrokni, Cliff Stein.On k-Column Sparse Packing Programs.
Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, Aravind Srinivasan. arXiv.org preprint, 2009.Online Ad Assignment with Free Disposal.
Jon Feldman, Nitish Korula, Vahab Mirrokni, S. Muthukrishnan, Martin Pál. To appear in WINE, 2009.
We study an online weighted assignment problem with a set of fixed nodes corresponding to advertisers and online arrival of nodes corresponding to ad impressions. Each advertiser a has a contract for n(a) impressions, and each impression has a set of weighted edges to advertisers. The problem is to assign the impressions online so that while each advertiser a gets n(a) impressions, the total weight of edges assigned is maximized.
Our insight is that ad impressions allow for free disposal, that is, advertisers are indifferent to, or prefer being assigned more than n(a) impressions without changing the contract terms. This means that the value of an assignment only includes the n(a) highest-weighted items assigned to each node a. With free disposal, we provide an algorithm for this problem that achieves a competitive ratio of 1 - 1/e; this is the best possible. Our algorithm also applies more broadly to Generalized Assignment Problems (GAP) with Free Disposal, and again we obtain O(1) competitive ratios.Unsplittable Flow in Paths and Trees, and Column-Restricted Packing Integer Programs.
Chandra Chekuri, Alina Ene and Nitish Korula. APPROX, 2009.
In the Unsplittable Flow problem (UFP), the input is an edge-capacitated graph and a set of k requests; each request consists of a source-destination pair of vertices si, ti, a demand di, and a weight wi. The goal is to select a max-weight set of requests that can be simultaneously routed unsplittably; that is, for which we can send di units of flow along a single path from si to ti. We give the first approximation algorithm for UFP on trees, and the first known LP for UFP on paths with a o(n) integrality gap. We also consider UFP in general graphs and Column-Restricted Packing Integer Programs, of which the natural UFP LP is an example.A Graph Reduction Step Preserving Element Connectivity, and Applications .
Chandra Chekuri and Nitish Korula. ICALP, 2009.
Given an undirected graph and a subset of its vertices called terminals, the element-connectivity of terminals u,v is the maximum number of u-v paths that are pairwise disjoint in both edges and non-terminals. Element-connectivity is more general than edge-connectivity, and less general than vertex-connectivity. We show that a graph reduction step originally due to Hind and Oellermann preserves all the pairwise element-connectivities of the terminals, allowing one to greatly simplify graphs while preserving element-connectivity. We also give applications of this reduction step to connectivity and network design problems.Algorithms for Secretary Problems on Graphs and Hypergraphs.
Nitish Korula and Martin Pál. ICALP, 2009.
We give constant-competitive algorithms for several online matching problems, with applications to ad reservation systems. Given an edge-weighted graph, where edges or vertices arrive online in a random order, the goal is to construct an online matching of weight comparable to the maximum-weight matching in the graph. We give algorithms for constructing matchings in graphs and hypergraphs, and improve the approximations for the transversal matroid and graphic matroid secretary problems. Also, we introduce secretary problems with groups.Single-Sink Network Design with Vertex Connectivity Requirements.
Chandra Chekuri and Nitish Korula. FSTTCS, 2008. (Full version not yet online; send me email if you'd like a copy.)
We study several related network design problems in undirected graphs with vertex-connectivity requirements. Given an edge-weighted graph, a set of terminals T, and an integer k, the goal of the basic k-connectivity problem is to find a minimum-cost subgraph that k-connects the given terminals. We give an kO(k) log n-approximation for this problem using a primal-dual method. (See also the improved algorithm of Chuzhoy and Khanna for a k log n-approximation.) We also study the problems of routing traffic along k disjoint paths from each terminal to a given root, using Rent-or-Buy and Buy-at-Bulk cost functions, and obtain improved approximations. (Some of these algorithms are the first approximations for these problems with k > 2.)Pruning 2-Connected Graphs, and Applications.
Chandra Chekuri and Nitish Korula. FSTTCS, 2008.
Let the density of an edge-weighted graph be the sum of its edge weights divided by the number of vertices it contains. We describe an algorithm that, given a 2-(vertex)-connected graph G, finds a 2-connected subgraph of density comparable to that of G, of any desired size. This useful pruning algorithm has applications in finding cheap subgraphs of a given size, or large subgraphs of bounded cost. For example, given a graph G with edge-costs, a subset of vertices marked as terminals, and an integer k, the k-λVC problem is to find a minimum-cost λ-vertex-connected subgraph with at least k terminals. When λ=1, this is the well-known k-MST problem. We give the first poly-logarithmic approximation for the case when λ=2; this result also generalizes that of Lau et al. for the similar edge-connectivity problem.Improved Algorithms for Orienteering and Related Problems.
Chandra Chekuri, Nitish Korula and Martin Pál. SODA, 2008.
In the orienteering problem, we are given an edge-weighted graph G, two vertices s,t, and a budget B. The goal is to find a walk from s to t of length at most B that visits as many vertices as possible. For undirected graphs, we improved the approximation ratio from 3 to (2+ε). For directed graphs, we give a simple combinatorial poly-logarithmic approximation algorithm. (Also see the clever LP-based algorithm achieving the same approximation ratio for orienteering in directed graphs by Viswanath Nagarajan and R. Ravi.) Our approximations for orienteering are based on, or lead to, improved algorithms for several related problems.Better Approximations for Orienteering with Time Windows.
Chandra Chekuri and Nitish Korula. Submitted.
The time-window problem is a variant of orienteering in which every vertex has a release time and a deadline, and we get credit for a vertex only if we visit it between its release time and deadline (inside its time window). We obtain improved approximations for this problem by focusing on the lengths of the longest and shortest time windows.Overlap Number of Graphs.
Daniel Cranston, Nitish Korula, Timothy LeSaulnier, Kevin Milans, Christopher Stocker, Jennifer Vandenbussche, Douglas B. West. In Preparation.
A labeling of a graph is a set S of labels together with a function f assigning each vertex a subset of the labels. A labeling is an overlap representation if vertices u,v are adjacent iff f(u) and f(v) intersect and neither properly contains the other. (With only the first part of the condition, one obtains the well-known intersection representation defined by Erdos, Goodman and Posa.) The overlap number of a graph is the size of the smallest label set S such that the graph admits an overlap representation with S; computing the overlap number of a given graph is NP-Hard. We give a polynomial time algorithm to find an optimal overlap representation for trees, and exactly characterize the extremal values of overlap numbers for n-vertex planar graphs and all n-vertex graphs.