5 papers
Random Serial Dictatorship is -Envy-Free
Frank Connor, Max Dupré la Tour, Louis-Roy Langevin +4
We analyze the house allocation problem, in which a set of agents must be matched to a set of objects for which they have cardinal utilities. A central mechanism for this problem i…
On Mobile Ad Hoc Networks for Coverage of Partially Observable Worlds
Edwin Meriaux, Shuo Wen, Louis-Roy Langevin +3
This paper addresses the movement and placement of mobile agents to establish a communication network in initially unknown environments. We cast the problem in a computational-geom…
Optimally revealing bits for rejection sampling
Louis-Roy Langevin, Alex Waese-Perlman
Rejection sampling is a popular method used to generate numbers that follow some given distribution. We study the use of this method to generate random numbers in the unit interval…
The Popular Dimension of Matchings
Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye +3
We study popular matchings in three classical settings: the house allocation problem, the marriage problem, and the roommates problem. In the popular matching problem, (a subset of…
Optimal root recovery for uniform attachment trees and -regular growing trees
Louigi Addario-Berry, Catherine Fontaine, Robin Khanfir +2
We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy , such an algori…