%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.06",
%%% date = "15 July 2009",
%%% time = "14:08:47 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 = "06921 6292 33843 293434",
%%% 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.06, the COMPLETE journal
%%% coverage looked like this:
%%%
%%% 2005 ( 20) 2007 ( 52) 2009 ( 10)
%%% 2006 ( 37) 2008 ( 66)
%%%
%%% Article: 185
%%%
%%% Total entries: 185
%%%
%%% 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
easily extended to the case of multiple repairmen, and
may be of independent interest.",
acknowledgement = ack-nhfb,
articleno = "40",
keywords = "Traveling salesman; vehicle routing",
}
@Article{Irani:2007:APS,
author = "Sandy Irani and Sandeep Shukla and Rajesh Gupta",
title = "Algorithms for power savings",
journal = j-TALG,
volume = "3",
number = "4",
pages = "41:1--41:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290678",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "This article examines two different mechanisms for
saving power in battery-operated embedded systems. The
first strategy is that the system can be placed in a
sleep state if it is idle. However, a fixed amount of
energy is required to bring the system back into an
active state in which it can resume work. The second
way in which power savings can be achieved is by
varying the speed at which jobs are run. We utilize a
power consumption curve $P(s)$ which indicates the
power consumption level given a particular speed. We
assume that $P(s)$ is convex, nondecreasing, and
nonnegative for $s \geq 0$. The problem is to schedule
arriving jobs in a way that minimizes total energy use
and so that each job is completed after its release
time and before its deadline. We assume that all jobs
can be preempted and resumed at no cost. Although each
problem has been considered separately, this is the
first theoretical analysis of systems that can use both
mechanisms. We give an offline algorithm that is within
a factor of 2 of the optimal algorithm. We also give an
online algorithm with a constant competitive ratio.",
acknowledgement = ack-nhfb,
articleno = "41",
keywords = "dynamic speed scaling; online algorithms; Power
savings",
}
@Article{Alon:2007:GSE,
author = "Noga Alon and Venkatesan Guruswami and Tali Kaufman
and Madhu Sudan",
title = "Guessing secrets efficiently via list decoding",
journal = j-TALG,
volume = "3",
number = "4",
pages = "42:1--42:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290679",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider the guessing secrets problem defined by
Chung et al. [2001]. This is a variant of the standard
20 questions game where the player has a set of $k > 1$
secrets from a universe of $N$ possible secrets. The
player is asked Boolean questions about the secret. For
each question, the player picks one of the $k$ secrets
adversarially, and answers according to this
secret.\par
We present an explicit set of $O(\log N)$ questions
together with an efficient (i.e., ${\rm poly}(\log N)$
time) algorithm to solve the guessing secrets problem
for the case of 2 secrets. This answers the main
algorithmic question left unanswered by Chung et al.
[2001]. The main techniques we use are small
$\epsilon$-biased spaces and the notion of list
decoding.\par
We also establish bounds on the number of questions
needed to solve the $k-secrets game for $k > 2$, and
discuss how list decoding can be used to get partial
information about the secrets, specifically to find a
small core of secrets that must intersect the actual
set of $k$ secrets.",
acknowledgement = ack-nhfb,
articleno = "42",
keywords = "20 questions; $\epsilon$-biased spaces; decoding
algorithms; error-correcting codes; $k$-universal
sets",
}
@Article{Raman:2007:SID,
author = "Rajeev Raman and Venkatesh Raman and Srinivasa Rao
Satti",
title = "Succinct indexable dictionaries with applications to
encoding $k$-ary trees, prefix sums and multisets",
journal = j-TALG,
volume = "3",
number = "4",
pages = "43:1--43:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290680",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider the indexable dictionary problem, which
consists of storing a set $S \subseteq \{0, \ldots , m
- 1\}$ for some integer $m$ while supporting the
operations of $\rank(x)$, which returns the number of
elements in $S$ that are less than $x$ if $x \in S$,
and $-1$ otherwise; and $\select(i)$, which returns the
$i$th smallest element in $S$. We give a data structure
that supports both operations in $O(1)$ time on the RAM
model and requires $B(n,m) + o(n) + O(\lg \lg m)$ bits
to store a set of size $n$, where $B(n, m) = \lfloor
\lg (m / n)\rfloor$ is the minimum number of bits
required to store any $n$-element subset from a
universe of size $m$. Previous dictionaries taking this
space only supported (yes/no) membership queries in $O
(1)$ time. In the cell probe model we can remove the $O
(\lg \lg m)$ additive term in the space bound,
answering a question raised by Fich and Miltersen
[1995] and Pagh [2001].\par
We present extensions and applications of our indexable
dictionary data structure, including:\par
--- an information-theoretically optimal representation
of a $k$-ary cardinal tree that supports standard
operations in constant time;\par
--- a representation of a multiset of size $n$ from
$\{0, \ldots , m - 1\}$ in $B(n, m + n) + o(n)$ bits
that supports (appropriate generalizations of) rank and
select operations in constant time; and $+ O(\lg \lg
m)$\par
--- a representation of a sequence of $n$ nonnegative
integers summing up to $m$ in $B(n, m + n) + o(n)$ bits
that supports prefix sum queries in constant time.",
acknowledgement = ack-nhfb,
articleno = "43",
keywords = "Dictionaries; multisets; perfect hashing; prefix sums;
sets; succinct data structures; tries",
}
@Article{Janson:2007:PFS,
author = "Svante Janson and Wojciech Szpankowski",
title = "Partial fillup and search time in {LC} tries",
journal = j-TALG,
volume = "3",
number = "4",
pages = "44:1--44:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290681",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Andersson and Nilsson introduced in 1993 a
level-compressed trie (for short, LC trie) in which a
full subtree of a node is compressed to a single node
of degree being the size of the subtree. Recent
experimental results indicated a ``dramatic
improvement'' when full subtrees are replaced by
``partially filled subtrees.'' In this article, we
provide a theoretical justification of these
experimental results, showing, among others, a rather
moderate improvement in search time over the original
LC tries. For such an analysis, we assume that n
strings are generated independently by a binary
memoryless source, with p denoting the probability of
emitting a ``1'' (and $q = 1 - p$). We first prove that
the so-called {$\alpha$}-fillup level $F_n (\alpha)$
(i.e., the largest level in a trie with $\alpha$
fraction of nodes present at this level) is
concentrated on two values with high probability:
either $F_n(\alpha) = k_n$ or $F_n ({\alpha}) = k_n +
1$, where $k_n = \log 1/\sqrt{pq} n - |ln(p/q)|/2 ln
3/2 (1 \sqrt{pq}) {\Phi} - 1 (\alpha) \sqrt{ \ln n} +
O(1)$ is an integer and $\Phi(x)$ denotes the normal
distribution function. This result directly yields the
typical depth (search time) $D_n (\alpha)$ in the
$\alpha$-LC tries, namely, we show that with high
probability $D_n(\alpha) \sim C_2 \log \log n$, where
$C_2 = 1/|log(1 - h / \log(1/\sqrt{pq}))|$ for $p \neq
q$ and $h = -p \log p - q \log q$ is the Shannon
entropy rate. This should be compared with recently
found typical depth in the original LC tries, which is
$C_1 \log \log n$, where $C_1 = 1/|log(1 - h) /
log(1/\min\{p, 1 - p\})|$. In conclusion, we observe
that $\alpha$ affects only the lower term of the
$\alpha$-fillup level $F_n(\alpha)$, and the search
time in $\alpha$-LC tries is of the same order as in
the original LC tries.",
acknowledgement = ack-nhfb,
articleno = "44",
keywords = "Digital trees; level-compressed tries; partial fillup;
Poissonization; probabilistic analysis; strings;
trees",
}
@Article{Hershberger:2007:FSS,
author = "John Hershberger and Matthew Maxel and Subhash Suri",
title = "Finding the $k$ shortest simple paths: {A} new
algorithm and its implementation",
journal = j-TALG,
volume = "3",
number = "4",
pages = "45:1--45:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290682",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We describe a new algorithm to enumerate the $k$
shortest simple (loopless) paths in a directed graph
and report on its implementation. Our algorithm is
based on a replacement paths algorithm proposed by
Hershberger and Suri [2001], and can yield a factor
$\Theta(n)$ improvement for this problem. But there is
a caveat: The fast replacement paths subroutine is
known to fail for some directed graphs. However, the
failure is easily detected, and so our k shortest paths
algorithm optimistically uses the fast subroutine, then
switches to a slower but correct algorithm if a failure
is detected. Thus, the algorithm achieves its
$\Theta(n)$ speed advantage only when the optimism is
justified. Our empirical results show that the
replacement paths failure is a rare phenomenon, and the
new algorithm outperforms the current best algorithms;
the improvement can be substantial in large graphs. For
instance, on GIS map data with about 5,000 nodes and
12,000 edges, our algorithm is 4--8 times faster. In
synthetic graphs modeling wireless ad hoc networks, our
algorithm is about 20 times faster.",
acknowledgement = ack-nhfb,
articleno = "45",
keywords = "directed paths; Loop-free paths; path equivalence
class; replacement paths",
}
@Article{Chekuri:2007:EDP,
author = "Chandra Chekuri and Sanjeev Khanna",
title = "Edge-disjoint paths revisited",
journal = j-TALG,
volume = "3",
number = "4",
pages = "46:1--46:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290683",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "The approximability of the maximum edge-disjoint paths
problem (EDP) in directed graphs was seemingly settled
by an $\Omega(m^{1/2} - \epsilon)$-hardness result of
Guruswami et al. [2003], and an $O (\sqrt{m})$
approximation achievable via a natural
multicommodity-flow-based LP relaxation as well as a
greedy algorithm. Here $m$ is the number of edges in
the graph. We observe that the $\Omega(m^{1/2} -
{\epsilon})$-hardness of approximation applies to
sparse graphs, and hence when expressed as a function
of $n$, that is, the number of vertices, only an
$\Omega(n^{1/2} - \epsilon)$-hardness follows. On the
other hand, $O(\sqrt{m})$-approximation algorithms do
not guarantee a sublinear (in terms of $n$)
approximation algorithm for dense graphs. We note that
a similar gap exists in the known results on the
integrality gap of the flow-based LP relaxation: an
$\Omega(\sqrt{n})$ lower bound and $O(\sqrt{m})$ upper
bound. Motivated by this discrepancy in the upper and
lower bounds, we study algorithms for EDP in directed
and undirected graphs and obtain improved approximation
ratios. We show that the greedy algorithm has an
approximation ratio of $O(\min(n^{2/3}, \sqrt{m}))$ in
undirected graphs and a ratio of $O (\min(n^{4/5},
\sqrt{m}))$ in directed graphs. For acyclic graphs we
give an $O(\sqrt{n} \ln n)$ approximation via LP
rounding. These are the first sublinear approximation
ratios for EDP. The results also extend to EDP with
weights and to the uniform-capacity unsplittable flow
problem (UCUFP).",
acknowledgement = ack-nhfb,
articleno = "46",
keywords = "approximation algorithm; Edge-disjoint paths; greedy
algorithm; multicommodity flow relaxation",
}
@Article{Cheriyan:2007:PED,
author = "Joseph Cheriyan and Mohammad R. Salavatipour",
title = "Packing element-disjoint steiner trees",
journal = j-TALG,
volume = "3",
number = "4",
pages = "47:1--47:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290684",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Given an undirected graph $G(V, E)$ with terminal set
$T \subseteq V$, the problem of packing
element-disjoint Steiner trees is to find the maximum
number of Steiner trees that are disjoint on the
nonterminal nodes and on the edges. The problem is
known to be NP-hard to approximate within a factor of
$\Omega(\log n)$, where $n$ denotes $|V|$. We present a
randomized $O(\log n)$-approximation algorithm for this
problem, thus matching the hardness lower bound.
Moreover, we show a tight upper bound of $O(\log n)$ on
the integrality ratio of a natural linear programming
relaxation.",
acknowledgement = ack-nhfb,
articleno = "47",
keywords = "approximation algorithms; element-disjoint; hardness
of approximation; Packing; Steiner trees",
}
@Article{Krivelevich:2007:AAH,
author = "Michael Krivelevich and Zeev Nutov and Mohammad R.
Salavatipour and Jacques Verstraete Yuster and Raphael
Yuster",
title = "Approximation algorithms and hardness results for
cycle packing problems",
journal = j-TALG,
volume = "3",
number = "4",
pages = "48:1--48:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290685",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "The cycle packing number $\nu e(G)$ of a graph $G$ is
the maximum number of pairwise edge-disjoint cycles in
$G$. Computing $\nu e(G)$ is an NP-hard problem. We
present approximation algorithms for computing $\nu e
(G)$ in both undirected and directed graphs. In the
undirected case we analyze a variant of the modified
greedy algorithm suggested by Caprara et al. [2003] and
show that it has approximation ratio $\Theta(\sqrt{\log
n})$, where $n = |V(G)|$. This improves upon the
previous $O(\log n)$ upper bound for the approximation
ratio of this algorithm. In the directed case we
present a $\sqrt{n}$-approximation algorithm. Finally,
we give an $O(n^{2/3})$-approximation algorithm for the
problem of finding a maximum number of edge-disjoint
cycles that intersect a specified subset $S$ of
vertices. We also study generalizations of these
problems. Our approximation ratios are the currently
best-known ones and, in addition, provide upper bounds
on the integrality gap of standard LP-relaxations of
these problems. In addition, we give lower bounds for
the integrality gap and approximability of $\nu e(G)$
in directed graphs. Specifically, we prove a lower
bound of $\Omega(\log n / \log \log n)$ for the
integrality gap of edge-disjoint cycle packing. We also
show that it is quasi-NP-hard to approximate $\nu e(G)$
within a factor of $O(\log 1 - \varepsilon n)$ for any
constant $\varepsilon > 0$. This improves upon the
previously known APX-hardness result for this
problem.",
acknowledgement = ack-nhfb,
articleno = "48",
keywords = "approximation algorithms; Cycle packing;
edge-disjoint; hardness of approximation; integrality
gap",
}
@Article{Albers:2007:EEA,
author = "Susanne Albers and Hiroshi Fujiwara",
title = "Energy-efficient algorithms for flow time
minimization",
journal = j-TALG,
volume = "3",
number = "4",
pages = "49:1--49:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290686",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We study scheduling problems in battery-operated
computing devices, aiming at schedules with low total
energy consumption. While most of the previous work has
focused on finding feasible schedules in deadline-based
settings, in this article we are interested in
schedules that guarantee good response times. More
specifically, our goal is to schedule a sequence of
jobs on a variable-speed processor so as to minimize
the total cost consisting of the energy consumption and
the total flow time of all jobs.\par
We first show that when the amount of work, for any
job, may take an arbitrary value, then no online
algorithm can achieve a constant competitive ratio.
Therefore, most of the article is concerned with
unit-size jobs. We devise a deterministic constant
competitive online algorithm and show that the offline
problem can be solved in polynomial time.",
acknowledgement = ack-nhfb,
articleno = "49",
keywords = "competitive analysis; dynamic programming; flow time;
offline algorithms; online algorithms; Variable-speed
processor",
}
@Article{Chrobak:2007:IOA,
author = "Marek Chrobak and Wojciech Jawor and Ji{\v{r}}{\'\i}
Sgall and Tom{\'a}{\v{s}} Tich{\'y}",
title = "Improved online algorithms for buffer management in
{QoS} switches",
journal = j-TALG,
volume = "3",
number = "4",
pages = "50:1--50:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290687",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider the following buffer management problem
arising in QoS networks: Packets with specified weights
and deadlines arrive at a network switch and need to be
forwarded so that the total weight of forwarded packets
is maximized. Packets not forwarded before their
deadlines are lost. The main result of the article is
an online $64/33 \approx 1.939$-competitive algorithm,
the first deterministic algorithm for this problem with
competitive ratio below 2. For the 2-uniform case we
give an algorithm with ratio $\approx 1.377$ and a
matching lower bound.",
acknowledgement = ack-nhfb,
articleno = "50",
keywords = "Online algorithms; scheduling",
}
@Article{Hajiaghayi:2007:ORN,
author = "Mohammad Taghi Hajiaghayi and Robert D. Kleinberg and
Harald R{\"a}cke and Tom Leighton",
title = "Oblivious routing on node-capacitated and directed
graphs",
journal = j-TALG,
volume = "3",
number = "4",
pages = "51:1--51:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290688",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Oblivious routing algorithms for general undirected
networks were introduced by R{\"a}cke [2002], and this
work has led to many subsequent improvements and
applications. Comparatively little is known about
oblivious routing in general directed networks, or even
in undirected networks with node capacities.\par
We present the first nontrivial upper bounds for both
these cases, providing algorithms for $k$-commodity
oblivious routing problems with competitive ratio
$O(\sqrt{k \log(n)})$ for undirected node-capacitated
graphs and $O(\sqrt{k_n} 1/4 \log(n))$ for directed
graphs. In the special case that all commodities have a
common source or sink, our upper bound becomes
$O(\sqrt{n} \log(n))$ in both cases, matching the lower
bound up to a factor of $\log(n)$. The lower bound
(which first appeared in Azar et al. [2003]) is
obtained on a graph with very high degree. We show
that, in fact, the degree of a graph is a crucial
parameter for node-capacitated oblivious routing in
undirected graphs, by providing an $O (\Delta
\polylog(n))$-competitive oblivious routing scheme for
graphs of degree $\Delta$. For the directed case,
however, we show that the lower bound of
$\Omega(\sqrt{n})$ still holds in low-degree
graphs.\par
Finally, we settle an open question about routing
problems in which all commodities share a common source
or sink. We show that even in this simplified scenario
there are networks in which no oblivious routing
algorithm can achieve a competitive ratio better than
$\Omega(\log n)$.",
acknowledgement = ack-nhfb,
articleno = "51",
keywords = "communication networks; directed graphs;
node-capacitated graphs; Oblivious routing",
}
@Article{Auletta:2007:RSU,
author = "Vincenzo Auletta and Roberto De Prisco and Paolo Penna
and Giuseppe Persiano",
title = "Routing selfish unsplittable traffic",
journal = j-TALG,
volume = "3",
number = "4",
pages = "52:1--52:??",
month = nov,
year = "2007",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1290672.1290689",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:55:31 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider general resource assignment games
involving selfish users/agents in which users compete
for resources and try to be assigned to those which
maximize their own benefits (e.g., try to route their
traffic through links which minimize the latency of
their own traffic). We propose and study a mechanism
design approach in which an allocation mechanism
assigns users to resources and charges the users for
using the resources so as to induce each user to
truthfully report a private piece of information he/she
holds (e.g., how much traffic he/she needs to
transmit). This information is crucial for computing
optimal (or close to optimal) allocations and an agent
could misreport his/her information to induce the
underlying allocation algorithm to output a solution
which he/she likes more (e.g., which assigns better
resources to him/her).\par
For our resource allocation problems, we give an
algorithmic characterization of the solutions for which
truth-telling is a Nash equilibrium. A natural
application of these results is to a scheduling/routing
problem which is the mechanism design counterpart of
the selfish routing game of Koutsoupias and
Papadimitriou [1999]: Each selfish user wants to route
a piece of unsplittable traffic using one of $m$ links
of different speeds so as to minimize his/her own
latency. Our mechanism design counterpart can be seen
as the problem of scheduling selfish jobs on parallel
related machines and is the dual of the problem of
scheduling (unselfish) jobs on parallel selfish
machines studied by Archer and Tardos
[2001].\par
Koutsoupias and Papadimitriou studied an ``anarchic''
scenario in which each user chooses his/her own link,
and this may produce Nash equilibria of cost
$\Omega(\log m / \log \log m)$ times the optimum. Our
mechanism design counterpart is a possible way of
reducing the effect of selfish behavior via suitable
incentives to the agents (i.e., taxes for using the
links). We indeed show that in the resulting game, it
is possible to guarantee an approximation factor of 8
for any number of links/machines (this solution also
works for online settings). However, it remains
impossible to guarantee arbitrarily good approximate
solutions, even for 2 links/machines and even if the
allocation algorithm is allowed superpolynomial time.
This result shows that our scheduling problem with
selfish jobs is more difficult than the scheduling
problem with selfish machines by Archer and Tardos
(which admits exact solutions).\par
We also study some generalizations of this basic
problem.",
acknowledgement = ack-nhfb,
articleno = "52",
keywords = "Algorithmic mechanism design; Nash equilibrium;
scheduling; selfish routing",
}
@Article{Ruzic:2008:UDD,
author = "Milan Ru{\v{z}}i{\'c}",
title = "Uniform deterministic dictionaries",
journal = j-TALG,
volume = "4",
number = "1",
pages = "1:1--1:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328912",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We present a new analysis of the well-known family of
multiplicative hash functions, and improved
deterministic algorithms for selecting ``good'' hash
functions. The main motivation is realization of
deterministic dictionaries with fast lookups and
reasonably fast updates. The model of computation is
the Word RAM, and it is assumed that the machine
word-size matches the size of keys in bits. Many of the
modern solutions to the dictionary problem are weakly
nonuniform, that is, they require a number of constants
to be computed at ``compile time'' for the stated time
bounds to hold. The currently fastest deterministic
dictionary uses constants not known to be computable in
polynomial time. In contrast, our dictionaries do not
require any special constants or instructions, and
running times are independent of word (and key) length.
Our family of dynamic dictionaries achieves a
performance of the following type: lookups in time
$O(t)$ and updates in amortized time $O(n^{1/t})$, for
an appropriate parameter function $t$. Update
procedures require division, whereas searching uses
multiplication only.",
acknowledgement = ack-nhfb,
articleno = "1",
keywords = "Deterministic algorithms; perfect hashing",
}
@Article{Franceschini:2008:NSB,
author = "Gianni Franceschini and Roberto Grossi",
title = "No sorting? better searching!",
journal = j-TALG,
volume = "4",
number = "1",
pages = "2:1--2:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328913",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Questions about order versus disorder in systems and
models have been fascinating scientists over the years.
In computer science, order is intimately related to
sorting, commonly meant as the task of arranging keys
in increasing or decreasing order with respect to an
underlying total order relation. The sorted
organization is amenable for searching a set of n keys,
since each search requires $\Theta(\log n)$ comparisons
in the worst case, which is optimal if the cost of a
single comparison can be considered a constant.
Nevertheless, we prove that disorder implicitly
provides more information than order does. For the
general case of searching an array of multidimensional
keys whose comparison cost is proportional to their
length (and hence which cannot be considered a
constant), we demonstrate that ``suitable'' disorder
gives better bounds than those derivable by using the
natural lexicographic order.\par
We start from previous work done by Andersson et al.
[2001], who proved that $\Theta(k \log \log n / \log
\log(4 + k \log \log n / \log n) + k + \log n)$
character comparisons (or probes) comprise the tight
complexity for searching a plain sorted array of $n$
keys, each of length $k$, arranged in lexicographic
order. We describe a novel permutation of the n keys
that is different from the sorted order. When keys are
kept ``unsorted'' in the array according to this
permutation, the complexity of searching drops to
$\Theta(k + \log n)$ character comparisons (or probes)
in the worst case, which is optimal among all possible
permutations, up to a constant factor. Consequently,
disorder carries more information than does order; this
fact was not observable before, since the latter two
bounds are $\Theta(\log n)$ when $k = O(1)$. More
implications are discussed in the article, including
searching in the bit-probe model.",
acknowledgement = ack-nhfb,
articleno = "2",
keywords = "Implicit data structures; in-place algorithms;
searching; sorting",
}
@Article{Kaplan:2008:THT,
author = "Haim Kaplan and Robert Endre Tarjan",
title = "Thin heaps, thick heaps",
journal = j-TALG,
volume = "4",
number = "1",
pages = "3:1--3:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328914",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "The Fibonacci heap was devised to provide an
especially efficient implementation of Dijkstra's
shortest path algorithm. Although asymptotically
efficient, it is not as fast in practice as other heap
implementations. Expanding on ideas of H{\o}yer [1995],
we describe three heap implementations (two versions of
thin heaps and one of thick heaps) that have the same
amortized efficiency as Fibonacci heaps, but need less
space and promise better practical performance. As part
of our development, we fill in a gap in H{\o}yer's
analysis.",
acknowledgement = ack-nhfb,
articleno = "3",
keywords = "binomial queue; Data structure; decrease key
operation; Fibonacci heap; heap; melding; priority
queue; thick heap; thin heap",
}
@Article{Barbay:2008:ARA,
author = "J{\'e}r{\'e}my Barbay and Claire Kenyon",
title = "Alternation and redundancy analysis of the
intersection problem",
journal = j-TALG,
volume = "4",
number = "1",
pages = "4:1--4:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328915",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "The intersection of sorted arrays problem has
applications in search engines such as Google. Previous
work has proposed and compared deterministic algorithms
for this problem, in an adaptive analysis based on the
encoding size of a certificate of the result (cost
analysis). We define the alternation analysis, based on
the nondeterministic complexity of an instance. In this
analysis we prove that there is a deterministic
algorithm asymptotically performing as well as any
randomized algorithm in the comparison model. We define
the redundancy analysis, based on a measure of the
internal redundancy of the instance. In this analysis
we prove that any algorithm optimal in the redundancy
analysis is optimal in the alternation analysis, but
that there is a randomized algorithm which performs
strictly better than any deterministic algorithm in the
comparison model. Finally, we describe how these
results can be extended beyond the comparison model.",
acknowledgement = ack-nhfb,
articleno = "4",
keywords = "Adaptive analysis; alternation analysis; intersection;
intersection of sorted arrays; randomized algorithm;
redundancy analysis",
}
@Article{Pettie:2008:RMS,
author = "Seth Pettie and Vijaya Ramachandran",
title = "Randomized minimum spanning tree algorithms using
exponentially fewer random bits",
journal = j-TALG,
volume = "4",
number = "1",
pages = "5:1--5:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328916",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "For many fundamental problems there exist randomized
algorithms that are asymptotically optimal and are
superior to the best-known deterministic algorithm.
Among these are the minimum spanning tree (MST)
problem, the MST sensitivity analysis problem, the
parallel connected components and parallel minimum
spanning tree problems, and the local sorting and set
maxima problems. (For the first two problems there are
provably optimal deterministic algorithms with unknown,
and possibly superlinear, running times.) One downside
of the randomized methods for solving these problems is
that they use a number of random bits linear in the
size of input. In this article we develop some general
methods for reducing exponentially the consumption of
random bits in comparison-based algorithms. In some
cases we are able to reduce the number of random bits
from linear to nearly constant, without affecting the
expected running time.\par
Most of our results are obtained by adjusting or
reorganizing existing randomized algorithms to work
well with a pairwise or $O(1)$-wise independent
sampler. The prominent exception, and the main focus of
this article, is a linear-time randomized minimum
spanning tree algorithm that is not derived from the
well-known Karger-Klein-Tarjan algorithm. In many ways
it resembles more closely the deterministic minimum
spanning tree algorithms based on soft heaps. Further,
using our algorithm as a guide, we present a unified
view of the existing ``nongreedy'' minimum spanning
tree algorithms. Concepts from the Karger-Klein-Tarjan
algorithm, such as F-lightness, MST verification, and
sampled graphs, are related to the concepts of edge
corruption, subgraph contractibility, and soft heaps,
which are the basis of the deterministic MST algorithms
of Chazelle and Pettie-Ramachandran.",
acknowledgement = ack-nhfb,
articleno = "5",
keywords = "Graph algorithms; minimum spanning trees; random
sampling",
}
@Article{Roditty:2008:FSF,
author = "Liam Roditty",
title = "A faster and simpler fully dynamic transitive
closure",
journal = j-TALG,
volume = "4",
number = "1",
pages = "6:1--6:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328917",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We obtain a new fully dynamic algorithm for
maintaining the transitive closure of a directed graph.
Our algorithm maintains the transitive closure matrix
in a total running time of $O(mn +({\rm ins} + {\rm
del}) {\cdot} n^2)$, where ins(del) is the number of
insert (delete) operations performed. Here $n$ is the
number of vertices in the graph and $m$ is the initial
number of edges in the graph. Obviously, reachability
queries can be answered in constant time. The algorithm
uses only $O(n^2)$ time which is essentially optimal
for maintaining the transitive closure matrix. Our
algorithm can also support path queries. If $v$ is
reachable from $u$, the algorithm can produce a path
from $u$ to $v$ in time proportional to the length of
the path. The best previously known algorithm for the
problem is due to Demetrescu and Italiano [2000]. Their
algorithm has a total running time of $O(n^3 +({\rm
ins} + {\rm del}) {\cdot} n^2)$. The query time is also
constant. In addition, we also present a simple
algorithm for directed acyclic graphs (DAGs) with a
total running time of $O(mn + {\rm ins} {\cdot} n^2 +
{\rm del})$. Our algorithms are obtained by combining
some new ideas with techniques of Italiano [1986,
1988], King [1999], King and Thorup [2001] and Frigioni
et al. [2001]. We also note that our algorithms are
extremely simple and can be easily implemented.",
acknowledgement = ack-nhfb,
articleno = "6",
keywords = "directed graph; Dynamic graph algorithms;
reachability",
}
@Article{Gabow:2008:FLD,
author = "Harold N. Gabow and Shuxin Nie",
title = "Finding a long directed cycle",
journal = j-TALG,
volume = "4",
number = "1",
pages = "7:1--7:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328918",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Consider a digraph with n vertices. For any fixed
value k, we present linear- and almost-linear-time
algorithms to find a cycle of length $\geq k$, if one
exists. We also find a cycle that has length $\geq \log
n / \log \log n$ in polynomial time, if one exists.
Under an appropriate complexity assumption it is known
to be impossible to improve this guarantee by more than
a $\log \log n$ factor. Our approach is based on
depth-first search.",
acknowledgement = ack-nhfb,
articleno = "7",
keywords = "Approximation algorithms; circumference; cycles;
Hamiltonian cycles; long cycles",
}
@Article{Buchsbaum:2008:RLC,
author = "Adam L. Buchsbaum and Emden R. Gansner and Cecilia M.
Procopiuc and Suresh Venkatasubramanian",
title = "Rectangular layouts and contact graphs",
journal = j-TALG,
volume = "4",
number = "1",
pages = "8:1--8:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328919",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Contact graphs of isothetic rectangles unify many
concepts from applications including VLSI and
architectural design, computational geometry, and GIS.
Minimizing the area of their corresponding rectangular
layouts is a key problem. We study the
area-optimization problem and show that it is NP-hard
to find a minimum-area rectangular layout of a given
contact graph. We present $O(n)$-time algorithms that
construct $O(n^2)$-area rectangular layouts for general
contact graphs and $O(n \log n)$-area rectangular
layouts for trees. (For trees, this is an $O(\log
n)$-approximation algorithm.) We also present an
infinite family of graphs (respectively, trees) that
require $\Omega(n^2)$ (respectively, $\Omega(n \log
n))$ area.\par
We derive these results by presenting a new
characterization of graphs that admit rectangular
layouts, using the related concept of rectangular
duals. A corollary to our results relates the class of
graphs that admit rectangular layouts to
rectangle-of-influence drawings.",
acknowledgement = ack-nhfb,
articleno = "8",
keywords = "Contact graphs; rectangular duals; rectangular
layouts",
}
@Article{Arge:2008:PRT,
author = "Lars Arge and Mark De Berg and Herman Haverkort and Ke
Yi",
title = "The priority {R-tree}: {A} practically efficient and
worst-case optimal {R-tree}",
journal = j-TALG,
volume = "4",
number = "1",
pages = "9:1--9:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328920",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We present the priority R-tree, or PR-tree, which is
the first R-tree variant that always answers a window
query using $O((N / B) 1 - 1/ d + T / B)$ I/Os, where
$N$ is the number of $d$-dimensional (hyper-)
rectangles stored in the R-tree, $B$ is the disk block
size, and $T$ is the output size. This is provably
asymptotically optimal and significantly better than
other R-tree variants, where a query may visit all $N /
B$ leaves in the tree even when $T = 0$. We also
present an extensive experimental study of the
practical performance of the PR-tree using both
real-life and synthetic data. This study shows that the
PR-tree performs similarly to the best-known R-tree
variants on real-life and relatively nicely distributed
data, but outperforms them significantly on more
extreme data.",
acknowledgement = ack-nhfb,
articleno = "9",
keywords = "R-trees",
}
@Article{Gudmundsson:2008:ADO,
author = "Joachim Gudmundsson and Christos Levcopoulos and Giri
Narasimhan and Michiel Smid",
title = "Approximate distance oracles for geometric spanners",
journal = j-TALG,
volume = "4",
number = "1",
pages = "10:1--10:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328921",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Given an arbitrary real constant $\varepsilon > 0$,
and a geometric graph $G$ in $d$-dimensional Euclidean
space with $n$ points, $O(n)$ edges, and constant
dilation, our main result is a data structure that
answers $(1 + \varepsilon)$-approximate
shortest-path-length queries in constant time. The data
structure can be constructed in $O(n \log n)$ time
using $O(n \log n)$ space. This represents the first
data structure that answers $(1 +
\varepsilon)$-approximate shortest-path queries in
constant time, and hence functions as an approximate
distance oracle. The data structure is also applied to
several other problems. In particular, we also show
that approximate shortest-path queries between vertices
in a planar polygonal domain with ``rounded'' obstacles
can be answered in constant time. Other applications
include query versions of closest-pair problems, and
the efficient computation of the approximate dilations
of geometric graphs. Finally, we show how to extend the
main result to answer $(1 + \varepsilon)$-approximate
shortest-path-length queries in constant time for
geometric spanner graphs with $m = \omega(n)$ edges.
The resulting data structure can be constructed in $O(m
+ n \log n)$ time using $O(n \log n)$ space.",
acknowledgement = ack-nhfb,
articleno = "10",
keywords = "approximation algorithm; computational geometry;
geometric graphs; Shortest paths; spanners",
}
@Article{Gandhi:2008:IBS,
author = "Rajiv Gandhi and Magn{\'u}s M. Halld{\'o}rsson and Guy
Kortsarz and Hadas Shachnai",
title = "Improved bounds for scheduling conflicting jobs with
minsum criteria",
journal = j-TALG,
volume = "4",
number = "1",
pages = "11:1--11:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328922",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider a general class of scheduling problems
where a set of conflicting jobs needs to be scheduled
(preemptively or nonpreemptively) on a set of machines
so as to minimize the weighted sum of completion times.
The conflicts among jobs are formed as an arbitrary
conflict graph.\par
Building on the framework of Queyranne and Sviridenko
[2002b], we present a general technique for reducing
the weighted sum of completion-times problem to the
classical makespan minimization problem. Using this
technique, we improve the best-known results for
scheduling conflicting jobs with the min-sum objective,
on several fundamental classes of graphs, including
line graphs, $(k + 1)$-claw-free graphs, and perfect
graphs. In particular, we obtain the first
constant-factor approximation ratio for nonpreemptive
scheduling on interval graphs. We also improve the
results of Kim [2003] for scheduling jobs on line
graphs and for resource-constrained scheduling.",
acknowledgement = ack-nhfb,
articleno = "11",
keywords = "Approximation algorithms; coloring; linear
programming; LP rounding; scheduling; sum
multicoloring",
}
@Article{Guerraoui:2008:CMA,
author = "Rachid Guerraoui and Ron R. Levy and Bastian Pochon
and Jim Pugh",
title = "The collective memory of amnesic processes",
journal = j-TALG,
volume = "4",
number = "1",
pages = "12:1--12:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328923",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "This article considers the problem of robustly
emulating a shared atomic memory over a distributed
message-passing system where processes can fail by
crashing and possibly recover. We revisit the notion of
atomicity in the crash-recovery context and introduce a
generic algorithm that emulates an atomic memory. The
algorithm is instantiated for various settings
according to whether processes have access to local
stable storage, and whether, in every execution of the
algorithm, a sufficient number of processes are assumed
not to crash. We establish the optimality of specific
instances of our algorithm in terms of resilience, log
complexity (number of stable storage accesses needed in
every read or write operation), as well as time
complexity (number of communication steps needed in
every read or write operation). The article also
discusses the impact of considering a multiwriter
versus a single-writer memory, as well as the impact of
weakening the consistency of the memory by providing
safe or regular semantics instead of atomicity.",
acknowledgement = ack-nhfb,
articleno = "12",
keywords = "Atomic registers; crash recovery; \log complexity;
shared-memory emulation",
}
@Article{Karakostas:2008:FAS,
author = "George Karakostas",
title = "Faster approximation schemes for fractional
multicommodity flow problems",
journal = j-TALG,
volume = "4",
number = "1",
pages = "13:1--13:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328924",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We present fully polynomial approximation schemes for
concurrent multicommodity flow problems that run in
time of the minimum possible dependencies on the number
of commodities k. We show that by modifying the
algorithms by Garg and K{\"o}nemann [1998] and
Fleischer [2000], we can reduce their running time on a
graph with n vertices and m edges from
$\tilde{O}(\varepsilon - 2(m^2 + km))$ to
$\tilde{O}(\varepsilon - 2 m^2)$ for an implicit
representation of the output, or $\tilde{O}(\varepsilon
2(m^2 + kn))$ for an explicit representation, where
$\tilde{O}(f)$ denotes a quantity that is $O(f \log
O(1) m)$. The implicit representation consists of a set
of trees rooted at sources (there can be more than one
tree per source), and with sinks as their leaves,
together with flow values for the flow directed from
the source to the sinks in a particular tree. Given
this implicit representation, the approximate value of
the concurrent flow is known, but if we want the
explicit flow per commodity per edge, we would have to
combine all these trees together, and the cost of doing
so may be prohibitive. In case we want to calculate
explicitly the solution flow, we modify our schemes so
that they run in time polylogarithmic in nk(n is the
number of nodes in the network). This is within a
polylogarithmic factor of the trivial lower bound of
time $\Omega(nk)$ needed to explicitly write down a
multicommodity flow of $k$ commodities in a network of
$n$ nodes. Therefore our schemes are within a
polylogarithmic factor of the minimum possible
dependencies of the running time on the number of
commodities $k$.",
acknowledgement = ack-nhfb,
articleno = "13",
keywords = "fully-polynomial time approximation schemes;
Multicommodity flows",
}
@Article{Lemire:2008:HBO,
author = "Daniel Lemire and Owen Kaser",
title = "Hierarchical bin buffering: {Online} local moments for
dynamic external memory arrays",
journal = j-TALG,
volume = "4",
number = "1",
pages = "14:1--14:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328925",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "For a massive I/O array of size n, we want to compute
the first $N$ local moments, for some constant $N$. Our
simpler algorithms partition the array into consecutive
ranges called bins, and apply not only to local-moment
queries, but also to algebraic queries. With $N$
buffers of size $\sqrt{n}$, time complexity drops to
$O(\sqrt{n})$. A more sophisticated approach uses
hierarchical buffering and has a logarithmic time
complexity ($O(b \log b n)$), when using $N$
hierarchical buffers of size $n / b$. Using overlapped
bin buffering, we show that only one buffer is needed,
as with wavelet-based algorithms, but using much less
storage.",
acknowledgement = ack-nhfb,
articleno = "14",
keywords = "hierarchical buffers; polynomial fitting; statistical
queries; Very large arrays",
}
@Article{Anshelevich:2008:PDU,
author = "Elliot Anshelevich and Lisa Zhang",
title = "Path decomposition under a new cost measure with
applications to optical network design",
journal = j-TALG,
volume = "4",
number = "1",
pages = "15:1--15:??",
month = mar,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1328911.1328926",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:15 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We introduce a problem directly inspired by its
application to DWDM (dense wavelength division
multiplexing) network design. We are given a set of
demands to be carried over a network. Our goal is to
choose a route for each demand and to decompose the
network into a collection of edge-disjoint simple
paths. These paths are called optical line systems. The
cost of routing one unit of demand is the number of
line systems with which the demand route overlaps; our
design objective is to minimize the total cost over all
demands. This cost metric is motivated by the need to
minimize O-E-O (optical-electrical-optical) conversions
in optical transmission.\par
For given line systems, it is easy to find the optimal
demand routes. On the other hand, for given demand
routes designing the optimal line systems can be
NP-hard. We first present a 2-approximation for general
network topologies. As optical networks often have low
node degrees, we offer an algorithm that finds the
optimal solution for the special case in which the node
degree is at most 3. Our solution is based on a local
greedy approach.\par
If neither demand routes nor line systems are fixed,
the situation becomes much harder. Even for a
restricted scenario on a 3-regular Hamiltonian network,
no efficient algorithm can guarantee a constant
approximation better than 2. For general topologies, we
offer a simple algorithm with an $O(\log K)$- and an
$O(\log n)$-approximation, where $K$ is the number of
demands and $n$ the number of nodes. This approximation
ratio is almost tight. For rings, a common special
topology, we offer a more complex 3/2-approximation
algorithm.",
acknowledgement = ack-nhfb,
articleno = "15",
keywords = "approximation algorithms; Optical network design; path
decomposition",
}
@Article{Buchsbaum:2008:GE,
author = "Adam L. Buchsbaum",
title = "Guest editorial",
journal = j-TALG,
volume = "4",
number = "2",
pages = "16:1--16:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361193",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
acknowledgement = ack-nhfb,
articleno = "16",
}
@Article{Blandford:2008:CDV,
author = "Daniel K. Blandford and Guy E. Blelloch",
title = "Compact dictionaries for variable-length keys and data
with applications",
journal = j-TALG,
volume = "4",
number = "2",
pages = "17:1--17:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361194",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We consider the problem of maintaining a dynamic
dictionary $T$ of keys and associated data for which
both the keys and data are bit strings that can vary in
length from zero up to the length w of a machine word.
We present a data structure for this
variable-bit-length dictionary problem that supports
constant time lookup and expected amortized
constant-time insertion and deletion. It uses $O(m + 3
n - n \log 2 n)$ bits, where $n$ is the number of
elements in $T$, and $m$ is the total number of bits
across all strings in $T$ (keys and data). Our
dictionary uses an array $A[1 \ldots n]$ in which
locations store variable-bit-length strings. We present
a data structure for this variable-bit-length array
problem that supports worst-case constant-time lookups
and updates and uses $O(m + n)$ bits, where $m$ is the
total number of bits across all strings stored in
$A$.\par
The motivation for these structures is to support
applications for which it is helpful to efficiently
store short varying-length bit strings. We present
several applications, including representations for
semidynamic graphs, order queries on integers sets,
cardinal trees with varying cardinality, and simplicial
meshes of $d$ dimensions. These results either
generalize or simplify previous results.",
acknowledgement = ack-nhfb,
articleno = "17",
keywords = "Compression",
}
@Article{Kolluri:2008:PGM,
author = "Ravikrishna Kolluri",
title = "Provably good moving least squares",
journal = j-TALG,
volume = "4",
number = "2",
pages = "18:1--18:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361195",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We analyze a moving least squares (MLS) interpolation
scheme for reconstructing a surface from point cloud
data. The input is a sufficiently dense set of sample
points that lie near a closed surface F with
approximate surface normals. The output is a
reconstructed surface passing near the sample points.
For each sample point $s$ in the input, we define a
linear point function that represents the local shape
of the surface near $s$. These point functions are
combined by a weighted average, yielding a
three-dimensional function $I$. The reconstructed
surface is implicitly defined as the zero set of
$I$.\par
We prove that the function $I$ is a good approximation
to the signed distance function of the sampled surface
$F$ and that the reconstructed surface is geometrically
close to and isotopic to $F$. Our sampling requirements
are derived from the local feature size function used
in Delaunay-based surface reconstruction algorithms.
Our analysis can handle noisy data provided the amount
of noise in the input dataset is small compared to the
feature size of $F$.",
acknowledgement = ack-nhfb,
articleno = "18",
keywords = "implicit surfaces; interpolation; Reconstruction",
}
@Article{Fusy:2008:DOT,
author = "{\'E}ric Fusy and Gilles Schaeffer and Dominique
Poulalhon",
title = "Dissections, orientations, and trees with applications
to optimal mesh encoding and random sampling",
journal = j-TALG,
volume = "4",
number = "2",
pages = "19:1--19:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361196",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "We present a bijection between some quadrangular
dissections of an hexagon and unrooted binary trees
with interesting consequences for enumeration, mesh
compression, and graph sampling. Our bijection yields
an efficient uniform random sampler for 3-connected
planar graphs, which turns out to be determinant for
the quadratic complexity of the current best-known
uniform random sampler for labelled planar graphs. It
also provides an encoding for the set $P(n)$ of
$n$-edge 3-connected planar graphs that matches the
entropy bound $1/ n \log 2 | P(n)| = 2 + o (1)$ bits
per edge (bpe). This solves a theoretical problem
recently raised in mesh compression as these graphs
abstract the combinatorial part of meshes with
spherical topology. We also achieve the optimal
parametric rate $1 / n \log 2 | P(n, i, j)|$ bpe for
graphs of $P(n)$ with $i$ vertices and $j$ faces,
matching in particular the optimal rate for
triangulations. Our encoding relies on a linear time
algorithm to compute an orientation associated with the
minimal Schnyder wood of a 3-connected planar map. This
algorithm is of independent interest, and it is, for
instance, a key ingredient in a recent straight line
drawing algorithm for 3-connected planar graphs.",
acknowledgement = ack-nhfb,
articleno = "19",
keywords = "Bijection; coding; counting; random generation",
}
@Article{VeghVegh:2008:PDA,
author = "L{\'a}szl{\'o} A. V{\'e}ghV{\'e}gh and Andr{\'a}s A.
Bencz{\'u}r",
title = "Primal-dual approach for directed vertex connectivity
augmentation and generalizations",
journal = j-TALG,
volume = "4",
number = "2",
pages = "20:1--20:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361197",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "In their seminal paper, Frank and Jord{\'a}n
[1995] show that a large class of optimization
problems, including certain directed graph
augmentation, fall into the class of covering
supermodular functions over pairs of sets. They also
give an algorithm for such problems, however, it relies
on the ellipsoid method. Prior to our result,
combinatorial algorithms existed only for the 0--1
valued problem. Our key result is a combinatorial
algorithm for the general problem that includes
directed vertex or S-T connectivity augmentation. The
algorithm is based on Bencz{\'u}r's previous algorithm
for the 0--1 valued case [Bencz{\'u}r 2003].\par
Our algorithm uses a primal-dual scheme for finding
covers of partially ordered sets that satisfy natural
abstract properties as in Frank and Jord{\'a}n. For an
initial (possibly greedy) cover, the algorithm searches
for witnesses for the necessity of each element in the
cover. If no two (weighted) witnesses have a common
cover, the solution is optimal. As long as this is not
the case, the witnesses are gradually exchanged for
smaller ones. Each witness change defines an
appropriate change in the solution; these changes are
finally unwound in a shortest-path manner to obtain a
solution of size one less.",
acknowledgement = ack-nhfb,
articleno = "20",
keywords = "combinatorial algorithm; Vertex connectivity
augmentation",
}
@Article{Sanders:2008:AAS,
author = "Peter Sanders and David Steurer",
title = "An asymptotic approximation scheme for multigraph edge
coloring",
journal = j-TALG,
volume = "4",
number = "2",
pages = "21:1--21:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361198",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "The edge coloring problem considers the assignment of
colors from a minimum number of colors to edges of a
graph such that no two edges with the same color are
incident to the same node. We give polynomial time
algorithms for approximate edge coloring of
multigraphs, that is, parallel edges are allowed. The
best previous algorithms achieve a fixed constant
approximation factor plus a small additive offset. One
of our algorithms achieves solution quality ${\rm opt}
+ \sqrt{9 {\rm opt}/2}$ and has execution time
polynomial in the number of nodes and the logarithm of
the maximum edge multiplicity.",
acknowledgement = ack-nhfb,
articleno = "21",
keywords = "chromatic index; data migration; Edge coloring;
multigraphs",
}
@Article{Chawla:2008:ENT,
author = "Shuchi Chawla and Anupam Gupta and Harald R{\"a}cke",
title = "Embeddings of negative-type metrics and an improved
approximation to generalized sparsest cut",
journal = j-TALG,
volume = "4",
number = "2",
pages = "22:1--22:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361199",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "In this article, we study metrics of negative type,
which are metrics $(V, d)$ such that $\sqrt{d}$ is an
Euclidean metric; these metrics are thus also known as
$\ell_2$-squared metrics. We show how to embed
$n$-point negative-type metrics into Euclidean space
$\ell_2$ with distortion $D = O(\log 3/4 n)$. This
embedding result, in turn, implies an $O(\log 3/4
k)$-approximation algorithm for the Sparsest Cut
problem with nonuniform demands. Another corollary we
obtain is that $n$-point subsets of $\ell_1$ embed into
$\ell_2$ with distortion $O(\log 3/4 n)$.",
acknowledgement = ack-nhfb,
articleno = "22",
keywords = "Approximation algorithm; embedding; metrics;
negative-type metric; sparsest cut",
}
@Article{Chuzhoy:2008:ASN,
author = "Julia Chuzhoy and Anupam Gupta and Joseph (Seffi) Naor
and Amitabh Sinha",
title = "On the approximability of some network design
problems",
journal = j-TALG,
volume = "4",
number = "2",
pages = "23:1--23:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361200",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "Consider the following classical network design
problem: a set of terminals $T = \{ t_i \}$ wishes to
send traffic to a root $r$ in an $n$-node graph $G =(V,
E)$. Each terminal $t_i$ sends $d_i$ units of traffic
and enough bandwidth has to be allocated on the edges
to permit this. However, bandwidth on an edge e can
only be allocated in integral multiples of some base
capacity $u_e$ and hence provisioning $k {\times} u_e$
bandwidth on edge $e$ incurs a cost of $\lceil k
\rceil$ times the cost of that edge. The objective is a
minimum-cost feasible solution.\par
This is one of many network design problems widely
studied where the bandwidth allocation is governed by
side constraints: edges can only allow a subset of
cables to be purchased on them or certain
quality-of-service requirements may have to be
met.\par
In this work, we show that this problem and, in fact,
several basic problems in this general network design
framework cannot be approximated better than
$\Omega(\log \log n)$ unless ${\rm NP} \subseteq {\rm
DTIME}(n O(\log \log \log n))$, where $|V| = n$. In
particular, we show that this inapproximability
threshold holds for (i) the Priority-Steiner Tree
problem, (ii) the (single-sink) Cost-Distance problem,
and (iii) the single-sink version of an even more
fundamental problem, Fixed Charge Network Flow. Our
results provide a further breakthrough in the
understanding of the level of complexity of network
design problems. These are the first nonconstant
hardness results known for all these problems.",
acknowledgement = ack-nhfb,
articleno = "23",
keywords = "cost-distance; fixed charge network flow; Hardness of
approximation; network design; priority Steiner tree",
}
@Article{Immorlica:2008:LCM,
author = "Nicole Immorlica and Mohammad Mahdian and Vahab S.
Mirrokni",
title = "Limitations of cross-monotonic cost-sharing schemes",
journal = j-TALG,
volume = "4",
number = "2",
pages = "24:1--24:??",
month = may,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1361192.1361201",
ISSN = "1549-6325",
bibdate = "Mon Jun 16 11:56:51 MDT 2008",
bibsource = "http://portal.acm.org/",
abstract = "A cost-sharing scheme is a set of rules defining how
to share the cost of a service (often computed by
solving a combinatorial optimization problem) among
serviced customers. A cost-sharing scheme is
cross-monotonic if it satisfies the property that
everyone is better off when the set of people who
receive the service expands. In this article, we
develop a novel technique for proving upper bounds on
the budget-balance factor of cross-monotonic
cost-sharing schemes or the worst-case ratio of
recovered cost to total cost. We apply this technique
to games defined, based on several combinatorial
optimization problems, including the problems of edge
cover, vertex cover, set cover, and metric facility
location and, in each case, derive tight or
nearly-tight bounds. In particular, we show that for
the facility location game, there is no cross-monotonic
cost-sharing scheme that recovers more than a third of
the total cost. This result, together with a recent
1/3-budget-balanced cross-monotonic cost-sharing scheme
of P{\'a}l and Tardos [2003] closes the gap for the
facility location game. For the vertex cover and set
cover games, we show that no cross-monotonic
cost-sharing scheme can recover more than a $O(n -
1/3)$ and $O(1 / n)$ fraction of the total cost,
respectively. Finally, we study the implications of our
results on the existence of group-strategyproof
mechanisms. We show that every group-strategyproof
mechanism corresponds to a cost-sharing scheme that
satisfies a condition weaker than cross-monotonicity.
Using this, we prove that group-strategyproof
mechanisms satisfying additional properties give rise
to cross-monotonic cost-sharing schemes and therefore
our upper bounds hold.",
acknowledgement = ack-nhfb,
articleno = "24",
keywords = "Cross-monotonic cost-sharing schemes;
group-strategyproof mechanism design; probabilistic
method",
}
@Article{Dinitz:2008:OAS,
author = "Yefim Dinitz and Shay Solomon",
title = "Optimality of an algorithm solving the {Bottleneck
Tower of Hanoi} problem",
journal = j-TALG,
volume = "4",
number = "3",
pages = "25:1--25:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367065",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We study the Bottleneck Tower of Hanoi puzzle posed by
D. Wood in 1981. There, a relaxed placement rule allows
a larger disk to be placed {\em higher\/} than a
smaller one if their size difference is less than a
pregiven value $k$. A shortest sequence of moves
(optimal algorithm) transferring all the disks placed
on some peg in decreasing order of size, to another peg
in the same order is in question. In 1992, D. Poole
suggested a natural disk-moving strategy for this
problem, and computed the length of the shortest move
sequence under its framework. However, other strategies
were overlooked, so the lower bound/optimality question
remained open. In 1998, Benditkis, Berend, and Safro
proved the optimality of Poole's algorithm for the
first nontrivial case $k = 2$. We prove Poole's
algorithm to be optimal in the general case.",
acknowledgement = ack-nhfb,
articleno = "25",
keywords = "Optimality proofs; Tower of Hanoi",
}
@Article{Alonso:2008:DP,
author = "Laurent Alonso and Edward M. Reingold",
title = "Determining plurality",
journal = j-TALG,
volume = "4",
number = "3",
pages = "26:1--26:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367066",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Given a set of $n$ elements, each of which is colored
one of $c$ colors, we must determine an element of the
plurality (most frequently occurring) color by pairwise
equal/unequal color comparisons of elements. We prove
that $(c - 1)(n - c)/2$ color comparisons are necessary
in the worst case to determine the plurality color and
give an algorithm requiring $(0.775 c + 5.9) n +
O(c^2)$ color comparisons for $c \geq 9$.",
acknowledgement = ack-nhfb,
articleno = "26",
keywords = "Algorithm analysis; majority problem; plurality
problem",
}
@Article{Alonso:2008:ACL,
author = "Laurent Alonso and Edward M. Reingold",
title = "Average-case lower bounds for the plurality problem",
journal = j-TALG,
volume = "4",
number = "3",
pages = "27:1--27:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367067",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Given a set of $n$ elements, each of which is colored
one of $c \geq 2$ colors, we have to determine an
element of the plurality (most frequently occurring)
color by pairwise equal/unequal color comparisons of
elements. We derive lower bounds for the expected
number of color comparisons when the $c^n$ colorings
are equally probable. We prove a general lower bound of
$c / 3 n - O(\sqrt n)$ for $c \geq 2$; we prove the
stronger particular bounds of $7/6 n - O(\sqrt n)$ for
$c = 3$, $54/35 n - O(\sqrt n)$ for $c = 4$, $607/315 n
O(\sqrt n)$ for $c = 5$, $1592/693 n - O(\sqrt n)$ for
$c = 6$, $7985/3003 n - O(\sqrt n)$ for $c = 7$, and
$19402/6435 n - O(\sqrt n)$ for $c = 8$.",
acknowledgement = ack-nhfb,
articleno = "27",
keywords = "Algorithm analysis; majority problem; plurality
problem",
}
@Article{Lu:2008:BPS,
author = "Hsueh-I Lu and Chia-Chi Yeh",
title = "Balanced parentheses strike back",
journal = j-TALG,
volume = "4",
number = "3",
pages = "28:1--28:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367068",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "An {\em ordinal tree\/} is an arbitrary rooted tree
where the children of each node are ordered. Succinct
representations for ordinal trees with efficient query
support have been extensively studied. The best
previously known result is due to Geary et al. [2004b,
pages 1--10]. The number of bits required by their
representation for an $n$-node ordinal tree $T$ is $2 n
+ o(n)$, whose first-order term is
information-theoretically optimal. Their representation
supports a large set of $O(1)$-time queries on $T$.
Based upon a balanced string of $2 n$ parentheses, we
give an improved $2 n + o(n)$-bit representation for
$T$. Our improvement is two-fold: First, the set of
$O(1)$-time queries supported by our representation is
a proper superset of that supported by the
representation of Geary, Raman, and Raman. Second, it
is also much easier for our representation to support
new queries by simply adding new auxiliary strings.",
acknowledgement = ack-nhfb,
articleno = "28",
keywords = "Succinct data structures; XML document
representation",
}
@Article{Roditty:2008:RSR,
author = "Iam Roditty and Mikkel Thorup and Uri Zwick",
title = "Roundtrip spanners and roundtrip routing in directed
graphs",
journal = j-TALG,
volume = "4",
number = "3",
pages = "29:1--29:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367069",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We introduce the notion of {\em roundtrip-spanners\/}
of weighted {\em directed\/} graphs and describe
efficient algorithms for their construction. We show
that for every integer $k \geq 1$ and any $\epsilon >
0$, any directed graph on $n$ vertices with edge
weights in the range $[1, W]$ has a $(2 k +
\epsilon)$-roundtrip-spanner with $O(\min(k^2
/\epsilon)) n^{1 + 1/ k} (\log(nW), (k /\epsilon)^2
n^{1 + 1/ k} ,(log n)^{2-1/k})$ edges. We then extend
these constructions and obtain compact roundtrip
routing schemes. For every integer $k$ \geq 1 and every
$\epsilon > 0$, we describe a roundtrip routing scheme
that has stretch $4 k + \epsilon$ , and uses at each
vertex a routing table of size $\Otilde((k^2 /
\epsilon) n^{1/k} \log(nW))$. We also show that any
weighted directed graph with {\em arbitrary/\/}
positive edge weights has a 3-roundtrip-spanner with
$O(n^{3/2})$ edges. This result is optimal. Finally, we
present a stretch 3 roundtrip routing scheme that uses
local routing tables of size $\Otilde(n^{1/2})$. This
routing scheme is essentially optimal. The
roundtrip-spanner constructions and the roundtrip
routing schemes for directed graphs that we describe
are only slightly worse than the best available
spanners and routing schemes for undirected graphs. Our
roundtrip routing schemes substantially improve
previous results of Cowen and Wagner. Our results are
obtained by combining ideas of Cohen, Cowen and Wagner,
Thorup and Zwick, with some new ideas.",
acknowledgement = ack-nhfb,
articleno = "29",
keywords = "distances; roundtrip; Routing; shortest paths;
spanners",
}
@Article{Gu:2008:OBD,
author = "Qian-Ping Gu and Hisao Tamaki",
title = "Optimal branch-decomposition of planar graphs in
{$O(n^3)$} time",
journal = j-TALG,
volume = "4",
number = "3",
pages = "30:1--30:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367070",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We give an $O(n^3)$ time algorithm for constructing a
minimum-width branch-decomposition of a given planar
graph with $n$ vertices. This is achieved through a
refinement to the previously best known algorithm of
Seymour and Thomas, which runs in $O(n^4)$ time.",
acknowledgement = ack-nhfb,
articleno = "30",
keywords = "Branch-decompositions; planar graphs",
}
@Article{Czumaj:2008:TEM,
author = "Artur Czumaj and Christian Sohler",
title = "Testing {Euclidean} minimum spanning trees in the
plane",
journal = j-TALG,
volume = "4",
number = "3",
pages = "31:1--31:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367071",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Given a Euclidean graph $G$ over a set $P$ of $n$
points in the plane, we are interested in verifying
whether $G$ is a Euclidean minimum spanning tree (EMST)
of $P$ or $G$ differs from it in more than $\epsilon n$
edges. We assume that $G$ is given in adjacency list
representation and the point/vertex set $P$ is given in
an array. We present a property testing algorithm that
accepts graph $G$ if it is an EMST of $P$ and that
rejects with probability at least $2/3$ if $G$ differs
from every EMST of $P$ in more than $\epsilon, n$
edges. Our algorithm runs in $O(\sqrt n / \epsilon
\cdot \log^2(n / \epsilon))$ time and has a query
complexity of $O(\sqrt n / \epsilon \cdot \log(n /
\epsilon))$.",
acknowledgement = ack-nhfb,
articleno = "31",
keywords = "Euclidean minimum spanning tree; property testing;
randomized algorithms",
}
@Article{Makinen:2008:DEC,
author = "Veli M{\"a}kinen and Gonzalo Navarro",
title = "Dynamic entropy-compressed sequences and full-text
indexes",
journal = j-TALG,
volume = "4",
number = "3",
pages = "32:1--32:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367072",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We give new solutions to the Searchable Partial Sums
with Indels problem. Given a sequence of $n$ $k$-bit
numbers, we present a structure taking $kn + o(kn)$
bits of space, able of performing operations {\em sum},
{\em search}, {\em insert}, and {\em delete}, all in
$O(\log n)$ worst-case time, for any $k = O(\log n)$.
This extends previous results by Hon et al. [2003c]
achieving the same space and $O (\log n / \log \log n)$
time complexities for the queries, yet offering
complexities for {\em insert\/} and {\em delete\/} that
are amortized and worse than ours, and supported only
for $k = O(1)$. Our result matches an existing lower
bound for large values of $k$.\par
We also give new solutions to the Dynamic Sequence
problem. Given a sequence of $n$ symbols in the range
$[1,\sigma]$ with binary zero-order entropy $H_0$, we
present a dynamic data structure that requires $n_0 +
o(n \log \sigma)$ bits of space, which is able of
performing {\em rank\/} and {\em select}, as well as
inserting and deleting symbols at arbitrary positions,
in $O(\log n log \sigma)$ time. Our result is the {\em
first\/} entropy-bound dynamic data structure for {\em
rank\/} and {\em select\/} over general
sequences.\par
In the case $\sigma = 2$, where both previous problems
coincide, we improve the dynamic solution of Hon et al.
[2003c] in that we compress the sequence. The only
previous result with entropy-bound space for dynamic
binary sequences is by Blandford and Blelloch [2004],
which has the same complexities as our structure, but
does not achieve constant 1 multiplying the entropy
term in the space complexity.\par
Finally, we present a new dynamic compressed full-text
self-index, for a collection of texts over an alphabet
of size {\sigma}, of overall length $n$ and $h$th order
empirical entropy $H_h$. The index requires $nH_h + o(n
\log \sigma)$ bits of space, for any $h \leq \alpha
\log_\sigma n$ and constant $0$.\par
An important result we prove in this paper is that the
wavelet tree of the Burrows-Wheeler transform of a
text, if compressed with a technique that achieves
zero-order compression locally (e.g., Raman et al.
[2002]), automatically achieves $h$th order entropy
space for any $h$. This unforeseen relation is
essential for the results of the previous paragraph,
but it also derives into significant simplifications on
many existing static compressed full-text self-indexes
that build on wavelet trees.",
acknowledgement = ack-nhfb,
articleno = "32",
keywords = "Compressed dynamic data structures; compressed text
databases; entropy; partial sums; sequences",
}
@Article{Kowalski:2008:WAD,
author = "Dariusz R. Kowalski and Alexander A. Shvartsman",
title = "Writing-all deterministically and optimally using a
nontrivial number of asynchronous processors",
journal = j-TALG,
volume = "4",
number = "3",
pages = "33:1--33:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367073",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "The problem of performing $n$ tasks on $p$
asynchronous or undependable processors is a basic
problem in distributed computing. This article
considers an abstraction of this problem called {\em
Write-All: using p processors write 1's into all
locations of an array of size n}. In this problem
writing 1 abstracts the notion of performing a simple
task. Despite substantial research, there is a dearth
of efficient deterministic asynchronous algorithms for
{\em Write-All/}. Efficiency of algorithms is measured
in terms of {\em work\/} that accounts for all local
steps performed by the processors in solving the
problem. Thus, an optimal algorithm would have work
$\Theta(n)$, however it is known that optimality cannot
be achieved when $p = \Omega(n)$. The quest then is to
obtain work-optimal solutions for this problem using a
nontrivial, compared to $n$, number of processors $p$.
The algorithm presented in this article has work
complexity of $O(n + p^{2 + \epsilon})$, and it
achieves work optimality for $p = O(n^{1/(2 +
\epsilon)})$ for any $\epsilon > 0$, while the previous
best result achieved optimality for $p \leq 4 \sqrt n /
\log n$. Additionally, the new result uses {\em only\/}
the atomic read/write memory, without resorting to
using the test-and-set primitive that was necessary in
the previous solution.",
acknowledgement = ack-nhfb,
articleno = "33",
keywords = "Asynchrony; distributed algorithms; shared memory;
work; Write-All",
}
@Article{Even:2008:ACR,
author = "Guy Even and Retsef Levi and Dror Rawitz and Baruch
Schieber and Shimon (Moni) Shahar and Maxim
Sviridenko",
title = "Algorithms for capacitated rectangle stabbing and lot
sizing with joint set-up costs",
journal = j-TALG,
volume = "4",
number = "3",
pages = "34:1--34:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367074",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "In the rectangle stabbing problem, we are given a set
of axis parallel rectangles and a set of horizontal and
vertical lines, and our goal is to find a minimum size
subset of lines that intersect all the rectangles. In
this article, we study the capacitated version of this
problem in which the input includes an integral
capacity for each line. The capacity of a line bounds
the number of rectangles that the line can cover. We
consider two versions of this problem. In the first,
one is allowed to use only a single copy of each line
({\em hard capacities\/}), and in the second, one is
allowed to use multiple copies of every line, but the
multiplicities are counted in the size (or weight) of
the solution ({\em soft capacities\/}).\par
We present an exact polynomial-time algorithm for the
weighted one dimensional case with hard capacities that
can be extended to the one dimensional weighted case
with soft capacities. This algorithm is also extended
to solve a certain capacitated multi-item {\em
lot-sizing\/} inventory problem with joint set-up
costs. For the case of $d$-dimensional rectangle
stabbing with soft capacities, we present a
$3d$-approximation algorithm for the unweighted case.
For $d$-dimensional rectangle stabbing problem with
hard capacities, we present a bi-criteria algorithm
that computes $4d$-approximate solutions that use at
most two copies of every line. Finally, we present
hardness results for rectangle stabbing when the
dimension is part of the input and for a
two-dimensional weighted version with hard
capacities.",
acknowledgement = ack-nhfb,
articleno = "34",
keywords = "Approximation algorithms; capacitated covering; lot
sizing; rectangle stabbing",
}
@Article{Zhang:2008:CCP,
author = "Cun-Quan Zhang and Yongbin Ou",
title = "Clustering, community partition and disjoint spanning
trees",
journal = j-TALG,
volume = "4",
number = "3",
pages = "35:1--35:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367075",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Clustering method is one of the most important tools
in statistics. In a graph theory model, clustering is
the process of finding all dense subgraphs. A
mathematically well-defined measure for graph density
is introduced in this article as follows. Let $G = (V,
E)$ be a graph (or multi-graph) and $H$ be a subgraph
of $G$. The dynamic density of $H$ is the greatest
integer $k$ such that $\min_\forall P \{| E (H / P)|/|
V (H / P)| - 1\} > k$ where the minimum is taken over
all possible partitions $P$ of the vertex set of $H$,
and $H / P$ is the graph obtained from $H$ by
contracting each part of $P$ into a single vertex. A
subgraph $H$ of $G$ is a level-$k$ community if $H$ is
a maximal subgraph of $G$ with dynamic density at least
$k$. An algorithm is designed in this paper to detect
all level-$h$ communities of an input multi-graph $G$.
The worst-case complexity of this algorithm is upper
bounded by $O(|V(G)|^2 h^2)$. This new method is one of
few available clustering methods that are
mathematically well-defined, supported by rigorous
mathematical proof and able to achieve the optimization
goal with polynomial complexity. As a byproduct, this
algorithm also can be applied for finding edge-disjoint
spanning trees of a multi-graph. The worst-case
complexity is lower than all known algorithms for
multi-graphs.",
acknowledgement = ack-nhfb,
articleno = "35",
keywords = "clustering; community; dense subgraph; dynamic
density; hierarchical clustering; polynomial algorithm;
Spanning trees",
}
@Article{Yu:2008:IAM,
author = "Hung-I. Yu and Tzu-Chin Lin and Biing-Feng Wang",
title = "Improved algorithms for the minmax-regret 1-center and
1-median problems",
journal = j-TALG,
volume = "4",
number = "3",
pages = "36:1--36:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367076",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "In this article, efficient algorithms are presented
for the minmax-regret 1-center and 1-median problems on
a general graph and a tree with uncertain vertex
weights. For the minmax-regret 1-center problem on a
general graph, we improve the previous upper bound from
$O(mn^2 \log n)$ to $O(mn \log n)$. For the problem on
a tree, we improve the upper bound from $O(n^2)$ to
$O(n \log^2 n)$. For the minmax-regret 1-median problem
on a general graph, we improve the upper bound from
$O(mn^2 \log n)$ to $O(mn^2 + n^3 \log n)$. For the
problem on a tree, we improve the upper bound from $O(n
\log^2 n)$ to $O(n \log n)$.",
acknowledgement = ack-nhfb,
articleno = "36",
keywords = "centers; general graphs; Location theory; medians;
minmax-regret optimization; trees",
}
@Article{Abraham:2008:CNI,
author = "Ittai Abraham and Cyril Gavoille and Dahlia Malkhi and
Noam Nisan and Mikkel Thorup",
title = "Compact name-independent routing with minimum
stretch",
journal = j-TALG,
volume = "4",
number = "3",
pages = "37:1--37:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367077",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Given a weighted undirected network with arbitrary
node names, we present a compact routing scheme, using
a $\Otilde(\sqrt n)$ space routing table at each node,
and routing along paths of stretch 3, that is, at most
thrice as long as the minimum cost paths. This is
optimal in a very strong sense. It is known that no
compact routing using $o(n)$ space per node can route
with stretch below 3. Also, it is known that any
stretch below 5 requires $\Omega (\sqrt n)$ space per
node.",
acknowledgement = ack-nhfb,
articleno = "37",
keywords = "Compact routing",
}
@Article{Pruhs:2008:GBR,
author = "Kirk Pruhs and Patchrawat Uthaisombut and Gerhard
Woeginger",
title = "Getting the best response for your erg",
journal = j-TALG,
volume = "4",
number = "3",
pages = "38:1--38:??",
month = jun,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1367064.1367078",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:06 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider the speed scaling problem of minimizing
the average response time of a collection of
dynamically released jobs subject to a constraint $A$
on energy used. We propose an algorithmic approach in
which an energy optimal schedule is computed for a huge
$A$, and then the energy optimal schedule is maintained
as $A$ decreases. We show that this approach yields an
efficient algorithm for equi-work jobs. We note that
the energy optimal schedule has the surprising feature
that the job speeds are not monotone functions of the
available energy. We then explain why this algorithmic
approach is problematic for arbitrary work jobs.
Finally, we explain how to use the algorithm for
equi-work jobs to obtain an algorithm for arbitrary
work jobs that is $O(1)$-approximate with respect to
average response time, given an additional factor of
$(1 + \epsilon)$ energy.",
acknowledgement = ack-nhfb,
articleno = "38",
keywords = "frequency scaling; power management; scheduling; Speed
scaling; voltage scaling",
}
@Article{Ajwani:2008:AIT,
author = "Deepak Ajwani and Tobias Friedrich and Ulrich Meyer",
title = "An {$O(n^{2.75})$} algorithm for incremental
topological ordering",
journal = j-TALG,
volume = "4",
number = "4",
pages = "39:1--39:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383370",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We present a simple algorithm which maintains the
topological order of a directed acyclic graph (DAG)
with $n$ nodes, under an online edge insertion
sequence, in $O(n^{2.75})$ time, independent of the
number $m$ of edges inserted. For dense DAGs, this is
an improvement over the previous best result of $O(\min
m^{3/2} \log n, m^{3/2} + n^2 \log n)$ by Katriel and
Bodlaender [2006]. We also provide an empirical
comparison of our algorithm with other algorithms for
incremental topological sorting.",
acknowledgement = ack-nhfb,
articleno = "39",
keywords = "Dynamic algorithms; graphs; online algorithms;
topological order",
}
@Article{Ibarra:2008:FDA,
author = "Louis Ibarra",
title = "Fully dynamic algorithms for chordal graphs and split
graphs",
journal = j-TALG,
volume = "4",
number = "4",
pages = "40:1--40:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383371",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We present the first dynamic algorithm that maintains
a clique tree representation of a chordal graph and
supports the following operations: (1) query whether
deleting or inserting an arbitrary edge preserves
chordality; and (2) delete or insert an arbitrary edge,
provided it preserves chordality. We give two
implementations. In the first, each operation runs in
$O(n)$ time, where $n$ is the number of vertices. In
the second, an insertion query runs in $O(\log^2 n)$
time, an insertion in $O(n)$ time, a deletion query in
$O(n)$ time, and a deletion in $O(n \log n)$ time. We
also present a data structure that allows a deletion
query to run in $O(\sqrt m)$ time in either
implementation, where $m$ is the current number of
edges. Updating this data structure after a deletion or
insertion requires $O(m)$ time.\par
We also present a very simple dynamic algorithm that
supports each of the following operations in $O(1)$
time on a general graph: (1) query whether the graph is
split, and (2) delete or insert an arbitrary edge.",
acknowledgement = ack-nhfb,
articleno = "40",
keywords = "chordal graphs; clique trees; Dynamic graph
algorithms; split graphs",
}
@Article{Korman:2008:DRS,
author = "Amos Korman and David Peleg",
title = "Dynamic routing schemes for graphs with low local
density",
journal = j-TALG,
volume = "4",
number = "4",
pages = "41:1--41:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383372",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "This article studies approximate distributed routing
schemes on dynamic communication networks. The work
focuses on dynamic weighted general graphs where the
vertices of the graph are fixed, but the weights of the
edges may change. Our main contribution concerns
bounding the cost of adapting to dynamic changes. The
update efficiency of a routing scheme is measured by
the time needed in order to update the routing scheme
following a weight change. A naive dynamic routing
scheme, which updates all vertices following a weight
change, requires $\Omega(\hbox{\em Diam\/})$ time in
order to perform the updates after every weight change,
where {\em Diam\/} is the diameter of the underlying
graph. In contrast, this article presents approximate
dynamic routing schemes with average time complexity
$\Thetatilde(d)$ per topological change, where $d$ is
the local density parameter of the underlying graph.
Following a weight change, our scheme never incurs more
than {\em Diam\/} time; thus, our scheme is
particularly efficient on graphs which have low local
density and large diameter. The article also
establishes upper and lower bounds on the size of the
databases required by the scheme at each site.",
acknowledgement = ack-nhfb,
articleno = "41",
keywords = "distributed algorithms; dynamic networks; Routing
schemes",
}
@Article{Cohen:2008:LGG,
author = "Reuven Cohen and Pierre Fraigniaud and David Ilcinkas
and Amos Korman and David Peleg",
title = "Label-guided graph exploration by a finite automaton",
journal = j-TALG,
volume = "4",
number = "4",
pages = "42:1--42:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383373",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "A finite automaton, simply referred to as a {\em
robot}, has to explore a graph, that is, visit all the
nodes of the graph. The robot has no a priori knowledge
of the topology of the graph, nor of its size. It is
known that for any $k$-state robot, there exists a
graph of maximum degree 3 that the robot cannot
explore. This article considers the effects of allowing
the system designer to add short labels to the graph
nodes in a preprocessing stage, for helping the
exploration by the robot. We describe an exploration
algorithm that, given appropriate 2-bit labels (in
fact, only 3-valued labels), allows a robot to explore
all graphs. Furthermore, we describe a suitable
labeling algorithm for generating the required labels
in linear time. We also show how to modify our labeling
scheme so that a robot can explore all graphs of
bounded degree, given appropriate 1-bit labels. In
other words, although there is no robot able to explore
all graphs of maximum degree 3, there is a robot $R$,
and a way to color in black or white the nodes of any
bounded-degree graph $G$, so that $R$ can explore the
colored graph $G$. Finally, we give impossibility
results regarding graph exploration by a robot with no
internal memory (i.e., a single-state automaton).",
acknowledgement = ack-nhfb,
articleno = "42",
keywords = "Distributed algorithms; graph exploration; labeling
schemes",
}
@Article{Suzuki:2008:DSP,
author = "Akiko Suzuki and Takeshi Tokuyama",
title = "Dense subgraph problems with output-density
conditions",
journal = j-TALG,
volume = "4",
number = "4",
pages = "43:1--43:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383374",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider the dense subgraph problem that extracts a
subgraph, with a prescribed number of vertices, having
the maximum number of edges (or total edge weight, in
the weighted case) in a given graph. We give
approximation algorithms with improved theoretical
approximation ratios assuming that the density of the
optimal output subgraph is high, where density is the
ratio of number of edges (or sum of edge weights) to
the number of edges in the clique on the same number of
vertices. Moreover, we investigate the case where the
input graph is bipartite and design a randomized
pseudopolynomial time approximation scheme that can
become a randomized PTAS, even if the size of the
optimal output graph is comparatively small. This is a
significant improvement in a theoretical sense, since
no constant-ratio approximation algorithm was known
previously if the output graph has o(n) vertices.",
acknowledgement = ack-nhfb,
articleno = "43",
keywords = "approximation algorithms; Combinatorial optimization;
dense subgraph; randomized algorithms",
}
@Article{Bar-Noy:2008:DCF,
author = "Amotz Bar-Noy and Panagiotis Cheilaris and Shakhar
Smorodinsky",
title = "Deterministic conflict-free coloring for intervals:
{From} offline to online",
journal = j-TALG,
volume = "4",
number = "4",
pages = "44:1--44:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383375",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We investigate deterministic algorithms for a
frequency assignment problem in cellular networks. The
problem can be modeled as a special vertex coloring
problem for hypergraphs: In every hyperedge there must
exist a vertex with a color that occurs exactly once in
the hyperedge (the conflict-free property). We
concentrate on a special case of the problem, called
conflict-free coloring for intervals. We introduce a
hierarchy of four models for the aforesaid problem: (i)
static, (ii) dynamic offline, (iii) dynamic online with
absolute positions, and (iv) dynamic online with
relative positions. In the dynamic offline model, we
give a deterministic algorithm that uses at most
log$_{3/2}$ $n$ + 1 \&;approx; 1.71 log$_2$ n colors
and show inputs that force any algorithm to use at
least 3 log$_5$ $n$ + 1 {\SGMLapprox} 1.29 log$_2$ $n$
colors. For the online absolute-positions model, we
give a deterministic algorithm that uses at most
3\lceil log$_3$ $n$ {\rceil} {\SGMLapprox} 1.89 log$_2$
$n$ colors. To the best of our knowledge, this is the
first deterministic online algorithm using $O(\log n)$
colors in a nontrivial online model. In the online
relative-positions model, we resolve an open problem by
showing a tight analysis on the number of colors used
by the first-fit greedy online algorithm. We also
consider conflict-free coloring only with respect to
intervals that contain at least one of the two extreme
points.",
acknowledgement = ack-nhfb,
articleno = "44",
keywords = "cellular networks; coloring; conflict free; frequency
assignment; Online algorithms",
}
@Article{Chandran:2008:IAO,
author = "Nishanth Chandran and Ryan Moriarty and Rafail
Ostrovsky and Omkant Pandey and Mohammad Ali Safari and
Amit Sahai",
title = "Improved algorithms for optimal embeddings",
journal = j-TALG,
volume = "4",
number = "4",
pages = "45:1--45:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383376",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "In the last decade, the notion of metric embeddings
with small distortion has received wide attention in
the literature, with applications in combinatorial
optimization, discrete mathematics, and
bio-informatics. The notion of embedding is, given two
metric spaces on the same number of points, to find a
bijection that minimizes maximum Lipschitz and
bi-Lipschitz constants. One reason for the popularity
of the notion is that algorithms designed for one
metric space can be applied to a different one, given
an embedding with small distortion. The better
distortion, the better the effectiveness of the
original algorithm applied to a new metric
space.\par
The goal recently studied by Kenyon et al. [2004] is to
consider all possible embeddings between two {\em
finite\/} metric spaces and to find the best possible
one; that is, consider a single objective function over
the space of all possible embeddings that minimizes the
distortion. In this article we continue this important
direction. In particular, using a theorem of Albert and
Atkinson [2005], we are able to provide an algorithm to
find the optimal bijection between two line metrics,
provided that the optimal distortion is smaller than
13.602. This improves the previous bound of 3 + 2\sqrt
2, solving an open question posed by Kenyon et al.
[2004]. Further, we show an inherent limitation of
algorithms using the ``forbidden pattern'' based
dynamic programming approach, in that they cannot find
optimal mapping if the optimal distortion is more than
7 + 4\sqrt 3 ({\SGMLsime} 13.928). Thus, our results
are almost optimal for this method. We also show that
previous techniques for general embeddings apply to a
(slightly) more general class of metrics.",
acknowledgement = ack-nhfb,
articleno = "45",
keywords = "dynamic programming; forbidden patterns; line
embeddings; metric spaces; Optimal metric embeddings;
shape matching",
}
@Article{Alon:2008:OEM,
author = "Noga Alon and Mihai B{\~a}doiu and Erik D. Demaine and
Martin Farach-Colton and Mohammadtaghi Hajiaghayi and
Anastasios Sidiropoulos",
title = "Ordinal embeddings of minimum relaxation: {General}
properties, trees, and ultrametrics",
journal = j-TALG,
volume = "4",
number = "4",
pages = "46:1--46:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383377",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We introduce a new notion of embedding, called {\em
minimum-relaxation ordinal embedding}, parallel to the
standard notion of minimum-distortion (metric)
embedding. In an ordinal embedding, it is the relative
order between pairs of distances, and not the distances
themselves, that must be preserved as much as possible.
The (multiplicative) relaxation of an ordinal embedding
is the maximum ratio between two distances whose
relative order is inverted by the embedding. We develop
several worst-case bounds and approximation algorithms
on ordinal embedding. In particular, we establish that
ordinal embedding has many qualitative differences from
metric embedding, and we capture the ordinal behavior
of ultrametrics and shortest-path metrics of unweighted
trees.",
acknowledgement = ack-nhfb,
articleno = "46",
keywords = "distortion; Metrics; ordinal embedding; relaxation",
}
@Article{Blaser:2008:NAA,
author = "Markus Bl{\"a}ser",
title = "A new approximation algorithm for the asymmetric {TSP}
with triangle inequality",
journal = j-TALG,
volume = "4",
number = "4",
pages = "47:1--47:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383378",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We present a polynomial time factor 0.999 {\SGMLcdot}
log $n$ approximation algorithm for the asymmetric
traveling salesperson problem with triangle
inequality.",
acknowledgement = ack-nhfb,
articleno = "47",
keywords = "Approximation algorithm; cycle cover; traveling
salesman problem; TSP",
}
@Article{Boyar:2008:RWO,
author = "Joan Boyar and Paul Medvedev",
title = "The relative worst order ratio applied to seat
reservation",
journal = j-TALG,
volume = "4",
number = "4",
pages = "48:1--48:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383379",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "The seat reservation problem is the problem of
assigning passengers to seats on a train with $n$ seats
and $k$ stations enroute in an online manner. The
performance of algorithms for this problem is studied
using the relative worst order ratio, a fairly new
measure for the quality of online algorithms, which
allows for direct comparisons between algorithms. This
study has yielded new separations between algorithms.
For example, for both variants of the problem
considered, using the relative worst order ratio,
First-Fit and Best-Fit are shown to be better than
Worst-Fit.",
acknowledgement = ack-nhfb,
articleno = "48",
keywords = "Online; quality measure; relative worst order ratio;
seat reservation",
}
@Article{Nieberg:2008:ASW,
author = "Tim Nieberg and Johann Hurink and Walter Kern",
title = "Approximation schemes for wireless networks",
journal = j-TALG,
volume = "4",
number = "4",
pages = "49:1--49:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383380",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Wireless networks are created by the communication
links between a collection of radio transceivers. The
nature of wireless transmissions does not lead to
arbitrary undirected graphs but to structured graphs
which we characterize by the polynomially bounded
growth property. In contrast to many existing graph
models for wireless networks, the property of
polynomially bounded growth is defined independently of
geometric data such as positional information.\par
On such wireless networks, we present an approach that
can be used to create polynomial-time approximation
schemes for several optimization problems called the
local neighborhood-based scheme. We apply this approach
to the problems of seeking maximum (weight) independent
sets and minimum dominating sets. These are two
important problems in the area of wireless
communication networks and are also used in many
applications ranging from clustering to routing
strategies. However, the approach is presented in a
general fashion since it can be applied to other
problems as well.\par
The approach for the approximation schemes is robust in
the sense that it accepts any undirected graph as input
and either outputs a solution of desired quality or
correctly asserts that the graph presented as input
does not satisfy the structural assumption of a
wireless network (an NP-hard problem).",
acknowledgement = ack-nhfb,
articleno = "49",
keywords = "bounded growth; maximum independent set; minimum
dominating set; PTAS; Wireless ad-hoc networks",
}
@Article{Massberg:2008:AAF,
author = "Jens Ma{\ss}berg and Jens Vygen",
title = "Approximation algorithms for a facility location
problem with service capacities",
journal = j-TALG,
volume = "4",
number = "4",
pages = "50:1--50:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383381",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We present the first constant-factor approximation
algorithms for the following problem. Given a metric
space $(V, c)$, a finite set $d \subseteq V$ of
terminals/customers with demands $d: d \rightarrow
R_+$, a facility opening cost $f \in R_+$ and a
capacity $u \in R_+$, find a partition $d = D_1
{\SGMLcupdot} \ldots{} {\SGMLcupdot} D_k$ and Steiner
trees $T_i$ for $D_i(i = 1, \ldots{}, k)$ with $c(E
(T_i)) + d (D_i) \leq u$ for $i = 1, \ldots{}, k$ such
that $\sum_i = 1^{k} c (E(T_i)) + kf$ is minimum. This
problem arises in VLSI design. It generalizes the
bin-packing problem and the Steiner tree problem. In
contrast to other network design and facility location
problems, it has the additional feature of upper bounds
on the service cost that each facility can handle.
Among other results, we obtain a 4.1-approximation in
polynomial time, a 4.5-approximation in cubic time, and
a 5-approximation as fast as computing a minimum
spanning tree on $(D, c)$.",
acknowledgement = ack-nhfb,
articleno = "50",
keywords = "Approximation algorithm; facility location; network
design; VLSI design",
}
@Article{Swamy:2008:FTF,
author = "Chaitanya Swamy and David B. Shmoys",
title = "Fault-tolerant facility location",
journal = j-TALG,
volume = "4",
number = "4",
pages = "51:1--51:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383382",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider a fault-tolerant generalization of the
classical uncapacitated facility location problem,
where each client $j$ has a requirement that $r_j$ {\em
distinct\/} facilities serve it, instead of just one.
We give a 2.076-approximation algorithm for this
problem using LP rounding, which is currently the
best-known performance guarantee. Our algorithm
exploits primal and dual complementary slackness
conditions and is based on {\em clustered randomized
rounding}. A technical difficulty that we overcome is
the presence of terms with negative coefficients in the
dual objective function, which makes it difficult to
bound the cost in terms of dual variables. For the case
where all requirements are the same, we give a
primal-dual 1.52-approximation algorithm.\par
We also consider a fault-tolerant version of the
$k$-median problem. In the metric $k$-median problem,
we are given $n$ points in a metric space. We must
select $k$ of these to be centers, and then assign each
input point $j$ to the selected center that is closest
to it. In the fault-tolerant version we want $j$ to be
assigned to $r_j$ distinct centers. The goal is to
select the $k$ centers so as to minimize the sum of
assignment costs. The primal-dual algorithm for
fault-tolerant facility location with uniform
requirements also yields a 4-approximation algorithm
for the fault-tolerant $k$-median problem for this
case. This the first constant-factor approximation
algorithm for the uniform requirements case.",
acknowledgement = ack-nhfb,
articleno = "51",
keywords = "Approximation algorithms; facility location; k-median
problem",
}
@Article{Fotakis:2008:ACG,
author = "Dimitris Fotakis and Spyros Kontogiannis and Paul
Spirakis",
title = "Atomic congestion games among coalitions",
journal = j-TALG,
volume = "4",
number = "4",
pages = "52:1--52:??",
month = aug,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1383369.1383383",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:03:43 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider algorithmic questions concerning the
existence, tractability, and quality of Nash
equilibria, in atomic congestion games among users
participating in selfish coalitions.\par
We introduce a coalitional congestion model among
atomic players and demonstrate many interesting
similarities with the noncooperative case. For example,
there exists a potential function proving the existence
of pure Nash equilibria (PNE) in the unrelated parallel
links setting; in the network setting, the finite
improvement property collapses as soon as we depart
from linear delays, but there is an exact potential
(and thus PNE) for linear delays. The price of anarchy
on identical parallel links demonstrates a quite
surprising threshold behavior: It persists on being
asymptotically equal to that in the case of the
noncooperative KP-model, unless the number of
coalitions is {\em sublogarithmic}.\par
We also show crucial differences, mainly concerning the
hardness of algorithmic problems that are solved
efficiently in the noncooperative case. Although we
demonstrate convergence to robust PNE, we also prove
the hardness of computing them. On the other hand, we
propose a generalized fully mixed Nash equilibrium that
can be efficiently constructed in most cases. Finally,
we propose a natural improvement policy and prove its
convergence in pseudopolynomial time to PNE which are
robust against (even dynamically forming) coalitions of
small size.",
acknowledgement = ack-nhfb,
articleno = "52",
keywords = "Algorithmic game theory; congestion games; convergence
to equilibria; price of anarchy",
}
@Article{Torng:2008:SOU,
author = "Eric Torng and Jason McCullough",
title = "{SRPT} optimally utilizes faster machines to minimize
flow time",
journal = j-TALG,
volume = "5",
number = "1",
pages = "1:1--1:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435376",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We analyze the shortest remaining processing time
(SRPT) algorithm with respect to the problem of
scheduling $n$ jobs with release times on $m$ identical
machines to minimize total flow time. It is known that
SRPT is optimal if $m$ = 1 but that SRPT has a
worst-case approximation ratio of $\Theta(\min(=log
n/m, \log \Delta))$ for this problem, where $\Delta$ is
the ratio of the length of the longest job divided by
the length of the shortest job. It has previously been
shown that SRPT is able to use faster machines to
produce a schedule {\em as good as\/} an optimal
algorithm using slower machines. We now show that SRPT
{\em optimally\/} uses these faster machines with
respect to the worst-case approximation ratio. That is,
if SRPT is given machines that are $s \geq 2 - 1 / m$
times as fast as those used by an optimal algorithm,
SRPT's flow time is at least $s$ {\em times smaller\/}
than the flow time incurred by the optimal algorithm.
Clearly, no algorithm can offer a better worst-case
guarantee, and we show that existing algorithms with
similar performance guarantees to SRPT without resource
augmentation do not optimally use extra resources.",
acknowledgement = ack-nhfb,
articleno = "1",
keywords = "flow time; parallel machines; resource augmentation;
scheduling; SRPT",
}
@Article{Goldwasser:2008:ONS,
author = "Michael H. Goldwasser and Mark Pedigo",
title = "Online nonpreemptive scheduling of equal-length jobs
on two identical machines",
journal = j-TALG,
volume = "5",
number = "1",
pages = "2:1--2:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435377",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider the nonpreemptive scheduling of two
identical machines for jobs with equal processing times
yet arbitrary release dates and deadlines. Our
objective is to maximize the number of jobs completed
by their deadlines. Using standard nomenclature, this
problem is denoted as $P 2 | p_j = p, 4_j |
\sum{\SGMLUhorbar}_j$. The problem is known to be
polynomially solvable in an offline setting.\par
In an online variant of the problem, a job's existence
and parameters are revealed to the scheduler only upon
that job's release date. We present an online
deterministic algorithm for the problem and prove that
it is $3/2$-competitive. A simple lower bound shows
that this is the optimal deterministic
competitiveness.",
acknowledgement = ack-nhfb,
articleno = "2",
keywords = "Admission control; competitive analysis; scheduling",
}
@Article{Aiello:2008:CBM,
author = "William Aiello and Alex Kesselman and Yishay Mansour",
title = "Competitive buffer management for shared-memory
switches",
journal = j-TALG,
volume = "5",
number = "1",
pages = "3:1--3:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435378",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider buffer management policies for shared
memory switches. We study the case of overloads
resulting in packet loss, where the constraint is the
limited shared memory capacity. The goal of the buffer
management policy is that of maximizing the number of
packets transmitted. The problem is online in nature,
and thus we use competitive analysis to measure the
performance of the buffer management policies. Our main
result is to show that the well-known preemptive
Longest Queue Drop ({\em LQD\/}) policy is at most
2-competitive and at least $\sqrt 2$-competitive. We
also demonstrate a general lower bound of $4/3$ on the
performance of any deterministic online policy.
Finally, we consider some other popular non-preemptive
policies including Complete Partition, Complete
Sharing, Static Threshold and Dynamic Threshold and
derive almost tight bounds on their performance.",
acknowledgement = ack-nhfb,
articleno = "3",
keywords = "Buffer management; competitive analysis; shared
memory",
}
@Article{Agarwal:2008:KDD,
author = "Pankaj K. Agarwal and Haim Kaplan and Micha Sharir",
title = "Kinetic and dynamic data structures for closest pair
and all nearest neighbors",
journal = j-TALG,
volume = "5",
number = "1",
pages = "4:1--4:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435379",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We present simple, fully dynamic and kinetic data
structures, which are variants of a dynamic
two-dimensional range tree, for maintaining the closest
pair and all nearest neighbors for a set of $n$ moving
points in the plane; insertions and deletions of points
are also allowed. If no insertions or deletions take
place, the structure for the closest pair uses $O(n
\log n)$ space, and processes $O(n^2 \beta_ + 2(n) \log
n)$ critical events, each in $O(\log^2 n)$ time. Here
$s$ is the maximum number of times where the distances
between any two specific pairs of points can become
equal, $\beta_s(q) = \lambda_s(q)/q$, and
$\lambda_s(q)$ is the maximum length of
Davenport-Schinzel sequences of order $s$ on $q$
symbols. The dynamic version of the problem incurs a
slight degradation in performance: If $m$ \geq $n$
insertions and deletions are performed, the structure
still uses $O(n \log n)$ space, and processes $O(m n
\beta_s +2(n) \log^3 n)$ events, each in $O(\log^3 n)$
time.\par
Our kinetic data structure for all nearest neighbors
uses $O(n \log^2 n)$ space, and processes $O(n^2
\beta^{2_s +2}(n) \log^3 n)$ critical events. The
expected time to process all events is $O(n^2 \beta_{s
+2}^2(n) \log^4 n)$, though processing a single event
may take $\Theta(n)$ expected time in the worst case.
If $m \geq n$ insertions and deletions are performed,
then the expected number of events is $O(m n \beta^2_{s
+2}(n) \log^3 n)$ and processing them all takes $O(m n
\beta^2_{s + 2} (n) \log^4 n)$. An insertion or
deletion takes $O(n)$ expected time.",
acknowledgement = ack-nhfb,
articleno = "4",
keywords = "closest pair; computational geometry; Kinetic data
structures; nearest neighbors",
}
@Article{Agarwal:2008:ACT,
author = "Pankaj K. Agarwal and Micha Sharir and Emo Welzl",
title = "Algorithms for center and {Tverberg} points",
journal = j-TALG,
volume = "5",
number = "1",
pages = "5:1--5:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435380",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Given a set $s$ of $n$ points in $R^3$, a point $x$ in
$R^3$ is called {\em center point of $S$\/} if every
closed halfspace whose bounding hyperplane passes
through $x$ contains at least $\lceil n / 4 \rceil$
points from $S$. We present a near-quadratic algorithm
for computing the {\em center region}, that is the set
of all center points, of a set of $n$ points in $R^3$.
This is nearly tight in the worst case since the center
region can have $\Omega(n^2)$ complexity.\par
We then consider sets $s$ of $3 n$ points in the plane
which are the union of three disjoint sets consisting
respectively of $n$ red, $n$ blue, and $n$ green
points. A point $x$ in $R^2$ is called a {\em colored
Tverberg point of $S$\/} if there is a partition of $s$
into $n$ triples with one point of each color, so that
$x$ lies in all triangles spanned by these triples. We
present a first polynomial-time algorithm for
recognizing whether a given point is a colored Tverberg
point of such a 3-colored set $S$.",
acknowledgement = ack-nhfb,
articleno = "5",
keywords = "Arrangements; center point; Tverberg point",
}
@Article{Grandoni:2008:DWV,
author = "Fabrizio Grandoni and Jochen K{\"o}nemann and
Alessandro Panconesi",
title = "Distributed weighted vertex cover via maximal
matchings",
journal = j-TALG,
volume = "5",
number = "1",
pages = "6:1--6:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435381",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "In this article, we consider the problem of computing
a minimum-weight vertex-cover in an $n$-node, weighted,
undirected graph $G = (V, E)$. We present a fully
distributed algorithm for computing vertex covers of
weight at most twice the optimum, in the case of
integer weights. Our algorithm runs in an expected
number of $O(\log n + \log \SGMLWcirc)$ communication
rounds, where $\SGMLWcirc$ is the average
vertex-weight. The previous best algorithm for this
problem requires $O(\log n (\log n + \log \SGMLWcirc))$
rounds and it is not fully distributed.\par
For a maximal matching $m$ in $G$, it is a well-known
fact that any vertex-cover in $G$ needs to have at
least $|m|$ vertices. Our algorithm is based on a
generalization of this combinatorial lower-bound to the
weighted setting.",
acknowledgement = ack-nhfb,
articleno = "6",
keywords = "Approximation algorithms; distributed algorithms;
maximal matching; vertex cover",
}
@Article{Vishwanathan:2008:HIA,
author = "Sundar Vishwanathan",
title = "On hard instances of approximate vertex cover",
journal = j-TALG,
volume = "5",
number = "1",
pages = "7:1--7:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435382",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We show that if there is a $2 - \epsilon$
approximation algorithm for vertex cover on graphs with
vector chromatic number at most $2 + \delta$, then
there is a $2 - f(\epsilon, \delta)$ approximation
algorithm for vertex cover for all graphs.",
acknowledgement = ack-nhfb,
articleno = "7",
keywords = "Approximation algorithms; vertex cover",
}
@Article{Berend:2008:CDG,
author = "Daniel Berend and Steven S. Skiena and Yochai Twitto",
title = "Combinatorial dominance guarantees for problems with
infeasible solutions",
journal = j-TALG,
volume = "5",
number = "1",
pages = "8:1--8:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435383",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "The design and analysis of approximation algorithms
for {\em NP\/}-hard problems is perhaps the most active
research area in the theory of combinatorial
algorithms. In this article, we study the notion of a
{\em combinatorial dominance guarantee\/} as a way for
assessing the performance of a given approximation
algorithm. An $f(n)$ dominance bound is a guarantee
that the heuristic always returns a solution not worse
than at least $f(n)$ solutions. We give tight analysis
of many heuristics, and establish novel and interesting
dominance guarantees even for certain inapproximable
problems and heuristic search algorithms. For example,
we show that the maximal matching heuristic of VERTEX
COVER offers a combinatorial dominance guarantee of
$2^n - (1.839 + o(1))^n$. We also give
inapproximability results for most of the problems we
discuss.",
acknowledgement = ack-nhfb,
articleno = "8",
keywords = "algorithms analysis; approximation algorithms;
Computation complexity; dominance analysis",
}
@Article{Fomin:2008:CBM,
author = "Fedor V. Fomin and Fabrizio Grandoni and Artem V.
Pyatkin and Alexey A. Stepanov",
title = "Combinatorial bounds via measure and conquer:
{Bounding} minimal dominating sets and applications",
journal = j-TALG,
volume = "5",
number = "1",
pages = "9:1--9:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435384",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We provide an algorithm listing all minimal dominating
sets of a graph on $n$ vertices in time $O(1.7159^n)$.
This result can be seen as an algorithmic proof of the
fact that the number of minimal dominating sets in a
graph on $n$ vertices is at most $1.7159^n$, thus
improving on the trivial $O(2^n / \sqrt n)$ bound. Our
result makes use of the measure-and-conquer technique
which was recently developed in the area of exact
algorithms.\par
Based on this result, we derive an $O(2.8718^n)$
algorithm for the domatic number problem.",
acknowledgement = ack-nhfb,
articleno = "9",
keywords = "domatic number; Exact exponential algorithms; listing
algorithms; measure and conquer; minimum dominating
set; minimum set cover",
}
@Article{Oum:2008:ARW,
author = "Sang-Il Oum",
title = "Approximating rank-width and clique-width quickly",
journal = j-TALG,
volume = "5",
number = "1",
pages = "10:1--10:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435385",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Rank-width was defined by Oum and Seymour [2006] to
investigate clique-width. They constructed an algorithm
that either outputs a rank-decomposition of width at
most $f(k)$ for some function f or confirms that
rank-width is larger than $k$ in time $O(|V|^9 \log
|V|)$ for an input graph $G = (V, E)$ and a fixed $k$.
We develop three separate algorithms of this kind with
faster running time. We construct an $O(|V|^4)$-time
algorithm with $f(k) = 3 k + 1$ by constructing a
subroutine for the previous algorithm; we avoid generic
algorithms minimizing submodular functions used by Oum
and Seymour. Another one is an $O(|V|^3)$-time
algorithm with $f(k) = 24 k$, achieved by giving a
reduction from graphs to binary matroids; then we use
an approximation algorithm for matroid branch-width by
Hlin{\^e}n{\'y} [2005]. Finally we construct an
$O(|V|^3)$-time algorithm with $f(k) = 3 k - 1$ by
combining the ideas of the two previously cited
papers.",
acknowledgement = ack-nhfb,
articleno = "10",
keywords = "Approximation algorithms; branch-width; clique-width;
matroids; rank-width",
}
@Article{Brandstadt:2008:SLT,
author = "Andreas Brandst{\"a}dt and Van Bang Le and R.
Sritharan",
title = "Structure and linear-time recognition of 4-leaf
powers",
journal = j-TALG,
volume = "5",
number = "1",
pages = "11:1--11:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435386",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "A graph $G$ is the $k$-{\em leaf power\/} of a tree
$T$ if its vertices are leaves of $T$ such that two
vertices are adjacent in $G$ if and only if their
distance in $T$ is at most $k$. Then $T$ is a $k$-{\em
leaf root\/} of $G$. This notion was introduced and
studied by Nishimura, Ragde, and Thilikos [2002],
motivated by the search for underlying phylogenetic
trees. Their results imply an $O(n^3)$-time recognition
algorithm for 4-leaf powers. Recently, Rautenbach
[2006] as well as Dom et al. [2005] characterized
4-leaf powers without true twins in terms of forbidden
subgraphs. We give new characterizations for 4-leaf
powers and squares of trees by a complete structural
analysis. As a consequence, we obtain a conceptually
simple linear-time recognition of 4-leaf powers.",
acknowledgement = ack-nhfb,
articleno = "11",
keywords = "Graph powers; leaf powers; phylogenetic trees; squares
of trees; trees",
}
@Article{Chen:2008:MCI,
author = "Xin Chen and Lan Liu and Zheng Liu and Tao Jiang",
title = "On the minimum common integer partition problem",
journal = j-TALG,
volume = "5",
number = "1",
pages = "12:1--12:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435387",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We introduce a new combinatorial optimization problem
in this article, called the {\em minimum common integer
partition\/} (MCIP) problem, which was inspired by
computational biology applications including ortholog
assignment and DNA fingerprint assembly. A {\em
partition\/} of a positive integer $n$ is a multiset of
positive integers that add up to exactly $n$, and an
{\em integer partition\/} of a multiset $s$ of integers
is defined as the multiset union of partitions of
integers in $S$. Given a sequence of multisets $s_1,
s_2, \ldots, S_k$ of integers, where $k \geq 2$, we say
that a multiset is a {\em common integer partition\/}
if it is an integer partition of every multiset $S_i, 1
\leq i \leq k$. The MCIP problem is thus defined as to
find a common integer partition of $s_1, s_2, \ldots,
S_k$ with the minimum cardinality, denoted as
MCIP($s_1$, $S_2$, \ldots{}, $S_k$). It is easy to see
that the MCIP problem is NP-hard, since it generalizes
the well-known subset sum problem. We can in fact show
that it is APX-hard. We will also present a
$5/4$-approximation algorithm for the MCIP problem when
$k = 2$, and a $3 k (k - 1) / 3 k - 2$-approximation
algorithm for $k \geq 3$.",
acknowledgement = ack-nhfb,
articleno = "12",
keywords = "approximation algorithm; combinatorial optimization;
computational biology; integer partition; NP-hard;
Subset sum",
}
@Article{Azriel:2008:IFS,
author = "Dany Azriel and Noam Solomon and Shay Solomon",
title = "On an infinite family of solvable {Hanoi} graphs",
journal = j-TALG,
volume = "5",
number = "1",
pages = "13:1--13:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435388",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "The Tower of Hanoi problem is generalized by placing
pegs on the vertices of a given directed graph $G$ with
two distinguished vertices, $s$ and $D$, and allowing
moves only along arcs of this graph. An optimal
solution for such a graph $G$ is an algorithm that
completes the task of moving a tower of any given
number of disks from $s$ to $d$ in a minimal number of
disk moves.\par
In this article we present an algorithm which solves
the problem for two infinite families of graphs, and
prove its optimality. To the best of our knowledge,
this is the first optimality proof for an {\em
infinite\/} family of graphs.\par
Furthermore, we present a unified algorithm that solves
the problem for a wider family of graphs and conjecture
its optimality.",
acknowledgement = ack-nhfb,
articleno = "13",
keywords = "Optimality proofs; Tower of Hanoi",
}
@Article{Elmasry:2008:MPQ,
author = "Amr Elmasry and Claus Jensen and Jyrki Katajainen",
title = "Multipartite priority queues",
journal = j-TALG,
volume = "5",
number = "1",
pages = "14:1--14:??",
month = nov,
year = "2008",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1435375.1435389",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:04:20 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We introduce a framework for reducing the number of
element comparisons performed in priority-queue
operations. In particular, we give a priority queue
which guarantees the worst-case cost of $O(1)$ per
minimum finding and insertion, and the worst-case cost
of $O(\log n)$ with at most $\log n + O(1)$ element
comparisons per deletion, improving the bound of $2
\log n + O(1)$ known for binomial queues. Here, $n$
denotes the number of elements stored in the data
structure prior to the operation in question, and $\log
n$ equals $\log_2(\max\{2, n\})$. As an immediate
application of the priority queue developed, we obtain
a sorting algorithm that is optimally adaptive with
respect to the inversion measure of disorder, and that
sorts a sequence having $n$ elements and $I$ inversions
with at most $n \log (I / n) + O(n)$ element
comparisons.",
acknowledgement = ack-nhfb,
articleno = "14",
keywords = "constant factors; heaps; meticulous analysis; Priority
queues",
}
@Article{Eppstein:2009:TBG,
author = "David Eppstein",
title = "Testing bipartiteness of geometric intersection
graphs",
journal = j-TALG,
volume = "5",
number = "2",
pages = "15:1--15:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497291",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We show how to test the bipartiteness of an
intersection graph of $n$ line segments or simple
polygons in the plane, or of an intersection graph of
balls in $d$-dimensional Euclidean space, in time $O(n
\log n)$. More generally, we find subquadratic
algorithms for connectivity and bipartiteness testing
of intersection graphs of a broad class of geometric
objects. Our algorithms for these problems return
either a bipartition of the input or an odd cycle in
its intersection graph. We also consider lower bounds
for connectivity and $k$-colorability problems of
geometric intersection graphs. For unit balls in $d$
dimensions, connectivity testing has equivalent
randomized complexity to construction of Euclidean
minimum spanning trees, and for line segments in the
plane connectivity testing has the same lower bounds as
Hopcroft's point-line incidence testing problem;
therefore, for these problems, connectivity is unlikely
to be solved as efficiently as bipartiteness. For line
segments or planar disks, testing $k$-colorability of
intersection graphs for $k$ > 2 is NP-complete.",
acknowledgement = ack-nhfb,
articleno = "15",
keywords = "Bipartite graph; coin graph; disks; geometric
thickness; graph coloring; Hopcroft's problem;
intersection graph; line segments; minimum spanning
tree",
}
@Article{Chen:2009:OCF,
author = "Ke Chen and Haim Kaplan and Micha Sharir",
title = "Online conflict-free coloring for halfplanes,
congruent disks, and axis-parallel rectangles",
journal = j-TALG,
volume = "5",
number = "2",
pages = "16:1--16:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497292",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We present randomized algorithms for online
conflict-free coloring (CF in short) of points in the
plane, with respect to halfplanes, congruent disks, and
nearly-equal axis-parallel rectangles. In all three
cases, the coloring algorithms use $O(\log n) colors,
with high probability.\par
We also present a deterministic algorithm for online CF
coloring of points in the plane with respect to
nearly-equal axis-parallel rectangles, using $O(\log^3
n)$ colors. This is the first efficient (i.e, using
$\polylog(n)$ colors) deterministic online CF coloring
algorithm for this problem.",
acknowledgement = ack-nhfb,
articleno = "16",
keywords = "coloring; Conflict free coloring; online algorithms",
}
@Article{Alonso:2009:ACA,
author = "Laurent Alonso and Edward M. Reingold",
title = "Average-case analysis of some plurality algorithms",
journal = j-TALG,
volume = "5",
number = "2",
pages = "17:1--17:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497293",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Given a set of $n$ elements, each of which is colored
one of $c$ colors, we must determine an element of the
plurality (most frequently occurring) color by pairwise
equal/unequal color comparisons of elements. We focus
on the expected number of color comparisons when the
$c^n$ colorings are equally probable. We analyze an
obvious algorithm, showing that its expected
performance is $c^2 + c - 2/2 c n - O(c^2)$, with
variance $\Theta(c^2 n)$. We present and analyze an
algorithm for the case $c = 3$ colors whose average
complexity on the $3^n$ equally probable inputs is
$7083/5425 n + O(\sqrt n) = 1.3056\ldots{} n + O(\sqrt
n)$, substantially better than the expected complexity
$5/3 n + O(1) = 1.6666\ldots{} n + O(1)$ of the obvious
algorithm. We describe a similar algorithm for $c = 4$
colors whose average complexity on the $4^n$ equally
probable inputs is $761311/402850 n + O(\log n) =
1.8898\ldots{} n + O(\log n)$, substantially better
than the expected complexity $9/4 n + O(1) = 2.25 n +
O(1)$ of the obvious algorithm.",
acknowledgement = ack-nhfb,
articleno = "17",
keywords = "Algorithm analysis; majority problem; plurality
problem",
}
@Article{Bar-Noy:2009:TMR,
author = "Amotz Bar-Noy and Sudipto Guha and Yoav Katz and
Joseph (Seffi) Naor and Baruch Schieber and Hadas
Shachnai",
title = "Throughput maximization of real-time scheduling with
batching",
journal = j-TALG,
volume = "5",
number = "2",
pages = "18:1--18:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497294",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider the following scheduling with batching
problem that has many applications, for example, in
multimedia-on-demand and manufacturing of integrated
circuits. The input to the problem consists of n jobs
and $k$ parallel machines. Each job is associated with
a set of time intervals in which it can be scheduled
(given either explicitly or nonexplicitly), a weight,
and a family. Each family is associated with a
processing time. Jobs that belong to the same family
can be batched and executed together on the same
machine. The processing time of each batch is the
processing time of the family of jobs it contains. The
goal is to find a nonpreemptive schedule with batching
that maximizes the weight of the scheduled jobs. We
give constant factor (4 or 4 + \epsilon) approximation
algorithms for two variants of the problem, depending
on the precise representation of the input. When the
batch size is unbounded and each job is associated with
a time window in which it can be processed, these
approximation ratios reduce to 2 and 2 + \epsilon ,
respectively. We also give approximation algorithms for
two special cases when all release times are the
same.",
acknowledgement = ack-nhfb,
articleno = "18",
keywords = "batching; local ratio technique; Scheduling",
}
@Article{Rabani:2009:BAT,
author = "Yuval Rabani and Gabriel Scalosub",
title = "Bicriteria approximation tradeoff for the node-cost
budget problem",
journal = j-TALG,
volume = "5",
number = "2",
pages = "19:1--19:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497295",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider an optimization problem consisting of an
undirected graph, with cost and profit functions
defined on all vertices. The goal is to find a
connected subset of vertices with maximum total profit,
whose total cost does not exceed a given budget. The
best result known prior to this work guaranteed a $(2,
O(\log n))$ bicriteria approximation, that is, the
solution's profit is at least a fraction of $1 / O(\log
n)$ of an optimum solution respecting the budget, while
its cost is at most twice the given budget. We improve
these results and present a bicriteria tradeoff that,
given any $\epsilon \in (0,1]$, guarantees a $(1 +
\epsilon, O(1/\epsilon \log n))$-approximation.",
acknowledgement = ack-nhfb,
articleno = "19",
keywords = "Approximation algorithms; bicriteria approximation",
}
@Article{Li:2009:PTA,
author = "Guojun Li and Xiaotie Deng and Ying Xu",
title = "A polynomial-time approximation scheme for embedding
hypergraph in a cycle",
journal = j-TALG,
volume = "5",
number = "2",
pages = "20:1--20:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497296",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We consider the problem of embedding hyperedges of a
hypergraph as paths in a cycle such that the maximum
congestion, namely the maximum number of paths that use
any single edge in a cycle, is minimized.\par
The {\em minimum congestion hypergraph embedding in a
cycle\/} problem is known to be NP-hard and its graph
version, the {\em minimum congestion graph embedding in
a cycle}, is solvable in polynomial-time. Furthermore,
for the graph problem, a polynomial-time approximation
scheme for the weighted version is known. For the
hypergraph model, several approximation algorithms with
a ratio of two have been previously published. A recent
paper reduced the approximation ratio to 1.5. We
present a polynomial-time approximation scheme in this
article, settling the debate regarding whether the
problem is polynomial-time approximable.",
acknowledgement = ack-nhfb,
articleno = "20",
keywords = "Hypergraph embedding; minimum congestion; NP-hard;
polynomial-time approximation scheme",
}
@Article{Even:2009:AAA,
author = "Guy Even and Jon Feldman and Guy Kortsarz and Zeev
Nutov",
title = "A 1.8 approximation algorithm for augmenting
edge-connectivity of a graph from 1 to 2",
journal = j-TALG,
volume = "5",
number = "2",
pages = "21:1--21:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497297",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We present a 1.8-approximation algorithm for the
following NP-hard problem: Given a connected graph $G =
(V, E)$ and an edge set $E$ on $V$ disjoint to $E$,
find a minimum-size subset of edges $F \subseteq E$
such that $(V, E \cup f)$ is 2-edge-connected. Our
result improves and significantly simplifies the
approximation algorithm with ratio $1.875 + \epsilon$
of Nagamochi.",
acknowledgement = ack-nhfb,
articleno = "21",
keywords = "Approximation algorithms; connectivity; graphs",
}
@Article{Marko:2009:ADP,
author = "Sharon Marko and Dana Ron",
title = "Approximating the distance to properties in
bounded-degree and general sparse graphs",
journal = j-TALG,
volume = "5",
number = "2",
pages = "22:1--22:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497298",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "We address the problem of approximating the distance
of bounded-degree and general sparse graphs from having
some predetermined graph property $p$. That is, we are
interested in sublinear algorithms for estimating the
fraction of edge modifications (additions or deletions)
that must be performed on a graph so that it obtains
$p$. This fraction is taken with respect to a given
upper bound $m$ on the number of edges. In particular,
for graphs with degree bound $d$ over $n$ vertices, $m
= dn$. To perform such an approximation the algorithm
may ask for the degree of any vertex of its choice, and
may ask for the neighbors of any vertex.\par
The problem of estimating the distance to having a
property was first explicitly addressed by Parnas et
al. [2006]. In the context of graphs this problem was
studied by Fischer and Newman [2007] in the dense
graphs model. In this model the fraction of edge
modifications is taken with respect to $n^2$, and the
algorithm may ask for the existence of an edge between
any pair of vertices of its choice. Fischer and Newman
showed that every graph property that has a testing
algorithm in this model, with query complexity
independent of the size of the graph, also has a
distance approximation algorithm with query complexity
that is independent of the size of graph.\par
In this work we focus on bounded-degree and general
sparse graphs, and give algorithms for all properties
shown to have efficient testing algorithms by Goldreich
and Ron [2002]. Specifically, these properties are
$k$-edge connectivity, subgraph freeness (for
constant-size subgraphs), being an Eulerian graph, and
cycle freeness. A variant of our subgraph-freeness
algorithm approximates the size of a minimum vertex
cover of a graph in sublinear time. This approximation
improves on a recent result of Parnas and Ron [2007].",
acknowledgement = ack-nhfb,
articleno = "22",
keywords = "distance approximation; graph properties; property
testing; Sublinear approximation algorithms",
}
@Article{Berry:2009:LTA,
author = "Vincent Berry and Christophe Paul and Sylvain
Guillemot and Fran{\c{c}}ois Nicolas",
title = "Linear time 3-approximation for the {MAST} problem",
journal = j-TALG,
volume = "5",
number = "2",
pages = "23:1--23:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497299",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Given a set of leaf-labeled trees with identical leaf
sets, the well-known Maximum Agreement SubTree (MAST)
problem consists in finding a subtree homeomorphically
included in all input trees and with the largest number
of leaves. MAST and its variant called Maximum
Compatible Tree (MCT) are of particular interest in
computational biology. This article presents a
linear-time approximation algorithm to solve the
complement version of MAST, namely identifying the
smallest set of leaves to remove from input trees to
obtain isomorphic trees. We also present an $O(n^2 +
kn)$ algorithm to solve the complement version of MCT.
For both problems, we thus achieve significantly lower
running times than previously known algorithms. Fast
running times are especially important in phylogenetics
where large collections of trees are routinely produced
by resampling procedures, such as the nonparametric
bootstrap or Bayesian MCMC methods.",
acknowledgement = ack-nhfb,
articleno = "23",
keywords = "Approximation algorithm; maximum agreement subtree;
maximum compatible subtree; phylogenetic tree",
}
@Article{Condon:2009:ADA,
author = "Anne Condon and Amol Deshpande and Lisa Hellerstein
and Ning Wu",
title = "Algorithms for distributional and adversarial
pipelined filter ordering problems",
journal = j-TALG,
volume = "5",
number = "2",
pages = "24:1--24:??",
month = mar,
year = "2009",
CODEN = "????",
DOI = "http://doi.acm.org/10.1145/1497290.1497300",
ISSN = "1549-6325",
bibdate = "Tue Jul 14 19:05:00 MDT 2009",
bibsource = "http://portal.acm.org/",
abstract = "Pipelined filter ordering is a central problem in
database query optimization. The problem is to
determine the optimal order in which to apply a given
set of commutative filters (predicates) to a set of
elements (the tuples of a relation), so as to find, as
efficiently as possible, the tuples that satisfy all of
the filters. Optimization of pipelined filter ordering
has recently received renewed attention in the context
of environments such as the Web, continuous high-speed
data streams, and sensor networks. Pipelined filter
ordering problems are also studied in areas such as
fault detection and machine learning under names such
as learning with attribute costs, minimum-sum set
cover, and satisficing search. We present algorithms
for two natural extensions of the classical pipelined
filter ordering problem: (1) a {\em
distributional-type\/} problem where the filters run in
parallel and the goal is to maximize throughput, and
(2) an {\em adversarial-type\/} problem where the goal
is to minimize the expected value of {\em
multiplicative regret}. We present two related
algorithms for solving (1), both running in time
$O(n^2)$, which improve on the $O(n 3 \log n)$
algorithm of Kodialam. We use techniques from our
algorithms for (1) to obtain an algorithm for 1.",
acknowledgement = ack-nhfb,
articleno = "24",
keywords = "flow algorithms; Pipelined filter ordering; query
optimization; selection ordering",
}