%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.05",
%%% date = "16 June 2008",
%%% time = "11:58:33 MDT",
%%% filename = "talg.bib",
%%% address = "University of Utah
%%% Department of Mathematics, 110 LCB
%%% 155 S 1400 E RM 233
%%% Salt Lake City, UT 84112-0090
%%% USA",
%%% telephone = "+1 801 581 5254",
%%% FAX = "+1 801 581 4148",
%%% URL = "http://www.math.utah.edu/~beebe",
%%% checksum = "07065 4183 21630 188347",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at computer.org (Internet)",
%%% codetable = "ISO/ASCII",
%%% keywords = "ACM Transactions on Algorithms; bibliography;
%%% TALG",
%%% license = "public domain",
%%% supported = "yes",
%%% docstring = "This is a COMPLETE BibTeX bibliography for
%%% ACM Transactions on Algorithms (CODEN ????,
%%% ISSN 1549-6325), covering all journal issues
%%% from 2005 -- date.
%%%
%%% At version 1.05, the COMPLETE journal
%%% coverage looked like this:
%%%
%%% 2005 ( 20) 2007 ( 52)
%%% 2006 ( 37) 2008 ( 24)
%%%
%%% Article: 133
%%%
%%% Total entries: 133
%%%
%%% The journal Web page can be found at:
%%%
%%% http://www.acm.org/pubs/taco.html
%%%
%%% The journal table of contents page is at:
%%%
%%% http://www.acm.org/talg/
%%% http://portal.acm.org/browse_dl.cfm?linked=1&part=periodical&idx=J982
%%%
%%% Qualified subscribers can retrieve the full
%%% text of recent articles in PDF form.
%%%
%%% The initial draft was extracted from the ACM
%%% Web pages.
%%%
%%% ACM copyrights explicitly permit abstracting
%%% with credit, so article abstracts, keywords,
%%% and subject classifications have been
%%% included in this bibliography wherever
%%% available. Article reviews have been
%%% omitted, until their copyright status has
%%% been clarified.
%%%
%%% bibsource keys in the bibliography entries
%%% below indicate the entry originally came
%%% from the computer science bibliography
%%% archive, even though it has likely since
%%% been corrected and updated.
%%%
%%% URL keys in the bibliography point to
%%% World Wide Web locations of additional
%%% information about the entry.
%%%
%%% BibTeX citation tags are uniformly chosen
%%% as name:year:abbrev, where name is the
%%% family name of the first author or editor,
%%% year is a 4-digit number, and abbrev is a
%%% 3-letter condensation of important title
%%% words. Citation tags were automatically
%%% generated by software developed for the
%%% BibNet Project.
%%%
%%% In this bibliography, entries are sorted in
%%% publication order, using ``bibsort -byvolume.''
%%%
%%% The checksum field above contains a CRC-16
%%% checksum as the first value, followed by the
%%% equivalent of the standard UNIX wc (word
%%% count) utility output of lines, words, and
%%% characters. This is produced by Robert
%%% Solovay's checksum utility.",
%%% }
%%% ====================================================================
@Preamble{"\input bibnames.sty"}
%%% ====================================================================
%%% Acknowledgement abbreviations:
@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
%%% ====================================================================
%%% Journal abbreviations:
@String{j-TALG = "ACM Transactions on Algorithms"}
%%% ====================================================================
%%% Bibliography entries:
@Article{Gabow:2005:EF,
author = "Harold N. Gabow",
title = "{Editor}'s foreword",
journal = j-TALG,
volume = "1",
number = "1",
pages = "1--1",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Yuster:2005:FSM,
author = "Raphael Yuster and Uri Zwick",
title = "Fast sparse matrix multiplication",
journal = j-TALG,
volume = "1",
number = "1",
pages = "2--13",
month = jul,
year = "2005",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1077464.1077466",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
abstract = "Let $A$ and $B$ be two $n \times n$ matrices over a
ring $R$ (e.g., the reals or the integers) each
containing at most $m$ nonzero elements. We present a
new algorithm that multiplies $A$ and $B$ using
$O(m^{0.7}n^{1.2} + n^2 + o(1))$ algebraic operations
(i.e., multiplications, additions and subtractions)
over $R$. The na{\"\i}ve matrix multiplication
algorithm, on the other hand, may need to perform
$\Omega(mn)$ operations to accomplish the same task.
For $m \leq n^{1.14}$, the new algorithm performs an
almost optimal number of only $n^2 + o(1)$ operations.
For $m \leq n^{1.68}$, the new algorithm is also faster
than the best known matrix multiplication algorithm for
dense matrices which uses $O(n^{2.38})$ algebraic
operations. The new algorithm is obtained using a
surprisingly straightforward combination of a simple
combinatorial idea and existing fast rectangular matrix
multiplication algorithms. We also obtain improved
algorithms for the multiplication of more than two
sparse matrices. As the known fast rectangular matrix
multiplication algorithms are far from being practical,
our result, at least for now, is only of theoretical
value.",
acknowledgement = ack-nhfb,
}
@Article{Edmonds:2005:MAL,
author = "Jeff Edmonds and Kirk Pruhs",
title = "A maiden analysis of longest wait first",
journal = j-TALG,
volume = "1",
number = "1",
pages = "14--32",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Demaine:2005:FPA,
author = "Erik D. Demaine and Fedor V. Fomin and Mohammadtaghi
Hajiaghayi and Dimitrios M. Thilikos",
title = "Fixed-parameter algorithms for $(k, r)$-center in
planar graphs and map graphs",
journal = j-TALG,
volume = "1",
number = "1",
pages = "33--47",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Adler:2005:PMM,
author = "Micah Adler and Dan Rubenstein",
title = "Pricing multicasting in more flexible network models",
journal = j-TALG,
volume = "1",
number = "1",
pages = "48--73",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Even:2005:NDP,
author = "Guy Even and Guy Kortsarz and Wolfgang Slany",
title = "On network design problems: fixed cost flows and the
covering {Steiner} problem",
journal = j-TALG,
volume = "1",
number = "1",
pages = "74--101",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Alstrup:2005:BBC,
author = "Stephen Alstrup and Thore Husfeldt and Theis Rauhe and
Mikkel Thorup",
title = "Black box for constant-time insertion in priority
queues (note)",
journal = j-TALG,
volume = "1",
number = "1",
pages = "102--106",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Vinkemeier:2005:LTA,
author = "Doratha E. Drake Vinkemeier and Stefan Hougardy",
title = "A linear-time approximation algorithm for weighted
matchings in graphs",
journal = j-TALG,
volume = "1",
number = "1",
pages = "107--122",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Grabner:2005:ALC,
author = "Peter J. Grabner and Clemens Heuberger and Helmut
Prodinger and J{\"o}rg M. Thuswaldner",
title = "Analysis of linear combination algorithms in
cryptography",
journal = j-TALG,
volume = "1",
number = "1",
pages = "123--142",
month = jul,
year = "2005",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1077464.1077473",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
abstract = "Several cryptosystems rely on fast calculations of
linear combinations in groups. One way to achieve this
is to use joint signed binary digit expansions of small
``weight.'' We study two algorithms, one based on
nonadjacent forms of the coefficients of the linear
combination, the other based on a certain joint sparse
form specifically adapted to this problem. Both methods
are sped up using the sliding windows approach combined
with precomputed lookup tables. We give explicit and
asymptotic results for the number of group operations
needed, assuming uniform distribution of the
coefficients. Expected values, variances and a central
limit theorem are proved using generating functions.
Furthermore, we provide a new algorithm that calculates
the digits of an optimal expansion of pairs of integers
from left to right. This avoids storing the whole
expansion, which is needed with the previously known
right-to-left methods, and allows an online
computation.",
acknowledgement = ack-nhfb,
}
@Article{Cechlarova:2005:GSR,
author = "Katar{\'\i}na Cechl{\'a}rov{\'a} and Tam{\'a}s
Fleiner",
title = "On a generalization of the stable roommates problem",
journal = j-TALG,
volume = "1",
number = "1",
pages = "143--156",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Khuller:2005:PC,
author = "Samir Khuller",
title = "Problems column",
journal = j-TALG,
volume = "1",
number = "1",
pages = "157--159",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Johnson:2005:NCC,
author = "David S. Johnson",
title = "The {NP}-completeness column",
journal = j-TALG,
volume = "1",
number = "1",
pages = "160--176",
month = jul,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:55 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Janson:2005:IDL,
author = "Svante Janson",
title = "Individual displacements for linear probing hashing
with different insertion policies",
journal = j-TALG,
volume = "1",
number = "2",
pages = "177--213",
month = oct,
year = "2005",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1103963.1103964",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
abstract = "We study the distribution of the individual
displacements in hashing with linear probing for three
different versions: First Come, Last Come and Robin
Hood. Asymptotic distributions and their moments are
found when the the size of the hash table tends to
infinity with the proportion of occupied cells
converging to some $\alpha$, $0 < \alpha < 1$. (In the
case of Last Come, the results are more complicated and
less complete than in the other cases.) We also show,
using the diagonal Poisson transform studied by
Poblete, Viola and Munro, that exact expressions for
finite $m$ and $n$ can be obtained from the limits as
$m,n \rightarrow \infty$. We end with some results,
conjectures and questions about the shape of the limit
distributions. These have some relevance for computer
applications.",
acknowledgement = ack-nhfb,
}
@Article{Viola:2005:EDI,
author = "Alfredo Viola",
title = "Exact distribution of individual displacements in
linear probing hashing",
journal = j-TALG,
volume = "1",
number = "2",
pages = "214--242",
month = oct,
year = "2005",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1103963.1103965",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
abstract = "This paper studies the distribution of individual
displacements for the standard and the Robin Hood
linear probing hashing algorithms. When a table of size
$m$ has $n$ elements, the distribution of the search
cost of a random element is studied for both
algorithms. Specifically, exact distributions for fixed
$m$ and $n$ are found as well as when the table is
$\alpha$-full, and $\alpha$ strictly smaller than 1.
Moreover, for full tables, limit laws for both
algorithms are derived.",
acknowledgement = ack-nhfb,
}
@Article{Alstrup:2005:MIF,
author = "Stephen Alstrup and Jacob Holm and Mikkel Thorup and
Kristian De Lichtenberg",
title = "Maintaining information in fully dynamic trees with
top trees",
journal = j-TALG,
volume = "1",
number = "2",
pages = "243--264",
month = oct,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Jothi:2005:AAC,
author = "Raja Jothi and Balaji Raghavachari",
title = "Approximation algorithms for the capacitated minimum
spanning tree problem and its variants in network
design",
journal = j-TALG,
volume = "1",
number = "2",
pages = "265--282",
month = oct,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Elkin:2005:CAS,
author = "Michael Elkin",
title = "Computing almost shortest paths",
journal = j-TALG,
volume = "1",
number = "2",
pages = "283--323",
month = oct,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Carvalho:2005:VAE,
author = "Marcelo H. De Carvalho and Joseph Cheriyan",
title = "An {$O(VE)$} algorithm for ear decompositions of
matching-covered graphs",
journal = j-TALG,
volume = "1",
number = "2",
pages = "324--337",
month = oct,
year = "2005",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1103963.1103969",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Goel:2005:AMF,
author = "Ashish Goel and Adam Meyerson and Serge Plotkin",
title = "Approximate majorization and fair online load
balancing",
journal = j-TALG,
volume = "1",
number = "2",
pages = "338--349",
month = oct,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Chrobak:2005:GAM,
author = "Marek Chrobak and Petr Kolman and Ji{\v{r}}{\'\i}
Sgall",
title = "The greedy algorithm for the minimum common string
partition problem",
journal = j-TALG,
volume = "1",
number = "2",
pages = "350--366",
month = oct,
year = "2005",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Tue Dec 13 18:19:56 MST 2005",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Sawada:2006:GRF,
author = "Joe Sawada",
title = "Generating rooted and free plane trees",
journal = j-TALG,
volume = "2",
number = "1",
pages = "1--13",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Hegde:2006:FSE,
author = "Rajneesh Hegde",
title = "Finding $3$-shredders efficiently",
journal = j-TALG,
volume = "2",
number = "1",
pages = "14--43",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Gramm:2006:PMA,
author = "Jens Gramm and Jiong Guo and Rolf Niedermeier",
title = "Pattern matching for arc-annotated sequences",
journal = j-TALG,
volume = "2",
number = "1",
pages = "44--65",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Hassin:2006:MGV,
author = "Refael Hassin and Asaf Levin",
title = "The minimum generalized vertex cover problem",
journal = j-TALG,
volume = "2",
number = "1",
pages = "66--78",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Epstein:2006:OSS,
author = "Leah Epstein and Rob Van Stee",
title = "Online scheduling of splittable tasks",
journal = j-TALG,
volume = "2",
number = "1",
pages = "79--94",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Gonzalez:2006:MTC,
author = "Teofilo F. Gonzalez and Joseph Y.-T. Leung and Michael
Pinedo",
title = "Minimizing total completion time on uniform machines
with deadline constraints",
journal = j-TALG,
volume = "2",
number = "1",
pages = "95--115",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Gandhi:2006:IRD,
author = "Rajiv Gandhi and Magn{\'u}s M. Halld{\'o}rsson and Guy
Kortsarz and Hadas Shachnai",
title = "Improved results for data migration and open shop
scheduling",
journal = j-TALG,
volume = "2",
number = "1",
pages = "116--129",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Khuller:2006:PC,
author = "Samir Khuller",
title = "Problems column",
journal = j-TALG,
volume = "2",
number = "1",
pages = "130--134",
month = jan,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Fri May 26 08:40:43 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Korsh:2006:LGC,
author = "James Korsh and Paul Lafollette",
title = "A loopless {Gray} code for rooted trees",
journal = j-TALG,
volume = "2",
number = "2",
pages = "135--152",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Alon:2006:ACS,
author = "Noga Alon and Dana Moshkovitz and Shmuel Safra",
title = "Algorithmic construction of sets for {$k$}-restrictions",
journal = j-TALG,
volume = "2",
number = "2",
pages = "153--177",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Lau:2006:BRG,
author = "Lap Chi Lau",
title = "Bipartite roots of graphs",
journal = j-TALG,
volume = "2",
number = "2",
pages = "178--208",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Agarwal:2006:EAB,
author = "Pankaj K. Agarwal and Boris Aronov and Vladlen Koltun",
title = "Efficient algorithms for bichromatic separability",
journal = j-TALG,
volume = "2",
number = "2",
pages = "209--227",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Epstein:2006:SU,
author = "Leah Epstein and Rob Van Stee",
title = "This side up!",
journal = j-TALG,
volume = "2",
number = "2",
pages = "228--243",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Huo:2006:MMF,
author = "Yumei Huo and Joseph Y.-T. Leung",
title = "Minimizing mean flow time for {UET} tasks",
journal = j-TALG,
volume = "2",
number = "2",
pages = "244--262",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Hassin:2006:RST,
author = "Refael Hassin and Danny Segev",
title = "Robust subgraphs for trees and paths",
journal = j-TALG,
volume = "2",
number = "2",
pages = "263--281",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Azar:2006:IAC,
author = "Yossi Azar and Yossi Richter",
title = "An improved algorithm for {CIOQ} switches",
journal = j-TALG,
volume = "2",
number = "2",
pages = "282--295",
month = apr,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Wed Aug 23 05:38:18 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Berend:2006:CMP,
author = "Daniel Berend and Amir Sapir",
title = "The cyclic multi-peg {Tower of Hanoi}",
journal = j-TALG,
volume = "2",
number = "3",
pages = "297--317",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Drmota:2006:RFA,
author = "Michael Drmota and Helmut Prodinger",
title = "The register function for $t$-ary trees",
journal = j-TALG,
volume = "2",
number = "3",
pages = "318--334",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Kowalik:2006:OBL,
author = "Lukasz Kowalik and Maciej Kurowski",
title = "Oracles for bounded-length shortest paths in planar
graphs",
journal = j-TALG,
volume = "2",
number = "3",
pages = "335--363",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Katriel:2006:OTO,
author = "Irit Katriel and Hans L. Bodlaender",
title = "Online topological ordering",
journal = j-TALG,
volume = "2",
number = "3",
pages = "364--379",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Duncan:2006:OCG,
author = "Christian A. Duncan and Stephen G. Kobourov and V. S.
Anil Kumar",
title = "Optimal constrained graph exploration",
journal = j-TALG,
volume = "2",
number = "3",
pages = "380--402",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Raman:2006:FFP,
author = "Venkatesh Raman and Saket Saurabh and C. R.
Subramanian",
title = "Faster fixed parameter tractable algorithms for
finding feedback vertex sets",
journal = j-TALG,
volume = "2",
number = "3",
pages = "403--415",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Jansen:2006:AAS,
author = "Klaus Jansen and Hu Zhang",
title = "An approximation algorithm for scheduling malleable
tasks under general precedence constraints",
journal = j-TALG,
volume = "2",
number = "3",
pages = "416--434",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Feigenbaum:2006:SMC,
author = "Joan Feigenbaum and Yuval Ishai and Tal Malkin and
Kobbi Nissim and Martin J. Strauss and Rebecca N.
Wright",
title = "Secure multiparty computation of approximations",
journal = j-TALG,
volume = "2",
number = "3",
pages = "435--472",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Johnson:2006:NCC,
author = "David S. Johnson",
title = "The {NP}-completeness column: {The} many limits on
approximation",
journal = j-TALG,
volume = "2",
number = "3",
pages = "473--489",
month = jul,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Thu Sep 21 08:13:30 MDT 2006",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Lopez-Ortiz:2006:F,
author = "Alejandro L{\'o}pez-Ortiz and J. Ian Munro",
title = "Foreword",
journal = j-TALG,
volume = "2",
number = "4",
pages = "491--491",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Eppstein:2006:QAM,
author = "David Eppstein",
title = "Quasiconvex analysis of multivariate recurrence
equations for backtracking algorithms",
journal = j-TALG,
volume = "2",
number = "4",
pages = "492--509",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Geary:2006:SOT,
author = "Richard F. Geary and Rajeev Raman and Venkatesh
Raman",
title = "Succinct ordinal trees with level-ancestor queries",
journal = j-TALG,
volume = "2",
number = "4",
pages = "510--534",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Mendelson:2006:MPQ,
author = "Ran Mendelson and Robert E. Tarjan and Mikkel Thorup
and Uri Zwick",
title = "Melding priority queues",
journal = j-TALG,
volume = "2",
number = "4",
pages = "535--556",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Baswana:2006:ADO,
author = "Surender Baswana and Sandeep Sen",
title = "Approximate distance oracles for unweighted graphs in
expected {$O(n^2)$} time",
journal = j-TALG,
volume = "2",
number = "4",
pages = "557--577",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Demetrescu:2006:EAD,
author = "Camil Demetrescu and Giuseppe F. Italiano",
title = "Experimental analysis of dynamic all pairs shortest
path algorithms",
journal = j-TALG,
volume = "2",
number = "4",
pages = "578--601",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Irving:2006:RMM,
author = "Robert W. Irving and Telikepalli Kavitha and Kurt
Mehlhorn and Dimitrios Michail and Katarzyna E.
Paluch",
title = "Rank-maximal matchings",
journal = j-TALG,
volume = "2",
number = "4",
pages = "602--610",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Foschini:2006:WIE,
author = "Luca Foschini and Roberto Grossi and Ankur Gupta and
Jeffrey Scott Vitter",
title = "When indexing equals compression: {Experiments} with
compressing suffix arrays and applications",
journal = j-TALG,
volume = "2",
number = "4",
pages = "611--639",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Alon:2006:GAO,
author = "Noga Alon and Baruch Awerbuch and Yossi Azar and Niv
Buchbinder and Joseph (Seffi) Naor",
title = "A general approach to online network optimization
problems",
journal = j-TALG,
volume = "2",
number = "4",
pages = "640--660",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Evans:2006:OSV,
author = "William Evans and David Kirkpatrick",
title = "Optimally scheduling video-on-demand to minimize delay
when sender and receiver bandwidth may differ",
journal = j-TALG,
volume = "2",
number = "4",
pages = "661--678",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Beier:2006:CES,
author = "Rene Beier and Artur Czumaj and Piotr Krysta and
Berthold V{\"o}cking",
title = "Computing equilibria for a service provider game with
(Im)perfect information",
journal = j-TALG,
volume = "2",
number = "4",
pages = "679--706",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Moore:2006:GQF,
author = "Cristopher Moore and Daniel Rockmore and Alexander
Russell",
title = "Generic quantum {Fourier} transforms",
journal = j-TALG,
volume = "2",
number = "4",
pages = "707--723",
month = oct,
year = "2006",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
}
@Article{Archer:2007:FPM,
author = "Aaron Archer and {\'E}va Tardos",
title = "Frugal path mechanisms",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "3",
}
@Article{Bhatia:2007:AAB,
author = "Randeep Bhatia and Julia Chuzhoy and Ari Freund and
Joseph (Seffi) Naor",
title = "Algorithmic aspects of bandwidth trading",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "10",
}
@Article{Carmo:2007:QPI,
author = "Renato Carmo and Tom{\'a}s Feder and Yoshiharu
Kohayakawa and Eduardo Laber and Rajeev Motwani and
Liadan O'Callaghan and Rina Panigrahy and Dilys
Thomas",
title = "Querying priced information in databases: {The}
conjunctive case",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "9",
}
@Article{Ciriani:2007:DSS,
author = "Valentina Ciriani and Paolo Ferragina and Fabrizio
Luccio and S. Muthukrishnan",
title = "A data structure for a sequence of string accesses in
external memory",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "6",
}
@Article{Cormode:2007:SED,
author = "Graham Cormode and S. Muthukrishnan",
title = "The string edit distance matching problem with moves",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
abstract = "The edit distance between two strings $S$ and $R$ is
defined to be the minimum number of character inserts,
deletes, and changes needed to convert $R$ to S. Given
a text string $t$ of length $n$, and a pattern string
$p$ of length $m$, informally, the string edit distance
matching problem is to compute the smallest edit
distance between $p$ and substrings of $t$. We relax
the problem so that: (a) we allow an additional
operation, namely, substring moves; and (b) we allow
approximation of this string edit distance. Our result
is a near-linear time deterministic algorithm to
produce a factor of $O(\log n \log\star n)$
approximation to the string edit distance with moves.
This is the first known significantly subquadratic
algorithm for a string edit distance problem in which
the distance involves nontrivial alignments. Our
results are obtained by embedding strings into $L_1$
vector space using a simplified parsing technique,
which we call edit-sensitive parsing (ESP).",
acknowledgement = ack-nhfb,
articleno = "2",
}
@Article{Czumaj:2007:TBW,
author = "Artur Czumaj and Berthold V{\"o}cking",
title = "Tight bounds for worst-case equilibria",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "4",
}
@Article{Elkin:2007:IAR,
author = "Michael Elkin and Guy Kortsarz",
title = "An improved algorithm for radio broadcast",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "8",
}
@Article{Eppstein:2007:FSI,
author = "David Eppstein",
title = "Foreword to special issue on {SODA 2002}",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "1",
}
@Article{Hershberger:2007:DSS,
author = "John Hershberger and Subhash Suri and Amit Bhosle",
title = "On the difficulty of some shortest path problems",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "5",
}
@Article{Pandurangan:2007:EBB,
author = "Gopal Pandurangan and Eli Upfal",
title = "Entropy-based bounds for online algorithms",
journal = j-TALG,
volume = "3",
number = "1",
pages = "??--??",
month = feb,
year = "2007",
CODEN = "????",
ISSN = "1549-6325",
bibdate = "Sat Apr 14 10:58:14 MDT 2007",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "7",
}
@Article{Voronenko:2007:MMC,
author = "Yevgen Voronenko and Markus P{\"u}schel",
title = "Multiplierless multiple constant multiplication",
journal = j-TALG,
volume = "3",
number = "2",
pages = "11:1--11:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240234",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "A variable can be multiplied by a given set of
fixed-point constants using a multiplier block that
consists exclusively of additions, subtractions, and
shifts. The generation of a multiplier block from the
set of constants is known as the multiple constant
multiplication (MCM) problem. Finding the optimal
solution, namely, the one with the fewest number of
additions and subtractions, is known to be NP-complete.
We propose a new algorithm for the MCM problem, which
produces solutions that require up to 20\% less
additions and subtractions than the best previously
known algorithm. At the same time our algorithm, in
contrast to the closest competing algorithm, is not
limited by the constant bitwidths. We present our
algorithm using a unifying formal framework for the
best, graph-based MCM algorithms and provide a detailed
runtime analysis and experimental evaluation. We show
that our algorithm can handle problem sizes as large as
100 32-bit constants in a time acceptable for most
applications. The implementation of the new algorithm
is available at \url{www.spiral.net}.",
acknowledgement = ack-nhfb,
articleno = "11",
keywords = "Addition chains; directed graph; FIR filter;
fixed-point arithmetic; strength reduction",
}
@Article{Chern:2007:PCR,
author = "Hua-Huai Chern and Michael Fuchs and Hsien-Kuei
Hwang",
title = "Phase changes in random point quadtrees",
journal = j-TALG,
volume = "3",
number = "2",
pages = "12:1--12:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240235",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We show that a wide class of linear cost measures
(such as the number of leaves) in random
$d$-dimensional point quadtrees undergo a change in
limit laws: If the dimension $d = 1, \ldots, 8$, then
the limit law is normal; if $d \geq 9$ then there is no
convergence to a fixed limit law. Stronger
approximation results such as convergence rates and
local limit theorems are also derived for the number of
leaves, additional phase changes being unveiled. Our
approach is new and very general, and also applicable
to other classes of search trees. A brief discussion of
Devroye's grid trees (covering $m$-ary search trees and
quadtrees as special cases) is given. We also propose
an efficient numerical procedure for computing the
constants involved to high precision.",
acknowledgement = ack-nhfb,
articleno = "12",
keywords = "analysis in distribution of algorithms; Asymptotic
transfer; central limit theorems; depth; differential
equations; grid trees; local limit theorems; Mellin
transforms; page usage; phase transitions; quadtrees;
total path length",
}
@Article{Demaine:2007:RDS,
author = "Erik D. Demaine and John Iacono and Stefan Langerman",
title = "Retroactive data structures",
journal = j-TALG,
volume = "3",
number = "2",
pages = "13:1--13:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240236",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We introduce a new data structuring paradigm in which
operations can be performed on a data structure not
only in the present, but also in the past. In this new
paradigm, called retroactive data structures, the
historical sequence of operations performed on the data
structure is not fixed. The data structure allows
arbitrary insertion and deletion of operations at
arbitrary times, subject only to consistency
requirements. We initiate the study of retroactive data
structures by formally defining the model and its
variants. We prove that, unlike persistence, efficient
retroactivity is not always achievable. Thus, we
present efficient retroactive data structures for
queues, doubly ended queues, priority queues,
union-find, and decomposable search structures.",
acknowledgement = ack-nhfb,
articleno = "13",
keywords = "History; persistence; point location; rollback; time
travel",
}
@Article{Hayward:2007:IAW,
author = "Ryan B. Hayward and Jeremy P. Spinrad and R.
Sritharan",
title = "Improved algorithms for weakly chordal graphs",
journal = j-TALG,
volume = "3",
number = "2",
pages = "14:1--14:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240237",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We use a new structural theorem on the presence of
two-pairs in weakly chordal graphs to develop improved
algorithms. For the recognition problem, we reduce the
time complexity from $O(mn^2)$ to $O(m^2)$ and the
space complexity from $O(n^3)$ to $O(m + n)$, and also
produce a hole or antihole if the input graph is not
weakly chordal. For the optimization problems, the
complexity of the clique and coloring problems is
reduced from $O(mn^2)$ to $O(n^3)$ and the complexity
of the independent set and clique cover problems is
improved from $O(n^4)$ to $O(mn)$. The space complexity
of our optimization algorithms is $O(m + n)$.",
acknowledgement = ack-nhfb,
articleno = "14",
keywords = "coloring; graph algorithms; Perfect graphs;
recognition; weakly chordal",
}
@Article{Kavitha:2007:SSM,
author = "Telikepalli Kavitha and Kurt Mehlhorn and Dimitrios
Michail and Katarzyna E. Paluch",
title = "Strongly stable matchings in time {$O(nm)$} and
extension to the hospitals-residents problem",
journal = j-TALG,
volume = "3",
number = "2",
pages = "15:1--15:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240238",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "An instance of the stable marriage problem is an
undirected bipartite graph $G = (X \cup W, E)$ with
linearly ordered adjacency lists with ties allowed in
the ordering. A matching $M$ is a set of edges, no two
of which share an endpoint. An edge $e = (a, b) \in E
\setminus M$ is a blocking edge for $M$ if $a$ is
either unmatched or strictly prefers $b$ to its partner
in $M$, and $b$ is unmatched, strictly prefers $a$ to
its partner in $M$, or is indifferent between them. A
matching is strongly stable if there is no blocking
edge with respect to it. We give an $O(nm)$ algorithm
for computing strongly stable matchings, where $n$ is
the number of vertices and $m$ the number of edges. The
previous best algorithm had running time $O(m^2)$. We
also study this problem in the hospitals-residents
setting, which is a many-to-one extension of the
aforementioned problem. We give an $O(m \sum_{h \in H}
p_h)$ algorithm for computing a strongly stable
matching in the hospitals-residents problem, where
$p_h$ is the quota of a hospital $h$. The previous best
algorithm had running time $O(m^2)$.",
acknowledgement = ack-nhfb,
articleno = "15",
keywords = "Bipartite matching; level maximal; stable marriage;
strong stability",
}
@Article{Bagchi:2007:DSR,
author = "Amitabha Bagchi and Amitabh Chaudhary and David
Eppstein and Michael T. Goodrich",
title = "Deterministic sampling and range counting in geometric
data streams",
journal = j-TALG,
volume = "3",
number = "2",
pages = "16:1--16:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240239",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We present memory-efficient deterministic algorithms
for constructing $\epsilon$-nets and
$\epsilon$-approximations of streams of geometric data.
Unlike probabilistic approaches, these deterministic
samples provide guaranteed bounds on their
approximation factors. We show how our deterministic
samples can be used to answer approximate online
iceberg geometric queries on data streams. We use these
techniques to approximate several robust statistics of
geometric data streams, including Tukey depth,
simplicial depth, regression depth, the Thiel-Sen
estimator, and the least median of squares. Our
algorithms use only a polylogarithmic amount of memory,
provided the desired approximation factors are at least
inverse-polylogarithmic. We also include a lower bound
for noniceberg geometric queries.",
acknowledgement = ack-nhfb,
articleno = "16",
keywords = "Data streams; epsilon nets; geometric data; iceberg
queries; range counting; robust statistics; sampling;
streaming algorithms",
}
@Article{Arya:2007:SEB,
author = "Sunil Arya and Theocharis Malamatos and David M.
Mount",
title = "A simple entropy-based algorithm for planar point
location",
journal = j-TALG,
volume = "3",
number = "2",
pages = "17:1--17:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240240",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Given a planar polygonal subdivision S, point location
involves preprocessing this subdivision into a data
structure so that given any query point q, the cell of
the subdivision containing q can be determined
efficiently. Suppose that for each cell z in the
subdivision, the probability p z that a query point
lies within this cell is also given. The goal is to
design the data structure to minimize the average
search time. This problem has been considered before,
but existing data structures are all quite complicated.
It has long been known that the entropy H of the
probability distribution is the dominant term in the
lower bound on the average-case search time. In this
article, we show that a very simple modification of a
well-known randomized incremental algorithm can be
applied to produce a data structure of expected linear
size that can answer point-location queries in $O(H)$
average time. We also present empirical evidence for
the practical efficiency of this approach.",
acknowledgement = ack-nhfb,
articleno = "17",
keywords = "entropy; expected-case complexity; Point location;
polygonal subdivision; randomized algorithms;
trapezoidal maps",
}
@Article{Kauers:2007:ADZ,
author = "Manuel Kauers",
title = "An algorithm for deciding zero equivalence of nested
polynomially recurrent sequences",
journal = j-TALG,
volume = "3",
number = "2",
pages = "18:1--18:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240241",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We introduce the class of nested polynomially
recurrent sequences which includes a large number of
sequences that are of combinatorial interest. We
present an algorithm for deciding zero equivalence of
these sequences, thereby providing a new algorithm for
proving identities among combinatorial sequences: In
order to prove an identity, decide by the algorithm
whether the difference of lefthand-side and
righthand-side is identically zero. This algorithm is
able to treat mathematical objects which are not
covered by any other known symbolic method for proving
combinatorial identities. Despite its theoretical
flavor and high complexity, an implementation of the
algorithm can be successfully applied to nontrivial
examples.",
acknowledgement = ack-nhfb,
articleno = "18",
keywords = "combinatorial sequences; nested polynomially recurrent
sequences; Symbolic computation; zero equivalence",
}
@Article{Amir:2007:DTS,
author = "Amihood Amir and Gad M. Landau and Moshe Lewenstein
and Dina Sokol",
title = "Dynamic text and static pattern matching",
journal = j-TALG,
volume = "3",
number = "2",
pages = "19:1--19:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240242",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "In this article, we address a new version of dynamic
pattern matching. The dynamic text and static pattern
matching problem is the problem of finding a static
pattern in a text that is continuously being updated.
The goal is to report all new occurrences of the
pattern in the text after each text update. We present
an algorithm for solving the problem where the text
update operation is changing the symbol value of a text
location. Given a text of length $n$ and a pattern of
length $m$, our algorithm preprocesses the text in time
$O(n \log \log m)$, and the pattern in time $O (m \log
m)$. The extra space used is $O(n + m \log m)$.
Following each text update, the algorithm deletes all
prior occurrences of the pattern that no longer match,
and reports all new occurrences of the pattern in the
text in $O(\log \log m)$ time. We note that the
complexity is not proportional to the number of pattern
occurrences, since all new occurrences can be reported
in a succinct form.",
acknowledgement = ack-nhfb,
articleno = "19",
keywords = "border trees; Dynamic text; static pattern",
}
@Article{Ferragina:2007:CRS,
author = "Paolo Ferragina and Giovanni Manzini and Veli
M{\"a}kinen and Gonzalo Navarro",
title = "Compressed representations of sequences and full-text
indexes",
journal = j-TALG,
volume = "3",
number = "2",
pages = "20:1--20:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240243",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Given a sequence $S = s_1 s_2 \ldots s_n$ of integers
smaller than $r = O (\polylog(n))$, we show how $S$ can
be represented using $nH_0(S) + o(n)$ bits, so that we
can know any $s_q$, as well as answer rank and select
queries on $S$, in constant time. $H_0(S)$ is the
zero-order empirical entropy of $S$ and $nH_0(S)$
provides an information-theoretic lower bound to the
bit storage of any sequence $S$ via a fixed encoding of
its symbols. This extends previous results on binary
sequences, and improves previous results on general
sequences where those queries are answered in $O(\log
r)$ time. For larger $r$, we can still represent $S$ in
$nH_0(S) + o(n \log r)$ bits and answer queries in
$O(\log r / \log \log n)$ time.\par
Another contribution of this article is to show how to
combine our compressed representation of integer
sequences with a compression boosting technique to
design compressed full-text indexes that scale well
with the size of the input alphabet {$\Sigma$}.
Specifically, we design a variant of the FM-index that
indexes a string $T[1,n]$ within $nH_k(T) + o(n)$ bits
of storage, where $H_k(T)$ is the $k$th-order empirical
entropy of $T$. This space bound holds simultaneously
for all $k \leq \alpha \log |\Sigma| n$, constant $0 <
\alpha < 1$, and $|\Sigma| = O(\polylog(n))$. This
index counts the occurrences of an arbitrary pattern
$P[1,p]$ as a substring of $T$ in $O(p)$ time; it
locates each pattern occurrence in $O(\log
1+\varepsilon n)) time for any constant $0 <
\varepsilon < 1$; and reports a text substring of
length $\ell$ in $O(\ell + \log 1+\varepsilon n)$
time.\par
Compared to all previous works, our index is the first
that removes the alphabet-size dependance from all
query times, in particular, counting time is linear in
the pattern length. Still, our index uses essentially
the same space of the $k$th-order entropy of the text
$T$, which is the best space obtained in previous work.
We can also handle larger alphabets of size ${|\Sigma|}
= O(n\beta)$, for any $0 < \beta < 1$, by paying $o(n
\log |\Sigma|)$ extra space and multiplying all query
times by $O(\log |\Sigma|/ \log \log n)$.",
acknowledgement = ack-nhfb,
articleno = "20",
keywords = "Burrows-Wheeler transform; compression boosting;
entropy; rank and select; text compression; Text
indexing; wavelet tree",
}
@Article{Chan:2007:CID,
author = "Ho-Leung Chan and Wing-Kai Hon and Tak-Wah Lam and
Kunihiko Sadakane",
title = "Compressed indexes for dynamic text collections",
journal = j-TALG,
volume = "3",
number = "2",
pages = "21:1--21:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240244",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Let $T$ be a string with $n$ characters over an
alphabet of constant size. A recent breakthrough on
compressed indexing allows us to build an index for $T$
in optimal space (i.e., $O(n)$ bits), while supporting
very efficient pattern matching [Ferragina and Manzini
2000; Grossi and Vitter 2000]. Yet the compressed
nature of such indexes also makes them difficult to
update dynamically.\par
This article extends the work on optimal-space indexing
to a dynamic collection of texts. Our first result is a
compressed solution to the library management problem,
where we show an index of $O(n)$ bits for a text
collection $L$ of total length $n$, which can be
updated in $O(| T | \log n)$ time when a text $T$ is
inserted or deleted from $L$; also, the index supports
searching the occurrences of any pattern $P$ in all
texts in $L$ in $O(|P| log n + {\rm occ} \log 2 n)$
time, where {\rm occ} is the number of
occurrences.\par
Our second result is a compressed solution to the
dictionary matching problem, where we show an index of
$O(d)$ bits for a pattern collection $D$ of total
length $d$, which can be updated in $O(|P| \log 2 d)$
time when a pattern $P$ is inserted or deleted from
$D$; also, the index supports searching the occurrences
of all patterns of $D$ in any text $T$ in $O((|T| +
{\rm occ})\log 2 d)$ time. When compared with the $O(d
\log d)$-bit suffix-tree-based solution of Amir et al.
[1995], the compact solution increases the query time
by roughly a factor of $\log d$ only.\par
The solution to the dictionary matching problem is
based on a new compressed representation of a suffix
tree. Precisely, we give an $O(n)$-bit representation
of a suffix tree for a dynamic collection of texts
whose total length is $n$, which supports insertion and
deletion of a text $T$ in $O(|T| \log 2 n)$ time, as
well as all suffix tree traversal operations, including
forward and backward suffix links. This work can be
regarded as a generalization of the compressed
representation of static texts. In the study of the
aforementioned result, we also derive the first
$O(n)$-bit representation for maintaining $n$ pairs of
balanced parentheses in $O(\log n / \log \log n)$ time
per operation, matching the time complexity of the
previous $O(n \log n)$-bit solution.",
acknowledgement = ack-nhfb,
articleno = "21",
keywords = "Compressed suffix tree; string matching",
}
@Article{Boyar:2007:RWO,
author = "Joan Boyar and Lene M. Favrholdt",
title = "The relative worst order ratio for online algorithms",
journal = j-TALG,
volume = "3",
number = "2",
pages = "22:1--22:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240245",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We define a new measure for the quality of online
algorithms, the relative worst order ratio, using ideas
from the max/max ratio [Ben-David and Borodin 1994] and
from the random order ratio [Kenyon 1996]. The new
ratio is used to compare online algorithms directly by
taking the ratio of their performances on their
respective worst permutations of a worst-case
sequence.\par
Two variants of the bin packing problem are considered:
the classical bin packing problem, where the goal is to
fit all items in as few bins as possible, and the dual
bin packing problem, which is the problem of maximizing
the number of items packed in a fixed number of bins.
Several known algorithms are compared using this new
measure, and a new, simple variant of first-fit is
proposed for dual bin packing.\par
Many of our results are consistent with those
previously obtained with the competitive ratio or the
competitive ratio on accommodating sequences, but new
separations and easier proofs are found.",
acknowledgement = ack-nhfb,
articleno = "22",
keywords = "bin packing; dual bin packing; Online; quality
measure; relative worst order ratio",
}
@Article{Becchetti:2007:SCM,
author = "L. Becchetti and J. K{\"o}nemann and S. Leonardi and
M. P{\'a}al",
title = "Sharing the cost more efficiently: {Improved}
approximation for multicommodity rent-or-buy",
journal = j-TALG,
volume = "3",
number = "2",
pages = "23:1--23:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240246",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "In the multicommodity rent-or-buy (MROB) network
design problems, we are given a network together with a
set of $k$ terminal pairs $(s_1, t_1), \ldots, (s_k,
t_k)$. The goal is to provision the network so that a
given amount of flow can be shipped between $s_i$ and
$t_i$ for all $1 \leq i \leq k$ simultaneously. In
order to provision the network, one can either rent
capacity on edges at some cost per unit of flow, or buy
them at some larger fixed cost. Bought edges have no
incremental, flow-dependent cost. The overall objective
is to minimize the total provisioning
cost.\par
Recently, Gupta et al. [2003a] presented a
12-approximation for the MROB problem. Their algorithm
chooses a subset of the terminal pairs in the graph at
random and then buys the edges of an approximate
Steiner forest for these pairs. This technique had
previously been introduced [Gupta et al. 2003b] for the
single-sink rent-or-buy network design problem.\par
In this article we give a 6.828-approximation for the
MROB problem by refining the algorithm of Gupta et al.
and simplifying their analysis. The improvement in our
article is based on a more careful adaptation and
simplified analysis of the primal-dual algorithm for
the Steiner forest problem due to Agrawal et al.
[1995]. Our result significantly reduces the gap
between the single-sink and multisink case.",
acknowledgement = ack-nhfb,
articleno = "23",
keywords = "Approximation algorithms; cost sharing; network
design; Steiner forests",
}
@Article{Johnson:2007:NCC,
author = "David S. Johnson",
title = "The {NP}-completeness column: {Finding} needles in
haystacks",
journal = j-TALG,
volume = "3",
number = "2",
pages = "24:1--24:??",
month = may,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1240233.1240247",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:54:42 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "This is the 26th edition of a column that covers new
developments in the theory of NP-completeness. The
presentation is modeled on that which M. R. Garey and I
used in our book ``Computers and Intractability: A
Guide to the Theory of NP-Completeness,'' W. H. Freeman
{\&} Co., New York, 1979, hereinafter referred to as
``[G{\&}J].'' Previous columns, the first 23 of which
appeared in J. Algorithms, will be referred to by a
combination of their sequence number and year of
appearance, e.g., ``Column 1 [1981].'' Full
bibliographic details on the previous columns, as well
as downloadable unofficial versions of them, can be
found at
\url{http://www.research.att.com/~dsj/columns/}. This
column discusses the question of whether finding an
object can be computationally difficult even when we
know that the object exists.",
acknowledgement = ack-nhfb,
articleno = "24",
keywords = "fixed point; game theory; local search; Nash
equilibrium; PLS; PPAD",
}
@Article{Feng:2007:FAS,
author = "Jianxing Feng and Daming Zhu",
title = "Faster algorithms for sorting by transpositions and
sorting by block interchanges",
journal = j-TALG,
volume = "3",
number = "3",
pages = "25:1--25:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273341",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "In this article, we present a new data structure,
called the permutation tree, to improve the running
time of sorting permutation by transpositions and
sorting permutation by block interchanges. The existing
1.5-approximation algorithm for sorting permutation by
transpositions has time complexity $O(n^{3/2}
\sqrt{\log n})$. By means of the permutation tree, we
can improve this algorithm to achieve time complexity
$O(n \log n)$. We can also improve the algorithm for
sorting permutation by block interchanges to take its
time complexity from $O(n^2)$ down to $O(n \log n)$.",
acknowledgement = ack-nhfb,
articleno = "25",
keywords = "Block interchange; genome; permutation; time
complexity; transposition; tree",
}
@Article{Gupta:2007:CPD,
author = "Himanshu Gupta and Rephael Wenger",
title = "Constructing pairwise disjoint paths with few links",
journal = j-TALG,
volume = "3",
number = "3",
pages = "26:1--26:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273342",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Let $P$ be a simple polygon and let $\{(u_1,
u{\prime}_1), (u_2, u{\prime}_2), \ldots, (u_m,
u{\prime}_m)\}$ be a set of $m$ pairs of distinct
vertices of $P$, where for every distinct $i, $j \leq
m$, there exist pairwise disjoint (nonintersecting)
paths connecting $u_i$ to $u\prime_i$ and $u_j$ to
$u\prime_j$. We wish to construct $m$ pairwise disjoint
paths in the interior of $P$ connecting $u_i$ to
$u\prime_i$ for $i = 1, \ldots, m$, with a minimal
total number of line segments. We give an approximation
algorithm that constructs such a set of paths using
$O(M)$ line segments in $O(n \log m + M \log m)$ time,
where $M$ is the number of line segments in the optimal
solution and $n$ is the size of the polygon.",
acknowledgement = ack-nhfb,
articleno = "26",
keywords = "isomorphic triangulations; Link paths; noncrossing;
polygon",
}
@Article{Chekuri:2007:MDF,
author = "Chandra Chekuri and Marcelo Mydlarz and F. Bruce
Shepherd",
title = "Multicommodity demand flow in a tree and packing
integer programs",
journal = j-TALG,
volume = "3",
number = "3",
pages = "27:1--27:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273343",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider requests for capacity in a given tree
network T =(V, E) where each edge e of the tree has
some integer capacity u e. Each request f is a node
pair with an integer demand d f and a profit w f which
is obtained if the request is satisfied. The objective
is to find a set of demands that can be feasibly routed
in the tree and which provides a maximum profit. This
generalizes well-known problems, including the knapsack
and $b$-matching problems.\par
When all demands are 1, we have the integer
multicommodity flow problem. Garg et al. [1997] had
shown that this problem is NP-hard and gave a
2-approximation algorithm for the cardinality case (all
profits are 1) via a primal-dual algorithm. Our main
result establishes that the integrality gap of the
natural linear programming relaxation is at most 4 for
the case of arbitrary profits. Our proof is based on
coloring paths on trees and this has other applications
for wavelength assignment in optical network
routing.\par
We then consider the problem with arbitrary demands.
When the maximum demand $d_{\rm max} is at most the
minimum edge capacity $u_{\rm min}, we show that the
integrality gap of the LP is at most 48. This result is
obtained by showing that the integrality gap for the
demand version of such a problem is at most 11.542
times that for the unit-demand case. We use techniques
of Kolliopoulos and Stein [2004, 2001] to obtain this.
We also obtain, via this method, improved algorithms
for line and ring networks. Applications and
connections to other combinatorial problems are
discussed.",
acknowledgement = ack-nhfb,
articleno = "27",
keywords = "approximation algorithm; Integer multicommodity flow;
integrality gap; packing integer program; tree",
}
@Article{Bar-Noy:2007:WSR,
author = "Amotz Bar-Noy and Richard E. Ladner and Tami Tamir",
title = "Windows scheduling as a restricted version of bin
packing",
journal = j-TALG,
volume = "3",
number = "3",
pages = "28:1--28:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273344",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Given a sequence of $n$ positive integers $w_1, w_2,
\ldots, w_n$ that are associated with the items $1, 2,
\ldots n$, respectively. In the windows scheduling
problem, the goal is to schedule all the items
(equal-length information pages) on broadcasting
channels such that the gap between two consecutive
appearances of page $i$ on any of the channels is at
most $w_i$ slots (a slot is the transmission time of
one page). In the unit-fractions bin packing problem,
the goal is to pack all the items in bins of unit size
where the size (width) of item $i$ is $1 / w_i$. The
optimization objective is to minimize the number of
channels or bins. In the offline setting, the sequence
is known in advance, whereas in the online setting, the
items arrive in order and assignment decisions are
irrevocable. Since a page requires at least $1 / w_i$
of a channel's bandwidth, it follows that windows
scheduling without migration (i.e., all broadcasts of a
page must be from the same channel) is a restricted
version of unit-fractions bin packing.\par
Let $H = \lceil \sum_{i=1}^n (1/ w_i)$ be the bandwidth
lower bound on the required number of bins (channels).
The best-known offline algorithm for the windows
scheduling problem used $H + O(\ln H)$ channels. This
article presents an offline algorithm for the
unit-fractions bin packing problem with at most $H + 1$
bins. In the online setting, this article presents
algorithms for both problems with $H + O(\sqrt{H})$
channels or bins, where the one for the unit-fractions
bin packing problem is simpler. On the other hand, this
article shows that already for the unit-fractions bin
packing problem, any online algorithm must use at least
$H + \Omega(\ln H)$ bins. For instances in which the
window sizes form a divisible sequence, an optimal
online algorithm is presented. Finally, this article
includes a new NP-hardness proof for the windows
scheduling problem.",
acknowledgement = ack-nhfb,
articleno = "28",
keywords = "approximation algorithms; bin-packing; online
algorithms; Periodic scheduling",
}
@Article{Hazay:2007:APM,
author = "Carmit Hazay and Moshe Lewenstein and Dina Sokol",
title = "Approximate parameterized matching",
journal = j-TALG,
volume = "3",
number = "3",
pages = "29:1--29:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273345",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Two equal length strings $s$ and $s\prime$ , over
alphabets ${\Sigma} s$ and ${\Sigma} s \prime$,
parameterize match if there exists a bijection ${\pi} :
{\Sigma} s \rightarrow {\Sigma} s \prime$ such that
${\pi}(s) = s \prime$, where ${\pi} (s)$ is the
renaming of each character of $s$ via ${\pi}$.
Parameterized matching is the problem of finding all
parameterized matches of a pattern string $p$ in a text
$t$, and approximate parameterized matching is the
problem of finding at each location a bijection ${\pi}$
that maximizes the number of characters that are mapped
from $p$ to the appropriate $|p|$-length substring of
$t$.\par
Parameterized matching was introduced as a model for
software duplication detection in software maintenance
systems and also has applications in image processing
and computational biology. For example, approximate
parameterized matching models image searching with
variable color maps in the presence of errors.\par
We consider the problem for which an error threshold,
$k$, is given, and the goal is to find all locations in
$t$ for which there exists a bijection ${\pi}$ which
maps $p$ into the appropriate $|p|$-length substring of
$t$ with at most $k$ mismatched mapped elements. Our
main result is an algorithm for this problem with
$O(nk^{1.5} + mk \log m)$ time complexity, where $m = |
p |$ and $n = | t |$. We also show that when $| p | = |
t | = m$, the problem is equivalent to the maximum
matching problem on graphs, yielding a $O(m + k^{1.5})$
solution.",
acknowledgement = ack-nhfb,
articleno = "29",
keywords = "Hamming distance; maximum matching; mismatch pair;
parameterize match",
}
@Article{Halldorsson:2007:IAR,
author = "Magn{\'u}s M. Halld{\'o}rsson and Kazuo Iwama and
Shuichi Miyazaki and Hiroki Yanagisawa",
title = "Improved approximation results for the stable marriage
problem",
journal = j-TALG,
volume = "3",
number = "3",
pages = "30:1--30:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273346",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "The stable marriage problem has recently been studied
in its general setting, where both ties and incomplete
lists are allowed. It is NP-hard to find a stable
matching of maximum size, while any stable matching is
a maximal matching and thus trivially we can obtain a
2-approximation algorithm.\par
In this article, we give the first nontrivial result
for approximation of factor less than two. Our
algorithm achieves an approximation ratio of $2/(1 + L
- 2)$ for instances in which only men have ties of
length at most $L$. When both men and women are allowed
to have ties but the lengths are limited to two, then
we show a ratio of $13/7(< 1.858)$. We also improve the
lower bound on the approximation ratio to $21/19(>
1.1052)$.",
acknowledgement = ack-nhfb,
articleno = "30",
keywords = "Approximation algorithms; incomplete lists; stable
marriage problem; ties",
}
@Article{Indyk:2007:NNP,
author = "Piotr Indyk and Assaf Naor",
title = "Nearest-neighbor-preserving embeddings",
journal = j-TALG,
volume = "3",
number = "3",
pages = "31:1--31:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273347",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "In this article we introduce the notion of
nearest-neighbor-preserving embeddings. These are
randomized embeddings between two metric spaces which
preserve the (approximate) nearest-neighbors. We give
two examples of such embeddings for Euclidean metrics
with low ``intrinsic'' dimension. Combining the
embeddings with known data structures yields the
best-known approximate nearest-neighbor data structures
for such metrics.",
acknowledgement = ack-nhfb,
articleno = "31",
keywords = "dimensionality reduction; doubling spaces; embeddings;
Nearest neighbor",
}
@Article{Even-Dar:2007:CTN,
author = "Eyal Even-Dar and Alex Kesselman and Yishay Mansour",
title = "Convergence time to {Nash} equilibrium in load
balancing",
journal = j-TALG,
volume = "3",
number = "3",
pages = "32:1--32:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273348",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We study the number of steps required to reach a pure
Nash equilibrium in a load balancing scenario where
each job behaves selfishly and attempts to migrate to a
machine which will minimize its cost. We consider a
variety of load balancing models, including identical,
restricted, related, and unrelated machines. Our
results have a crucial dependence on the weights
assigned to jobs. We consider arbitrary weights,
integer weights, k distinct weights, and identical
(unit) weights. We look both at an arbitrary schedule
(where the only restriction is that a job migrates to a
machine which lowers its cost) and specific efficient
schedulers (e.g., allowing the largest weight job to
move first). A by-product of our results is
establishing a connection between various scheduling
models and the game-theoretic notion of potential
games. We show that load balancing in unrelated
machines is a generalized ordinal potential game, load
balancing in related machines is a weighted potential
game, and load balancing in related machines and unit
weight jobs is an exact potential game.",
acknowledgement = ack-nhfb,
articleno = "32",
keywords = "convergence time; game theory; Nash equilibrium",
}
@Article{Andrews:2007:RSM,
author = "Matthew Andrews and Lisa Zhang",
title = "Routing and scheduling in multihop wireless networks
with time-varying channels",
journal = j-TALG,
volume = "3",
number = "3",
pages = "33:1--33:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273349",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We study routing and scheduling in multihop wireless
networks. When data is transmitted from its source node
to its destination node it may go through other
wireless nodes as intermediate hops. The data
transmission is node constrained, that is, every node
can transmit data to at most one neighboring node per
time step. The transmission rates are time varying as a
result of changing wireless channel conditions.\par
In this article, we assume that data arrivals and
transmission rates are governed by an adversary. The
power of the adversary is limited by an admissibility
condition which forbids the adversary from overloading
any wireless node a priori. The node-constrained
transmission and time-varying nature of the
transmission rates make our model different from and
harder than the standard adversarial queueing model
which relates to wireline networks.\par
For the case in which the adversary specifies the paths
that the data must follow, we design scheduling
algorithms that ensure network stability. These
algorithms try to give priority to the data that is
closest to its source node. However, at each time step
only a subset of the data queued at a node is eligible
for scheduling. One of our algorithms is fully
distributed.\par
For the case in which the adversary does not dictate
the data paths, we show how to route data so that the
admissibility condition is satisfied. We can then
schedule data along the chosen paths using our stable
scheduling algorithms.",
acknowledgement = ack-nhfb,
articleno = "33",
keywords = "routing; Scheduling; stability; time-varying; wireless
network",
}
@Article{Naor:2007:NAP,
author = "Moni Naor and Udi Wieder",
title = "Novel architectures for {P2P} applications: {The}
continuous-discrete approach",
journal = j-TALG,
volume = "3",
number = "3",
pages = "34:1--34:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273350",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We propose a new approach for constructing P2P
networks based on a dynamic decomposition of a
continuous space into cells corresponding to servers.
We demonstrate the power of this approach by suggesting
two new P2P architectures and various algorithms for
them. The first serves as a DHT (distributed hash
table) and the other is a dynamic expander network. The
DHT network, which we call Distance Halving, allows
logarithmic routing and load while preserving constant
degrees. It offers an optimal tradeoff between degree
and path length in the sense that degree d guarantees a
path length of $O(\log d n)$. Another advantage over
previous constructions is its relative simplicity. A
major new contribution of this construction is a
dynamic caching technique that maintains low load and
storage, even under the occurrence of hot spots. Our
second construction builds a network that is guaranteed
to be an expander. The resulting topologies are simple
to maintain and implement. Their simplicity makes it
easy to modify and add protocols. A small variation
yields a DHT which is robust against random Byzantine
faults. Finally we show that, using our approach, it is
possible to construct any family of constant degree
graphs in a dynamic environment, though with worse
parameters. Therefore, we expect that more distributed
data structures could be designed and implemented in a
dynamic environment.",
acknowledgement = ack-nhfb,
articleno = "34",
keywords = "Peer-to-peer networks; routing",
}
@Article{Khuller:2007:PC,
author = "Samir Khuller",
title = "Problems column",
journal = j-TALG,
volume = "3",
number = "3",
pages = "35:1--35:??",
month = aug,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1273340.1273351",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:11 MDT 2008",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "35",
}
@Article{Gabow:2007:ISS,
author = "H. N. Gabow and Michael A. Bender and Martin
Farach-Colton",
title = "Introduction to {SODA} 2002 and 2003 special issue",
journal = j-TALG,
volume = "3",
number = "4",
pages = "36:1--36:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290673",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "36",
}
@Article{Aspnes:2007:SG,
author = "James Aspnes and Gauri Shah",
title = "Skip graphs",
journal = j-TALG,
volume = "3",
number = "4",
pages = "37:1--37:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290674",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Skip graphs are a novel distributed data structure,
based on skip lists, that provide the full
functionality of a balanced tree in a distributed
system where resources are stored in separate nodes
that may fail at any time. They are designed for use in
searching peer-to-peer systems, and by providing the
ability to perform queries based on key ordering, they
improve on existing search tools that provide only hash
table functionality. Unlike skip lists or other tree
data structures, skip graphs are highly resilient,
tolerating a large fraction of failed nodes without
losing connectivity. In addition, simple and
straightforward algorithms can be used to construct a
skip graph, insert new nodes into it, search it, and
detect and repair errors within it introduced due to
node failures.",
acknowledgement = ack-nhfb,
articleno = "37",
keywords = "overlay networks; Peer-to-peer; skip lists",
}
@Article{Han:2007:OPS,
author = "Yijie Han",
title = "Optimal parallel selection",
journal = j-TALG,
volume = "3",
number = "4",
pages = "38:1--38:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290675",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We present an optimal parallel selection algorithm on
the EREW PRAM. This algorithm runs in $O(\log n)$ time
with $n / \log n$ processors. This complexity matches
the known lower bound for parallel selection on the
EREW PRAM model. We therefore close this problem which
has been open for more than a decade.",
acknowledgement = ack-nhfb,
articleno = "38",
keywords = "EREW PRAM; Parallel algorithms; selection",
}
@Article{Bansal:2007:MWF,
author = "Nikhil Bansal and Kedar Dhamdhere",
title = "Minimizing weighted flow time",
journal = j-TALG,
volume = "3",
number = "4",
pages = "39:1--39:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290676",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider the problem of minimizing the total
weighted flow time on a single machine with
preemptions. We give an online algorithm that is
$O(k)$-competitive for $k$ weight classes. This implies
an $O (\log W)$-competitive algorithm, where $W$ is the
maximum to minimum ratio of weights. This algorithm
also implies an $O(\log n + \log P)$-approximation
ratio for the problem, where $P$ is the ratio of the
maximum to minimum job size and $n$ is the number of
jobs. We also consider the nonclairvoyant setting where
the size of a job is unknown upon its arrival and
becomes known to the scheduler only when the job meets
its service requirement. We consider the resource
augmentation model, and give a $(1 +
\varepsilon)$-speed, $(1 +1/\varepsilon)$-competitive
online algorithm.",
acknowledgement = ack-nhfb,
articleno = "39",
keywords = "nonclairvoyant scheduling; online algorithms; response
time; Scheduling",
}
@Article{Fakcharoenphol:2007:TRP,
author = "Jittat Fakcharoenphol and Chris Harrelson and Satish
Rao",
title = "The $k$-traveling repairmen problem",
journal = j-TALG,
volume = "3",
number = "4",
pages = "40:1--40:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290677",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider the $k$-traveling repairmen problem, also
known as the minimum latency problem, to multiple
repairmen. We give a polynomial-time $8.497
\alpha$-approximation algorithm for this
generalization, where $\alpha$ denotes the best
achievable approximation factor for the problem of
finding the least-cost rooted tree spanning i vertices
of a metric. For the latter problem, a $(2 +
\varepsilon)$-approximation is known. Our results can
be compared with the best-known approximation algorithm
using similar techniques for the case $k = 1$, which is
$3.59\alpha$. Moreover, recent work of Chaudry et al.
[2003] shows how to remove the factor of $\alpha$, thus
improving all of these results by that factor. We are
aware of no previous work on the approximability of the
present problem. In addition, we give a simple proof of
the $3.59 \alpha$-approximation result that can be more