5 papers
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…
Online Min-Cost Matching with General Arrivals
Josh Ascher, Eric Balkanski, Jason Chatzitheodorou +1
In the classic online min-cost matching problem, the goal is to match a sequence of requests that arrive dynamically over time to a set of static servers, aiming to minimize the to…
Procurement Auctions with Predictions: Improved Frugality for Facility Location
Eric Balkanski, Nicholas DeFilippis, Vasilis Gkatzelis +1
We study the problem of designing procurement auctions for the strategic uncapacitated facility location problem: a company needs to procure a set of facility locations in order to…
Fair Secretaries with Unfair Predictions
Eric Balkanski, Will Ma, Andreas Maggiori
Algorithms with predictions is a recent framework for decision-making under uncertainty that leverages the power of machine-learned predictions without making any assumption about…
Strategyproof Learning with Advice
Eric Balkanski, Cherlin Zhu
An important challenge in robust machine learning is when training data is provided by strategic sources who may intentionally report erroneous data for their own benefit. A line o…