Publications (33)
Non-monotone Submodular Maximization in Exponentially Fewer Iterations
Eric Balkanski, Adam Breuer, Yaron Singer
In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our mai…
The Knapsack Secretary Problem is Strictly Harder Than the Secretary Problem
Eric Balkanski, Jason Chatzitheodorou, Dimitris Fotakis +1
The knapsack secretary problem is a generalization of the classical secretary problem where the accepted items must satisfy a knapsack constraint. A line of work has developed cons…
Dynamic First Price Auctions Robust to Heterogeneous Buyers
Shipra Agrawal, Eric Balkanski, Vahab Mirrokni +1
We study dynamic mechanisms for optimizing revenue in repeated auctions, that are robust to heterogeneous forward-looking and learning behavior of the buyers. Typically it is assum…
The FAST Algorithm for Submodular Maximization
Adam Breuer, Eric Balkanski, Yaron Singer
In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint whose ap…
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
Eric Balkanski, Aviad Rubinstein, Yaron Singer
In this paper we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimiza…
Scheduling with Speed Predictions
Eric Balkanski, Tingting Ou, Clifford Stein +1
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, ver…