enter search term and/or author name
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani
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
We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. , 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
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
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
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,...