Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 50 Issue 6, November 2003

Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani
Pages: 795-824
DOI: 10.1145/950620.950621
In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation...

Improving table compression with combinatorial optimization
Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo
Pages: 825-851
DOI: 10.1145/950620.950622
We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [2000], in which a table is partitioned by an off-line training procedure into disjoint intervals of columns, each of which is...

Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998
Cynthia Dwork, Moni Naor, Omer Reingold, Larry Stockmeyer
Pages: 852-921
DOI: 10.1145/950620.950623
We prove that three apparently unrelated fundamental problems in distributed computing, cryptography, and complexity theory, are essentially the same problem. These three problems and brief descriptions of them follow. (1) The selective...

Conditions on input vectors for consensus solvability in asynchronous distributed systems
Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal
Pages: 922-954
DOI: 10.1145/950620.950624
This article introduces and explores the condition-based approach to solve the consensus problem in asynchronous systems. The approach studies conditions that identify sets of input vectors for which it is possible to solve consensus...

On the generating sequences of regular languages on k symbols
Marie-Pierre Béal, Dominique Perrin
Pages: 955-980
DOI: 10.1145/950620.950625
The main result is a characterization of the generating sequences of the length of words in a regular language on k symbols. We say that a sequence s of integers is regular if there is a finite graph G with two vertices i,...