Traditional online algorithms deal typically with (1) inputs over a sequence with a goal of minimizing the total cost; (2) inputs over a time where the goal is to minimize some function of the time. Following the work of Emek, Kutten and Wattenhofer (STOC'16) we consider problems where the goal is to minimize the cost plus the waiting time (delay) until requests are served. In particular we deal with online min-cost matching with delays (matching players in game platforms) and online two sided min-cost matching with delays (matching customers to drivers in transportation platforms such as Uber/Lyft). We provide logarithmic competitive algorithms for these problems.

Based on joint work with Chiplunkar, Kaplan (SODA’ 17), Ashlagi, Charikar, Chiplunkar, Geri, Kaplan, Makhijani, Wang, Wattenhofer (APPROX’ 17).

We consider a setting where selfish agents want to schedule jobs on related machines.  The agent submitting a job picks a server that minimizes a linear combination of the server price and the resulting response time for that job on the selected server. The manager's task is to maintain server prices to (approximately) optimize the maximum response time, which is a measure of social good.  We show that the existence of a pricing scheme with certain competitiveness is equivalent to the existence of a monotone immediate-dispatch algorithm.  Our main result is a monotone immediate-dispatch algorithm that is  O(1)-competitive with respect to the maximum response time.

We consider the problem of designing a packet-level congestion control and scheduling policy for datacenter networks. Current datacenter networks primarily inherit the principles that went into the design of Internet, where congestion control and scheduling are distributed. While distributed architecture provides robustness, it suffers in terms of performance. Unlike Internet, data center is fundamentally a ""controlled"" environment. This raises the possibility of designing a centralized architecture to achieve better performance. Recent solutions such as Fastpass and Flowtune have provided the proof of this concept. This raises the question: what is theoretically optimal performance achievable in a data center?

We propose a centralized policy that guarantees a per-flow end-to-end flow delay bound of O(#hops*flow-size/gap-to-capacity). Effectively such an end-to-end delay will be experienced by flows even if we removed congestion control and scheduling constraints as the resulting queueing networks can be viewed as the classical reversible multi-class queuing network, which has a product-form stationary distribution. In the language of Harrison et al., we establish that baseline performance for this model class is achievable.

Indeed, as the key contribution of this work, we propose a method to emulate such a reversible queuing network while satisfying congestion control and scheduling constraints. Precisely, our policy is an emulation of Store-and-Forward (SFA) congestion control in conjunction with Last-Come-First-Serve Preemptive-Resume (LCFS-PR) scheduling policy.

Consider the seller's problem of finding optimal prices for her (divisible) goods when faced with a set of consumers, given that she can only observe their purchased bundles at the set prices, i.e., access to only revealed preferences (demand oracle). We study both social welfare and profit maximization under this setting, assuming the concave valuation function of consumers and the convex production cost function of the seller, which are standard assumptions in economics.

A recent series of works (Roth et al., 2016, 2017) studied this problem for various special cases of valuation and cost functions while making no assumption on the demand oracle. The main difficulty they observe is that the resulting optimization problem is non-convex in prices. For social-welfare maximization, we obtain a natural interpretation of the revealed preference feedback in the dual optimization problem, and thereby obtain a simple gradient-based algorithm. This simplifies and improves on the series of works of Roth et al. (2016, 2017) at least by a quadratic factor in terms of query complexity.

Second, we study social-welfare maximization in the online setting, where consumers arrive one-by-one in a random order, a.k.a. the secretary model. For the case where consumer valuation can be an arbitrary continuous function, we design a price posting mechanism that achieves average expected social welfare up to an additive factor of 1/sqrt(m) of maximum social welfare, where m is the number of consumers. Third, for profit maximization, we obtain the first FPTAS when valuation and cost functions are separable, with a matching lower bound. For the non-separable case, we show that no PTAS exists, even when only the cost function is non-separable.

The talk addresses a classical problem in the area of scheduling, namely minimizing the total weighted completion time of non-preemptive jobs on a set of unrelated machines. Uncertainty enters the model by assuming that job processing times are stochastic. In order to obtain constant factor approximation algorithms for that problem, prior work required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. In contrast, we analyze a purely combinatorial, online algorithm. Maybe surprisingly, we show how to derive performance bounds for that algorithm that are of the same order of magnitude as those of earlier work, while our results are the first for an online setting. The analysis is based on dual fitting techniques. (Joint work with V. Gupta, B. Moseley, Q. Xi)

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to ma- troids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg [STOC 2012] and Feldman et al. [SODA 2015] show that for adversarial arrival order of random variables the optimal prophet inequalities give a 1/2-approximation. For many settings, however, it’s conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the 1/2-approximation and obtain (1−1/e)- approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan [SODA 2011] and Esfandiari et al. [ESA 2015] who worked in the special cases where we can fully control the arrival order or when there is only a single item.

Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

Joint work with Soheil Ehsani, MohammadTaghi Hajiaghayi, and Sahil Singla. To appear in SODA 2018.

There are four challenges in Topic Modeling: (i) Scaling up to very large data sets of billions of tokens (ii) Learning models with 100K + topics and (iii) doing so with a (provable) polynomial time algorithm with good error bounds which also (iv) performs well empirically on real corpora. We demonstrate all of the above starting with a new model.

Joint work with : Chiranjib Bhattacharyya and Harsha Simhadri

Clustering is a fundamental technique in data analysis: the objective is to identify a set of k points (centroids) that minimize the clustering cost (a function of the distances of points to the nearest centroid). With very large data sets, we seek efficient constructions of small samples that act as surrogates to the full data. Existing methods that provide quality guarantees are either worst-case, unable to benefit from structure of real data set, or make explicit assumptions on the structure.  We show here how to avoid both these pitfalls using adaptive algorithms and demonstrate experimentally large gains of our adaptive versus the worst-case constructions.

We introduce the stochastic graph exploration problem. The input is an undirected graph G with a source vertex s, stochastic edge costs, and deterministic rewards of vertices. The goal is to find a set F of edges of total cost at most 1, such that the subgraph of G induced by F is connected, contains s, and has maximum total reward. The set F is constructed by adding edges one by one and after each step the subgraph of G induced by F has to be connected and contain s. When an edge is chosen, its actual cost is revealed. The chosen edge has to be added to F, unless the total cost of edges in F would exceed 1, in which case the process finishes.

We show that this problem generalizes the stochastic knapsack problem. However, as opposed to knapsack problem, the adaptivity gap of the stochastic graph exploration problem is superconstant. On the positive side, we show bi-criteria approximation algorithms both for trees and general graphs.