enter search term and/or author name
An in-place sorting with O(nlog n) comparisons and O(n) moves
Gianni Franceschini, Viliam Geffert
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
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
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
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
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
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
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...