Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 13 Issue 2, February 2017

Section: Special Issue on SODA'15

Dynamic Facility Location via Exponential Clocks
Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson
Article No.: 21
DOI: 10.1145/2928272

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
Shi Li
Article No.: 22
DOI: 10.1145/2983633

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 FC, 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
DOI: 10.1145/3009909

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...