Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 52 Issue 4, July 2005

An in-place sorting with O(nlog n) comparisons and O(n) moves
Gianni Franceschini, Viliam Geffert
Pages: 515-537
DOI: 10.1145/1082036.1082037
We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(nlog n) element comparisons and O(n) element transports.This solves a long-standing open...

Asymmetric k-center is log* n-hard to approximate
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph (Seffi) Naor
Pages: 538-551
DOI: 10.1145/1082036.1082038
In the ASYMMETRIC k-CENTER problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to...

Indexing compressed text
Paolo Ferragina, Giovanni Manzini
Pages: 552-581
DOI: 10.1145/1082036.1082039
We design two compressed data structures for the full-text indexing problem that support efficient substring searches using roughly the space required for storing the text in compressed form.Our first compressed data structure retrieves the...

Source routing and scheduling in packet networks
Matthew Andrews, Antonio Fernández, Ashish Goel, Lisa Zhang
Pages: 582-601
DOI: 10.1145/1082036.1082040
We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in...

Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko
Pages: 602-626
DOI: 10.1145/1082036.1082041
A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem, one can represent such a multigraph as a combination of at most n2 cycle covers, each taken...

Remote attribute grammars
John Tang Boyland
Pages: 627-687
DOI: 10.1145/1082036.1082042
Describing the static semantics of programming languages with attribute grammars is eased when the formalism allows direct dependencies to be induced between rules for nodes arbitrarily far away in the tree. Such direct non-local dependencies...

Boosting textual compression in optimal linear time
Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini, Marinella Sciortino
Pages: 688-713
DOI: 10.1145/1082036.1082043
We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable...