1 citations · 1 across the 12 of their papers we have counts for
14 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…
Kernel Methods for Refined Prophet Inequalities
Patrick Loiseau, Mathieu Molina, Vianney Perchet +2
The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irr…
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…
Tight Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1
Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing th…
Competition Versus Complexity in Multiple-Selection Prophet Inequalities
Eugenio Cruz-Ossa, Sebastian Perez-Salazar, Victor Verdugo
Competition complexity formalizes a compelling intuition: rather than refining the mechanism, how much additional competition is sufficient for a simple mechanism to compete with a…
Linear Programming Hierarchies Collapse under Symmetry
Yuri Faenza, Víctor Verdugo, José Verschae +1
The presence of symmetries is one of the central structural features that make some integer programs challenging for state-of-the-art solvers. In this work, we study the efficacy o…
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…
Mean-field Concentration of Opinion Dynamics in Random Graphs
Javiera Gutiérrez-Ramírez, David Salas, Victor Verdugo
Opinion and belief dynamics are a central topic in the study of social interactions through dynamical systems. In this work, we study a model where, at each discrete time, all the…
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…
Prophet Upper Bounds for Online Matching and Auctions
José Soto, Victor Verdugo
In the online 2-bounded auction problem, we have a collection of items represented as nodes in a graph and bundles of size two represented by edges. Agents are presented sequential…
Optimal Guarantees for Online Selection Over Time
Sebastian Perez-Salazar, Victor Verdugo
Prophet inequalities are a cornerstone in optimal stopping and online decision-making. Traditionally, they involve the sequential observation of non-negative independent random…
Splitting Guarantees for Prophet Inequalities via Nonlinear Systems
Johannes Brustle, Sebastian Perez-Salazar, Victor Verdugo
The prophet inequality is one of the cornerstone problems in optimal stopping theory and has become a crucial tool for designing sequential algorithms in Bayesian settings. In the…
The Competition Complexity of Prophet Inequalities
Johannes Brustle, José Correa, Paul Dütting +3
We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the -competition complexity of different t…
Online Combinatorial Assignment in Independence Systems
Javier Marinkovic, José A. Soto, Victor Verdugo
We consider an online multi-weighted generalization of several classic online optimization problems, called the online combinatorial assignment problem. We are given an independenc…