Cliff Stein
Cliff Stein is a part time visiting professor at Google. He is a member of the
Large Scale Optimization Team and the NYC Algorithms and Optimization Team . His research interests include
algorithms, combinatorial optimization, scheduling, graph algorithms, parallel and distributed algorithms and algorithm engineering. He has worked on a variety of projects in different areas, including advertising, optimization and computational infrastructure.
He is also the co-author of the best selling textbook Introduction to Algorithms
, together with Tom Cormen, Charles Leiserson and Ron Rivest.
A complete list of his publications can be found here .
Authored Publications
Sort By
Fast Algorithms for Knapsack via Convolution and Prediction
MohammadTaghi Hajiaghayi
Saeed Seddighin
Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC) (2018), pp. 1269-1282
Preview abstract
The knapsack problem is a fundamental problem in combinatorial optimization. It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size t with the maximum value from a collection of n items with given sizes and values.
Recent evidence suggests that a classic O(nt) dynamic-programming solution for the knapsack problem might be the fastest in the worst case. In fact, solving the knapsack problem was shown to be equivalent to the (min,+) convolution problem (Cygan et al., ICALP 2017), which is thought to be facing a quadratic-time barrier. This hardness is in contrast to the more famous (+,·) convolution (generally known as polynomial multiplication), that has an O(nlogn)-time solution via Fast Fourier Transform.
Our main results are algorithms with near-linear running times for the knapsack problem, if either the values or sizes of items are small integers. More specifically, if item sizes are integers bounded by s_max, the running time of our algorithm is O~((n + t)s_max). If the item values are integers bounded by v_max, our algorithm runs in time O~(n + t v_max). Best previously known running times were O(nt), O(n^2 s_max) and O(n s_max v_max) (Pisinger, J. of Alg., 1999).
At the core of our algorithms lies the prediction technique: Roughly speaking, this new technique enables us to compute the convolution of two vectors in time O (n e_max) when an approximation of the solution within an additive error of e_max is available.
Our results also have implications regarding algorithms for several other problems including tree sparsity, tree separability and the unbounded knapsack problem, in the case when some of the relevant numerical input values are bounded.
View details
Online Stochastic Packing Applied to Display Ad Allocation
Monika Henzinger
ESA (1) (2010), pp. 182-194
Preview abstract
Inspired by online ad allocation, we study online stochastic packing integer programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing integer programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple dual training-based algorithm achieves a (1 − o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1−1e1−1e for online ad allocation, and log(m) for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based algorithms on real data sets, and also indicates an intrinsic trade-off between fairness and efficiency.
View details
