We consider the extension of the orienteering problem, but now there are random waiting times at nodes before we can collect reward. This therefore naturally generalizes the stochastic knapsack problem also, where there is a trivial metric of co-located jobs. While most earlier papers on such stochastic problems bound adaptivity gaps using an LP relaxation, we are unable to do so because we don't know of good LPs for just orienteering. We circumvent this by directly arguing about an adaptive solution using a Martingale analysis and are able to show an O(log log B)-approximation algorithm and adaptivity gap.

We extend the results of Dean, Goemans and Vondrak for the Stochastic Knapsack problem to one where the reward of an item may be correlated with the size it instantiates to, and give a constant-factor non-adaptive approximation algorithm. We use ideas for this problem and also present a constant-factor adaptive approximation algorithm for the general Multi-Armed Bandits problem, relaxing certain Martingale property requirements of currently known algorithms.

In this paper, we look at the 2-edge-connectivity generalization of the problems: (i) group Steiner tree (now we want to choose representatives from each group and 2-connect them to the root), (ii) connected facility location (the facilities need to be 2-edge-connected), (iii) buy-at-bulk (the demand pairs need 2-edge-disjoint paths), and (iv) k-MST (pick an arbitrary set of k vertices and 2-connect them). We show that tree embedding techniques can be used to simplify all these problems and obtain polylogarithmic approximations.

Consider the following generalization of the online Steiner tree problem: each day, a new pair of vertices (s_i,t_i) arrive requiring k-edge-connectivity; the objective is to buy a set of edges to k-connect these vertices such that the total cost of the edges bought till date is competitive with the cost of the optimal offline solution feasible to the pairs that have arrived. We give an online algorithm with polylogarithmic competitiveness, by using recent results on embeddings into subtrees to get more structure on the cuts.

In the broadcast scheduling problem, there are a set of n pages, and requests for these arrive online. The server can broadcast pages at a fixed speed, and with any broadcast of some page, all pending requests for that page get satisfied. The goal is then to minimize the average response time of the requests. In this paper, we give an O(1 + ε)-speed O(1/ε²)-competitive online algorithm for the general problem with arbitrary page sizes.

We give an online speed-scaling algorithm which achieves constant competitiveness with (1 + ε)-speed augmentation for the problem of scheduling jobs on non-identical machines with each machine having an arbitrary power function, for the objective function of total flow time plus energy consumed.

We give an online algorithm which achieves constant competitiveness with (p + ε)-speed augmentation for the problem of non-clairvoyantly scheduling jobs with different degrees of parallelism on identical machines, with the objective of minimizing the L_p norm of flowtimes.

Consider the generalized min-sum set cover problem: we are given a universe of elements and a collection of subsets. Each subset S also has a requirement K(S). The goal is to output an ordering of the universe so that the total cover time of the sets is minimized, where the cover time of a set S is the earliest position in the order when K(S) elements from S have been output. We give a constant-factor approximation algorithm for this problem via rounding of a strengthened LP relaxation.

In this paper, we study scheduling problems with the added flexibility of not picking a small fraction of jobs. Formally, given a set of jobs (each with an associated profit) and an objective function (like maximum makespan, average completion time, or average flow time), the goal is to schedule a subset of jobs that achieve some target profit, while minimizing the objective function on those set of jobs.

We show that if a set system has hereditary approximation ratio of A (i.e., approximation ratio of any subsystem is also A), then its priority covering problem has an A log² k approximation algorithm. In particular such set systems admit an A log log² C approximation algorithm for the capacitated set cover problem where C is the maximum capacity of any set. We also show that this is tight upto log log C factor.

In the classic k-median problem, given a metric space, we are required to open k centers to minimize the total cost of connecting each client to the nearest open center. What if the vertices belonged to L color classes, and there are different budgets on the number of centers that can be opened in each color class? For example, if there are 2 color classes, then the constraint would be to open r red centers and b blue centers, and the objective is again to minimize the total cost of connecting each client to the nearest open center (clients don't have any colors). In this paper, we give a constant approximation for this, and the more general setting where the open centers have to form an independent set of a given matroid. The technique involves sparsifying an LP solution, to reduce it to a feasible solution of another LP which almost resembles matroid intersection, which is an integral polytope.