enter search term and/or author name
Dynamic Facility Location via Exponential Clocks
Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson
Article No.: 21
The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in...
On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
Article No.: 22
In this article, we study the uniform capacitated k-median (CKM) problem. In the problem, we are given a set F of potential facility locations, a set C of clients, a metric d over F ∪ C, an upper bound...
Section: Special Issue on SODA'15
Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation
Axel Bacher, Olivier Bodini, Hsien-Kuei Hwang, Tsung-Hsi Tsai
Article No.: 24
Several simple, classical, little-known algorithms in the statistics and computer science literature for generating random permutations by coin tossing are examined, analyzed, and implemented. These algorithms are either asymptotically optimal or...