2 citations · 4 across the 12 of their papers we have counts for
15 papers
The Strong Secretary Conjecture is True for Linear Matroids
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos +2
We prove a guarantee for the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both…
Batched Pandora's Box
Shaddin Dughmi, Yusuf Hakan Kalayci, Vasilis Livanos +1
Motivated by numerous parallelizable stochastic search problems, most notable and timely among them being LLM inference-time scaling, we propose and study batched versions of the P…
Threshold Dynamics and Correlated Prophet Inequalities
José Correa, Maximilian Fichtl, Reda Jlibene +4
Prophet inequalities have become a central tool for analyzing the performance of online algorithms. However, most existing results assume that input random variables are independen…
About a ball removal process on bins
José Correa, Marcos Kiwi, Vasilis Livanos +2
We consider a basic balls-and-bins question in which you have to distribute balls into bins. Then, round by round, a ball is removed from a non-empty bin chosen uniformly a…
Free-Order Online Selection for k-Systems
Kristóf Bérczi, Vasilis Livanos, José A. Soto +1
The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. We introduce a bipartite graph fram…
Posted Pricing and Competition in Large Markets
José Correa, Vasilis Livanos, Dana Pizarro +1
Posted price mechanisms are prevalent in allocating goods within online marketplaces due to their simplicity and practical efficiency. We explore a fundamental scenario where buyer…
Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach
Vasilis Livanos, Ruta Mehta
The I.I.D. Prophet Inequality is a fundamental problem where, given independent random variables drawn from a known distribution , one has to decid…
Matroid Secretary via Labeling Schemes
Kristóf Bérczi, Vasilis Livanos, José Soto +1
The Matroid Secretary Problem (MSP) is one of the most prominent settings for online resource allocation and optimal stopping. A decision-maker is presented with a ground set of el…
Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
Vasilis Livanos, Kalen Patton, Sahil Singla
Over the past two decades, significant strides have been made in stochastic problems such as revenue-optimal auction design and prophet inequalities, traditionally modeled with …
Oracle-Augmented Prophet Inequalities
Sariel Har-Peled, Elfarouk Harb, Vasilis Livanos
In the classical prophet inequality settings, a gambler is given a sequence of random variables , taken from known distributions, observes their values in this…
Prophet Inequalities for Cost Minimization
Vasilis Livanos, Ruta Mehta
Prophet inequalities for rewards maximization are fundamental to optimal stopping theory with extensive applications to mechanism design and online optimization. We study the \emph…
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
Vasilis Livanos, Ruta Mehta, Aniket Murhekar
We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents a…
Simple and Optimal Greedy Online Contention Resolution Schemes
Vasilis Livanos
Real-world problems such as ad allocation and matching have been extensively studied under the lens of combinatorial optimization. In several applications, uncertainty in the input…
On Submodular Prophet Inequalities and Correlation Gap
Chandra Chekuri, Vasilis Livanos
Prophet inequalities and secretary problems have been extensively studied in recent years due to their elegance, connections to online algorithms, stochastic optimization, and mech…
Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence
Wei-Chun Lee, Vasilis Livanos, Ruta Mehta +1
The decisions that human beings make to allocate time has significant bearing on economic output and to the sustenance of social networks. The time allocation problem motivates our…