Noticias en español
From 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 MoreRawlsian Assignments.
Abstract: We study the assignment of indivisible objects to individuals when transfers are not allowed. Previous literature has mainly focused on efficiency (from ex-ante and ex-post perspectives), and individually fair assignments. Consequently, egalitarian concerns have been overlooked. We are inspired by the assignment of apartments in housing cooperatives where families regard the egalitarianism of the assignments as a first-order requirement. In particular, they want to avoid assignments where some families get their most preferred apartment, while others get options ranked very low in...
Read MoreToward Elimination of Infectious Diseases with Mobile Screening Teams: HAT in the DRC.
Abstract: In pursuit of Sustainable Development Goal 3 “Ensure healthy lives and promote well-being for all at all ages,” considerable global effort is directed toward elimination of infectious diseases in general and Neglected Tropical Diseases in particular. For various such diseases, the deployment of mobile screening teams forms an important instrument to reduce prevalence toward elimination targets. There is considerable variety in planning methods for the deployment of these mobile teams in practice, but little understanding of their effectiveness. Moreover, there appears to be little...
Read MoreRecursive local amoeba construction.
Abstract: Amoeba graphs were born as examples of balanceable graphs, which are graphs that appear in any 2-edge coloring of the edges of a large enough $K_n$ with a sufficient amount of red and blue edges. As they were studied further, interesting aspects were found. An edge replacement $e\to e$ in a labeled graph G means to take an edge e in E(G) and replace it with e’ \in E(\overline{G})\cup \{e\}$. If $G-e+e’$ is isomorphic to $G$ then we say $e\to e’$ is a \emph{feasible edge replacement}. Every edge replacement yields a set of permutations of the labels in $G$. The set...
Read More