2 citations · 4 across the 8 of their papers we have counts for
11 papers
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time
Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ra…
Optimal Revenue Guarantees for Pricing in Large Markets
José Correa, Dana Pizarro, Victor Verdugo
Posted price mechanisms (PPM) constitute one of the predominant practices to price goods in online marketplaces and their revenue guarantees have been a central object of study in…
Apportionment with Parity Constraints
Claire Mathieu, Victor Verdugo
In the classic apportionment problem the goal is to decide how many seats of a parliament should be allocated to each party as a result of an election. The divisor methods provide…
The Convergence Rates of Blockchain Mining Games: A Markovian Approach
Alejandro Jofré, Angel Pardo, David Salas +2
Understanding the strategic behavior of miners in a blockchain is of great importance for its proper operation. A common model for mining games considers an infinite time horizon,…
Preserving Diversity when Partitioning: A Geometric Approach
Sebastian Perez-Salazar, Alfredo Torrico, Victor Verdugo
Diversity plays a crucial role in multiple contexts such as team formation, representation of minority groups and generally when allocating resources fairly. Given a community comp…
On the extension complexity of scheduling
Hans Raj Tiwary, Victor Verdugo, Andreas Wiese
Linear programming is a powerful method in combinatorial optimization with many applications in theory and practice. For solving a linear program quickly it is desirable to have a…
Breaking symmetries to rescue Sum of Squares in the case of makespan scheduling
Victor Verdugo, José Verschae, Andreas Wiese
The Sum of Squares (\sos{}) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for…
Strong Algorithms for the Ordinal Matroid Secretary Problem
José A. Soto, Abner Turkieltaub, Victor Verdugo
In the ordinal Matroid Secretary Problem (MSP), elements from a weighted matroid are presented in random order to an algorithm that must incrementally select a large weight indepen…
Skyline Computation with Noisy Comparisons
Benoît Groz, Frederik Mallmann-Trenn, Claire Mathieu +1
Given a set of points in a -dimensional space, we seek to compute the skyline, i.e., those points that are not strictly dominated by any other point, using few comparisons b…
How large is your graph?
Varun Kanade, Frederik Mallmann-Trenn, Victor Verdugo
We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a \emph{seed} nod…
Split Scheduling with Uniform Setup Times
Frans Schalekamp, Rene Sitters, Suzanne van der Ster +3
We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job req…