7 citations · 20 across the 8 of their papers we have counts for
12 papers
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.…
Prophet Secretary Against the Online Optimal
Paul Dütting, Evangelia Gergatsouli, Rojin Rezvan +2
We study the prophet secretary problem, a well-studied variant of the classic prophet inequality, where values are drawn from independent known distributions but arrive in uniforml…
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…
Contextual Pandora's Box
Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli +2
Pandora's Box is a fundamental stochastic optimization problem, where the decision-maker must find a good alternative while minimizing the search cost of exploring the value of eac…
Online Learning for Min Sum Set Cover and Pandora's Box
Evangelia Gergatsouli, Christos Tzamos
Two central problems in Stochastic Optimization are Min Sum Set Cover and Pandora's Box. In Pandora's Box, we are presented with boxes, each containing an unknown value and the…
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…
Black-box Methods for Restoring Monotonicity
Evangelia Gergatsouli, Brendan Lucier, Christos Tzamos
In many practical applications, heuristic or approximation algorithms are used to efficiently solve the task at hand. However their solutions frequently do not satisfy natural mono…
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…
The Complexity of Black-Box Mechanism Design with Priors
Evangelia Gergatsouli, Brendan Lucier, Christos Tzamos
We study black-box reductions from mechanism design to algorithm design for welfare maximization in settings of incomplete information. Given oracle access to an algorithm for an u…