4 papers · 1 filter
A Consistency-Robustness Framework for Robust Optimization: Integrating Predictions into Robust Scheduling
Yasser Alghouass, Eric Balkanski, Nicole Megow +1
Robust optimization protects against uncertainty by optimizing for the worst case over a prescribed uncertainty set. This protection can be overly conservative when forecasts, hist…
On the Average-Case Performance of Greedy for Maximum Coverage
Eric Balkanski, Jason Chatzitheodorou, Flore Sentenac
For the classical maximum coverage problem, the greedy algorithm achieves a worst-case approximation, which is optimal unless . The notion of coverage…
The Power of Greedy for Online Minimum Cost Matching on the Line
Eric Balkanski, Yuri Faenza, Noemie Perivier
We consider the online minimum cost matching problem on the line, in which there are servers and, at each of time steps, a request arrives and must be irrevocably matched t…
Learning Low Degree Hypergraphs
Eric Balkanski, Oussama Hanguir, Shatian Wang
We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these s…