7 citations · 20 across the 8 of their papers we have counts for
7 papers · 1 filter
The Role of Commitment in Optimal Stopping
José Correa, Evangelia Gergatsouli, Bruno Ziliotto
We investigate the role of commitment in optimal stopping by studying all the variants between Prophet Inequality (PI) and Pandora's Box (PB). Both problems deal with a set of vari…
Online Combinatorial Optimization with Graphical Dependencies
Zhimeng Gao, Evangelia Gergatsouli, Kalen Patton +1
Most existing work in online stochastic combinatorial optimization assumes that inputs are drawn from independent distributions -- a strong assumption that often fails in practice.…
Weitzman's Rule for Pandora's Box with Correlations
Evangelia Gergatsouli, Christos Tzamos
Pandora's Box is a central problem in decision making under uncertainty that can model various real life scenarios. In this problem we are given boxes, each with a fixed openin…
Graph Connectivity with Noisy Queries
Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis +2
Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its op…
Approximating Pandora's Box with Correlations
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan +1
We revisit the classic Pandora's Box (PB) problem under correlated distributions on the box values. Recent work of arXiv:1911.01632 obtained constant approximate algorithms for a r…
Improved Bounds for Online Facility Location with Predictions
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis +2
We consider Online Facility Location in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and mu…
Pandora's Box with Correlations: Learning and Approximation
Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng +2
The Pandora's Box problem and its extensions capture optimization problems with stochastic input where the algorithm can obtain instantiations of input random variables at some cos…