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