Noticias en español
Competition and Recall in Selection Problems.
Abstract: In this talk, I will present an extension of the prophet inequality problem to a competitive setting. At every period, a new sample from a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random). As soon as a player gets one sample, he leaves the market, and his payoff is the value of the sample. In a first variant, namely no recall case, the agents can only bid in each period for the current value. In a second variant, the full...
Read MoreGeneralized formulations for the traveling salesman problem.
Abstract: The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ) formulation. First, we argue that the choice of some parameters of this formulation is arbitrary and, therefore, there is a family of formulations of which MTZ is a particular case. We analyze this family, noting that in general the formulations involved are not comparable to each other and there is no one that dominates the rest. Then, we study the intersection of this family, which we...
Read MoreImpartial Selection with Additive Guarantees via Iterated Deletion.
Abstract: Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\gamma)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\gamma})$ nominations, where $\gamma \in [0,1]$. For $\gamma=0$, i.e., when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized...
Read MoreFrom Combinatorial Optimization to Combinatorial Generation.
Abstract: We propose a new simple general approach for combinatorial generation. Given some binary strings X⊆{0,1}ⁿ, our approach consists of greedily computing a Hamilton path in a polytope with X as vertices, namely conv(X). Our main result shows that this approach works for all X⊆{0,1}ⁿ and is efficient whenever optimization over X can be efficiently solved, showing an unexplored relation between combinatorial optimization and generation. More specifically, if we can solve certain linear optimization problems for X in time O(T), we can compute a Hamilton path in conv(X) in roughly...
Read MoreConstant-depth sorting networks.
Abstract: Assume that you want to sort n integers, and you have many copies of a device that can sort k integers. At one step, you can partition n integers into sets of size at most k by putting them into your devices. How many such steps do you need to sort your initial array? When k = 2, this problem is just a problem of constructing a sorting network. It can be solved in O(log n) steps, though the construction is complicated and impractical. We consider a reversed setting. Namely, we fix a number of steps and seek for the minimal k such that our problem is solvable within this number of...
Read MoreReconstruction of token graphs.
Abstract: Let $G$ be a graph of order $n\ge 2$, and let $k$ be an integer with $k\in \{1,2,\dots,n-1\}$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are all the $k$-subsets of vertices of $G$, and two of such $k$-subsets are adjacent whenever their symmetric difference is an edge of $G$. We denote by $C_4$ the $4$-cycle and by $D_4$ the diamond graph (a $4$-cycle with a chord). We say that $G$ is a $(C_4,D_4)$-free graph if $G$ does not contain $C_4$ nor $D_4$ as a subgraph. In 2012 Fabila-Monroy et al. conjectured the following: If $G$ and $H$ are two graphs such that...
Read More