Showing 2026Show all
3 papers · 1 filter
cs.DS2026
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…
cs.DM2026
An Algorithm for the Assignment Game Beyond Additive Valuations
Eric Balkanski, Christopher En, Yuri Faenza
The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is a…
cs.DS2026
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…