2 citations · 4 across the 8 of their papers we have counts for
7 papers · 1 filter
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…
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…