Journal Papers (Accepted and Under Review)

Gamma Analysis: A Study on Online Stochastic Optimization,
Submitted.
[Abstract]
We study the the problem of preemptive job scheduling in a stochastic environment. We characterize statistical quantities that affect the performance of heuristic policies such as the weighted round robin policy and the stochastic offline policy based on weighted shortest expected processing time rule. We quantify the performances of such policies with respect to the clairvoyant policy by studying the competitive ratio. We also demonstrate reductions from the problems with multiple machines and the problems with weighted jobs to single machine unweighted problems, which could be of independent interest.
Also, in order to provide systematic insights into the effect of the stochasticity of the environment on the performances of different policies, we propose gamma analysis as a parametric approach to study this problem. We provide some evidences that gamma analysis can be helpful in studying other online stochastic optimization problems.

Concise Bid Optimization Strategies with Multiple Budget Constraints,
with M. Bateni, K. Bhawalkar, and V. Mirrokni.
Second Round of Review, Management Science.
[Abstract]
A major challenge faced by marketers attempting to optimize their advertising campaigns is to deal with budget constraints. The problem is even harder in the face of multidimensional budget constraints, particularly in the presence of many decision variables involved and the interplay among the decision variables through such constraints. Concise bidding strategies help advertisers deal with this challenge by introducing fewer variables to act on.
In this paper, we study the problem of finding optimal concise bidding strategies for advertising campaigns with multiple budget constraints. We provide approximation algorihtms based on ideas from dynamic programming and also a very fast dependent randomized rounding of the LP relaxation that runs in linear time and may be of independent interest. Our results do not rely on any concavity assumption about the value or the cost functions. Moreover, our results are not limited to costperclick models and (as opposed to uniform bidding strategies as the current state of the art) can apply to payperimpression or payperconversion models, too. We accompany our theoretical results with experimental findings that show an improvement between 1% to 6% over uniform bidding in case of one budget constraint, and an average increase of 5% over an enhanced version of uniform bidding designed for the problems with multiple budget constraints.

LargeScale Bundle Size Pricing: A Theoretical Analysis,
with T. Abdallah and J. Reed.
Second Round of Review, Management Science.
[Abstract]
Bundle size pricing (BSP) is a multidimensional selling mechanism where the firm prices the size of the bundle rather than the different possible combinations of bundles. In BSP, the firm offers the customer a menu of different sizes and prices. The customer then chooses the size that maximizes his surplus and customizes his bundle given his chosen size. While BSP is commonly used across several industries, little is known about the optimal BSP policy in terms of sizes and prices along with the theoretical properties of its profit. In this paper, we provide a simple and tractable theoretical framework to analyze the largescale BSP problem where a multiproduct firm is selling a large number of products. The BSP problem is in general hard as it involves optimizing over order statistics, however we show that for large numbers of products, the BSP problem transforms from a hard multidimensional problem to a simple multiunit pricing problem with concave and increasing utilities. Our framework allows us to identify the main source of inefficiency of BSP that is the heterogeneity of marginal costs across products. For this reason, we propose two new BSP policies called "clustered BSP" and "assorted BSP" that significantly reduce the inefficiency of regular BSP. We then utilize our framework to study richer models of BSP such as when customers have budgets and when there exists multiple customer types.

Online Resource Allocation with Limited Flexibility,
with X. Wang and J. Zhang.
Second Round of Review, Management Science.
[Abstract]
We consider a class of online resource allocation problems in which there are n
types of resources with limited initial inventory and n demand classes. The resources
are flexible in that each type of resources can serve more than one demand class.
In this paper, we focus on a special class of structures with limited flexibility, the
long chain design, which was proposed by Jordan and Graves (1995) and has been an
important concept in the design of sparse flexible processes. We show the effectiveness
of the long chain design in mitigating supplydemand mismatch under a simple myopic
online allocation policy. In particular, we provide an upper bound on the expected
total number of lost sales that is irrespective of how large the market size is.

An O(log n / log log n)approximation Algorithm for the Asymmetric Traveling Salesman Problem,
with M. X. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi.
Operations Research, 2017.
[Abstract] We present a randomized O(log n / log log n)approximation algorithm for the asymmetric traveling sales man problem (ATSP). This provides the first asymptotic improvement over the longstanding Θ(logn)approximation bound stemming from the work of Frieze et al. [FGM82].
The key ingredient of our approach is a new connection between the approximability of the ATSP and the notion of socalled thin trees. To exploit this connection, we employ maximum entropy rounding—a novel method of randomized rounding of LP relaxations of optimization problems. We believe that this method might be of independent interest.

Maximizing Stochastic Monotone Submodular Functions,
with H. Nazerzadeh.
Management Science, 2016.
[Abstract]
We study the problem of maximizing a stochastic monotone submodular function with respect to a matroid constraint. Due to the presence of diminishing marginal values in realworld problems, our model can capture the effect of stochasticity in a wide range of applications. We show that the adaptivity gap  the ratio between the values of optimal adaptive and optimal nonadaptive policies  is bounded and is equal to 1.58. We propose a polynomialtime nonadaptive policy that achieves this bound. We also present an adaptive myopic policy that obtains at least half of the optimal value. Furthermore, when the matroid is uniform, the myopic policy achieves the optimal approximation ratio of 0.63.

Santa claus Meets Hypergraph Matchings,
with U. Feige and A. Saberi.
Transactions on Algorithms, 2012.
[Abstract]
We consider the restricted assignment version of the problem of maxmin fair allocation of indivisible goods, also known as the Santa Claus problem. There are m items and n players. Every item has some nonnegative value, and every player is interested in only some of the items. The goal is to distribute the items to the players in a way that maximizes the minimum of the sum of the values of the items given to any player. It was previously shown via a nonconstructive proof that uses the Lovász local lemma that the integrality gap of a certain configuration LP for the problem is no worse than some (unspecified) constant. This gives a polynomial time algorithm to estimate the optimum value ofthe problem within a constant factor, but does not provide a polynomial time algorithm for finding a corresponding allocation.
We use a different approach to analyze the integrality gap. Our approach is based upon local search techniques for finding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the configuration LP is no worse than 1/4. Our proof provides a local search algorithm which finds the corresponding allocation, but is nonconstructive in the sense that this algorithm is not known to converge to a local optimum in a polynomial number of steps.

An Approximation Algorithm for Maxmin Fair Allocation of Indivisible Goods,
with A. Saberi.
SIAM Jounal on Computing, 2010.
[Abstract]
In this paper, we give the first approximation algorithm for the problem of maxmin fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them.
The approximation ratio of our algorithm is Ω(1/(k^{0.5} log^{3} k))). As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree to an integral matching which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem.
Refereed Conference Papers

Concise Bid Optimization Strategies with Multiple Budget Constraints,
with M. Bateni, K. Bhawalkar, and V. Mirrokni.
Proceedings of the 10th Conference on Web and Internet Economics (WINE), 2014.

An O(log n/ log log n)approximation Algorithm for the Asymmetric Traveling Salesman Problem,
with M. X. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi.
Proceedings of the 21st ACMSIAM Symposium on Discrete Algorithms (SODA), 2010. (Winner of the Best Paper Award)

On the Inefficiency Ratio of Stable Equilibria in Congestion Games,
with A. Saberi.
Proceedings of the 5th Conference on Web and Internet Economics (WINE), 2009.

Santa claus meets hypergraph matchings,
with U. Feige and A. Saberi.
Proceedings of the 11th Workshop on Approximation, Randomization and Combinatorial
Optimization (APPROX), 2008.

Stochastic Submodular Maximization,
with H. Nazerzadeh and A. Saberi.
Proceedings of the 4th Conference on Web and Internet Economics (WINE), 2008.

An approximation algorithm for maxmin fair allocation of indivisible goods,
with A. Saberi.
Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), 2007.