%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.06", %%% date = "15 July 2009", %%% time = "14:08:47 MDT", %%% filename = "talg.bib", %%% address = "University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "06921 6292 33843 293434", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "ACM Transactions on Algorithms; bibliography; %%% TALG", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This is a COMPLETE BibTeX bibliography for %%% ACM Transactions on Algorithms (CODEN ????, %%% ISSN 1549-6325), covering all journal issues %%% from 2005 -- date. %%% %%% At version 1.06, the COMPLETE journal %%% coverage looked like this: %%% %%% 2005 ( 20) 2007 ( 52) 2009 ( 10) %%% 2006 ( 37) 2008 ( 66) %%% %%% Article: 185 %%% %%% Total entries: 185 %%% %%% The journal Web page can be found at: %%% %%% http://www.acm.org/pubs/taco.html %%% %%% The journal table of contents page is at: %%% %%% http://www.acm.org/talg/ %%% http://portal.acm.org/browse_dl.cfm?linked=1&part=periodical&idx=J982 %%% %%% Qualified subscribers can retrieve the full %%% text of recent articles in PDF form. %%% %%% The initial draft was extracted from the ACM %%% Web pages. %%% %%% ACM copyrights explicitly permit abstracting %%% with credit, so article abstracts, keywords, %%% and subject classifications have been %%% included in this bibliography wherever %%% available. Article reviews have been %%% omitted, until their copyright status has %%% been clarified. %%% %%% bibsource keys in the bibliography entries %%% below indicate the entry originally came %%% from the computer science bibliography %%% archive, even though it has likely since %%% been corrected and updated. %%% %%% URL keys in the bibliography point to %%% World Wide Web locations of additional %%% information about the entry. %%% %%% BibTeX citation tags are uniformly chosen %%% as name:year:abbrev, where name is the %%% family name of the first author or editor, %%% year is a 4-digit number, and abbrev is a %%% 3-letter condensation of important title %%% words. Citation tags were automatically %%% generated by software developed for the %%% BibNet Project. %%% %%% In this bibliography, entries are sorted in %%% publication order, using ``bibsort -byvolume.'' %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{"\input bibnames.sty"} %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Journal abbreviations: @String{j-TALG = "ACM Transactions on Algorithms"} %%% ==================================================================== %%% Bibliography entries: @Article{Gabow:2005:EF, author = "Harold N. Gabow", title = "{Editor}'s foreword", journal = j-TALG, volume = "1", number = "1", pages = "1--1", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Yuster:2005:FSM, author = "Raphael Yuster and Uri Zwick", title = "Fast sparse matrix multiplication", journal = j-TALG, volume = "1", number = "1", pages = "2--13", month = jul, year = "2005", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1077464.1077466", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", abstract = "Let $A$ and $B$ be two $n \times n$ matrices over a ring $R$ (e.g., the reals or the integers) each containing at most $m$ nonzero elements. We present a new algorithm that multiplies $A$ and $B$ using $O(m^{0.7}n^{1.2} + n^2 + o(1))$ algebraic operations (i.e., multiplications, additions and subtractions) over $R$. The na{\"\i}ve matrix multiplication algorithm, on the other hand, may need to perform $\Omega(mn)$ operations to accomplish the same task. For $m \leq n^{1.14}$, the new algorithm performs an almost optimal number of only $n^2 + o(1)$ operations. For $m \leq n^{1.68}$, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses $O(n^{2.38})$ algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.", acknowledgement = ack-nhfb, } @Article{Edmonds:2005:MAL, author = "Jeff Edmonds and Kirk Pruhs", title = "A maiden analysis of longest wait first", journal = j-TALG, volume = "1", number = "1", pages = "14--32", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Demaine:2005:FPA, author = "Erik D. Demaine and Fedor V. Fomin and Mohammadtaghi Hajiaghayi and Dimitrios M. Thilikos", title = "Fixed-parameter algorithms for $(k, r)$-center in planar graphs and map graphs", journal = j-TALG, volume = "1", number = "1", pages = "33--47", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Adler:2005:PMM, author = "Micah Adler and Dan Rubenstein", title = "Pricing multicasting in more flexible network models", journal = j-TALG, volume = "1", number = "1", pages = "48--73", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Even:2005:NDP, author = "Guy Even and Guy Kortsarz and Wolfgang Slany", title = "On network design problems: fixed cost flows and the covering {Steiner} problem", journal = j-TALG, volume = "1", number = "1", pages = "74--101", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Alstrup:2005:BBC, author = "Stephen Alstrup and Thore Husfeldt and Theis Rauhe and Mikkel Thorup", title = "Black box for constant-time insertion in priority queues (note)", journal = j-TALG, volume = "1", number = "1", pages = "102--106", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Vinkemeier:2005:LTA, author = "Doratha E. Drake Vinkemeier and Stefan Hougardy", title = "A linear-time approximation algorithm for weighted matchings in graphs", journal = j-TALG, volume = "1", number = "1", pages = "107--122", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Grabner:2005:ALC, author = "Peter J. Grabner and Clemens Heuberger and Helmut Prodinger and J{\"o}rg M. Thuswaldner", title = "Analysis of linear combination algorithms in cryptography", journal = j-TALG, volume = "1", number = "1", pages = "123--142", month = jul, year = "2005", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1077464.1077473", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", abstract = "Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small ``weight.'' We study two algorithms, one based on nonadjacent forms of the coefficients of the linear combination, the other based on a certain joint sparse form specifically adapted to this problem. Both methods are sped up using the sliding windows approach combined with precomputed lookup tables. We give explicit and asymptotic results for the number of group operations needed, assuming uniform distribution of the coefficients. Expected values, variances and a central limit theorem are proved using generating functions. Furthermore, we provide a new algorithm that calculates the digits of an optimal expansion of pairs of integers from left to right. This avoids storing the whole expansion, which is needed with the previously known right-to-left methods, and allows an online computation.", acknowledgement = ack-nhfb, } @Article{Cechlarova:2005:GSR, author = "Katar{\'\i}na Cechl{\'a}rov{\'a} and Tam{\'a}s Fleiner", title = "On a generalization of the stable roommates problem", journal = j-TALG, volume = "1", number = "1", pages = "143--156", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Khuller:2005:PC, author = "Samir Khuller", title = "Problems column", journal = j-TALG, volume = "1", number = "1", pages = "157--159", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Johnson:2005:NCC, author = "David S. Johnson", title = "The {NP}-completeness column", journal = j-TALG, volume = "1", number = "1", pages = "160--176", month = jul, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:55 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Janson:2005:IDL, author = "Svante Janson", title = "Individual displacements for linear probing hashing with different insertion policies", journal = j-TALG, volume = "1", number = "2", pages = "177--213", month = oct, year = "2005", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1103963.1103964", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", abstract = "We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some $\alpha$, $0 < \alpha < 1$. (In the case of Last Come, the results are more complicated and less complete than in the other cases.) We also show, using the diagonal Poisson transform studied by Poblete, Viola and Munro, that exact expressions for finite $m$ and $n$ can be obtained from the limits as $m,n \rightarrow \infty$. We end with some results, conjectures and questions about the shape of the limit distributions. These have some relevance for computer applications.", acknowledgement = ack-nhfb, } @Article{Viola:2005:EDI, author = "Alfredo Viola", title = "Exact distribution of individual displacements in linear probing hashing", journal = j-TALG, volume = "1", number = "2", pages = "214--242", month = oct, year = "2005", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1103963.1103965", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", abstract = "This paper studies the distribution of individual displacements for the standard and the Robin Hood linear probing hashing algorithms. When a table of size $m$ has $n$ elements, the distribution of the search cost of a random element is studied for both algorithms. Specifically, exact distributions for fixed $m$ and $n$ are found as well as when the table is $\alpha$-full, and $\alpha$ strictly smaller than 1. Moreover, for full tables, limit laws for both algorithms are derived.", acknowledgement = ack-nhfb, } @Article{Alstrup:2005:MIF, author = "Stephen Alstrup and Jacob Holm and Mikkel Thorup and Kristian De Lichtenberg", title = "Maintaining information in fully dynamic trees with top trees", journal = j-TALG, volume = "1", number = "2", pages = "243--264", month = oct, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Jothi:2005:AAC, author = "Raja Jothi and Balaji Raghavachari", title = "Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design", journal = j-TALG, volume = "1", number = "2", pages = "265--282", month = oct, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Elkin:2005:CAS, author = "Michael Elkin", title = "Computing almost shortest paths", journal = j-TALG, volume = "1", number = "2", pages = "283--323", month = oct, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Carvalho:2005:VAE, author = "Marcelo H. De Carvalho and Joseph Cheriyan", title = "An {$O(VE)$} algorithm for ear decompositions of matching-covered graphs", journal = j-TALG, volume = "1", number = "2", pages = "324--337", month = oct, year = "2005", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1103963.1103969", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Goel:2005:AMF, author = "Ashish Goel and Adam Meyerson and Serge Plotkin", title = "Approximate majorization and fair online load balancing", journal = j-TALG, volume = "1", number = "2", pages = "338--349", month = oct, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Chrobak:2005:GAM, author = "Marek Chrobak and Petr Kolman and Ji{\v{r}}{\'\i} Sgall", title = "The greedy algorithm for the minimum common string partition problem", journal = j-TALG, volume = "1", number = "2", pages = "350--366", month = oct, year = "2005", CODEN = "????", ISSN = "1549-6325", bibdate = "Tue Dec 13 18:19:56 MST 2005", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Sawada:2006:GRF, author = "Joe Sawada", title = "Generating rooted and free plane trees", journal = j-TALG, volume = "2", number = "1", pages = "1--13", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Hegde:2006:FSE, author = "Rajneesh Hegde", title = "Finding $3$-shredders efficiently", journal = j-TALG, volume = "2", number = "1", pages = "14--43", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Gramm:2006:PMA, author = "Jens Gramm and Jiong Guo and Rolf Niedermeier", title = "Pattern matching for arc-annotated sequences", journal = j-TALG, volume = "2", number = "1", pages = "44--65", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Hassin:2006:MGV, author = "Refael Hassin and Asaf Levin", title = "The minimum generalized vertex cover problem", journal = j-TALG, volume = "2", number = "1", pages = "66--78", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Epstein:2006:OSS, author = "Leah Epstein and Rob Van Stee", title = "Online scheduling of splittable tasks", journal = j-TALG, volume = "2", number = "1", pages = "79--94", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Gonzalez:2006:MTC, author = "Teofilo F. Gonzalez and Joseph Y.-T. Leung and Michael Pinedo", title = "Minimizing total completion time on uniform machines with deadline constraints", journal = j-TALG, volume = "2", number = "1", pages = "95--115", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Gandhi:2006:IRD, author = "Rajiv Gandhi and Magn{\'u}s M. Halld{\'o}rsson and Guy Kortsarz and Hadas Shachnai", title = "Improved results for data migration and open shop scheduling", journal = j-TALG, volume = "2", number = "1", pages = "116--129", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Khuller:2006:PC, author = "Samir Khuller", title = "Problems column", journal = j-TALG, volume = "2", number = "1", pages = "130--134", month = jan, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Fri May 26 08:40:43 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Korsh:2006:LGC, author = "James Korsh and Paul Lafollette", title = "A loopless {Gray} code for rooted trees", journal = j-TALG, volume = "2", number = "2", pages = "135--152", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Alon:2006:ACS, author = "Noga Alon and Dana Moshkovitz and Shmuel Safra", title = "Algorithmic construction of sets for {$k$}-restrictions", journal = j-TALG, volume = "2", number = "2", pages = "153--177", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Lau:2006:BRG, author = "Lap Chi Lau", title = "Bipartite roots of graphs", journal = j-TALG, volume = "2", number = "2", pages = "178--208", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Agarwal:2006:EAB, author = "Pankaj K. Agarwal and Boris Aronov and Vladlen Koltun", title = "Efficient algorithms for bichromatic separability", journal = j-TALG, volume = "2", number = "2", pages = "209--227", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Epstein:2006:SU, author = "Leah Epstein and Rob Van Stee", title = "This side up!", journal = j-TALG, volume = "2", number = "2", pages = "228--243", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Huo:2006:MMF, author = "Yumei Huo and Joseph Y.-T. Leung", title = "Minimizing mean flow time for {UET} tasks", journal = j-TALG, volume = "2", number = "2", pages = "244--262", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Hassin:2006:RST, author = "Refael Hassin and Danny Segev", title = "Robust subgraphs for trees and paths", journal = j-TALG, volume = "2", number = "2", pages = "263--281", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Azar:2006:IAC, author = "Yossi Azar and Yossi Richter", title = "An improved algorithm for {CIOQ} switches", journal = j-TALG, volume = "2", number = "2", pages = "282--295", month = apr, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Wed Aug 23 05:38:18 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Berend:2006:CMP, author = "Daniel Berend and Amir Sapir", title = "The cyclic multi-peg {Tower of Hanoi}", journal = j-TALG, volume = "2", number = "3", pages = "297--317", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Drmota:2006:RFA, author = "Michael Drmota and Helmut Prodinger", title = "The register function for $t$-ary trees", journal = j-TALG, volume = "2", number = "3", pages = "318--334", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Kowalik:2006:OBL, author = "Lukasz Kowalik and Maciej Kurowski", title = "Oracles for bounded-length shortest paths in planar graphs", journal = j-TALG, volume = "2", number = "3", pages = "335--363", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Katriel:2006:OTO, author = "Irit Katriel and Hans L. Bodlaender", title = "Online topological ordering", journal = j-TALG, volume = "2", number = "3", pages = "364--379", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Duncan:2006:OCG, author = "Christian A. Duncan and Stephen G. Kobourov and V. S. Anil Kumar", title = "Optimal constrained graph exploration", journal = j-TALG, volume = "2", number = "3", pages = "380--402", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Raman:2006:FFP, author = "Venkatesh Raman and Saket Saurabh and C. R. Subramanian", title = "Faster fixed parameter tractable algorithms for finding feedback vertex sets", journal = j-TALG, volume = "2", number = "3", pages = "403--415", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Jansen:2006:AAS, author = "Klaus Jansen and Hu Zhang", title = "An approximation algorithm for scheduling malleable tasks under general precedence constraints", journal = j-TALG, volume = "2", number = "3", pages = "416--434", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Feigenbaum:2006:SMC, author = "Joan Feigenbaum and Yuval Ishai and Tal Malkin and Kobbi Nissim and Martin J. Strauss and Rebecca N. Wright", title = "Secure multiparty computation of approximations", journal = j-TALG, volume = "2", number = "3", pages = "435--472", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Johnson:2006:NCC, author = "David S. Johnson", title = "The {NP}-completeness column: {The} many limits on approximation", journal = j-TALG, volume = "2", number = "3", pages = "473--489", month = jul, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Thu Sep 21 08:13:30 MDT 2006", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Lopez-Ortiz:2006:F, author = "Alejandro L{\'o}pez-Ortiz and J. Ian Munro", title = "Foreword", journal = j-TALG, volume = "2", number = "4", pages = "491--491", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Eppstein:2006:QAM, author = "David Eppstein", title = "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms", journal = j-TALG, volume = "2", number = "4", pages = "492--509", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Geary:2006:SOT, author = "Richard F. Geary and Rajeev Raman and Venkatesh Raman", title = "Succinct ordinal trees with level-ancestor queries", journal = j-TALG, volume = "2", number = "4", pages = "510--534", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Mendelson:2006:MPQ, author = "Ran Mendelson and Robert E. Tarjan and Mikkel Thorup and Uri Zwick", title = "Melding priority queues", journal = j-TALG, volume = "2", number = "4", pages = "535--556", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Baswana:2006:ADO, author = "Surender Baswana and Sandeep Sen", title = "Approximate distance oracles for unweighted graphs in expected {$O(n^2)$} time", journal = j-TALG, volume = "2", number = "4", pages = "557--577", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Demetrescu:2006:EAD, author = "Camil Demetrescu and Giuseppe F. Italiano", title = "Experimental analysis of dynamic all pairs shortest path algorithms", journal = j-TALG, volume = "2", number = "4", pages = "578--601", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Irving:2006:RMM, author = "Robert W. Irving and Telikepalli Kavitha and Kurt Mehlhorn and Dimitrios Michail and Katarzyna E. Paluch", title = "Rank-maximal matchings", journal = j-TALG, volume = "2", number = "4", pages = "602--610", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Foschini:2006:WIE, author = "Luca Foschini and Roberto Grossi and Ankur Gupta and Jeffrey Scott Vitter", title = "When indexing equals compression: {Experiments} with compressing suffix arrays and applications", journal = j-TALG, volume = "2", number = "4", pages = "611--639", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Alon:2006:GAO, author = "Noga Alon and Baruch Awerbuch and Yossi Azar and Niv Buchbinder and Joseph (Seffi) Naor", title = "A general approach to online network optimization problems", journal = j-TALG, volume = "2", number = "4", pages = "640--660", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Evans:2006:OSV, author = "William Evans and David Kirkpatrick", title = "Optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ", journal = j-TALG, volume = "2", number = "4", pages = "661--678", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Beier:2006:CES, author = "Rene Beier and Artur Czumaj and Piotr Krysta and Berthold V{\"o}cking", title = "Computing equilibria for a service provider game with (Im)perfect information", journal = j-TALG, volume = "2", number = "4", pages = "679--706", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Moore:2006:GQF, author = "Cristopher Moore and Daniel Rockmore and Alexander Russell", title = "Generic quantum {Fourier} transforms", journal = j-TALG, volume = "2", number = "4", pages = "707--723", month = oct, year = "2006", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, } @Article{Archer:2007:FPM, author = "Aaron Archer and {\'E}va Tardos", title = "Frugal path mechanisms", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "3", } @Article{Bhatia:2007:AAB, author = "Randeep Bhatia and Julia Chuzhoy and Ari Freund and Joseph (Seffi) Naor", title = "Algorithmic aspects of bandwidth trading", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "10", } @Article{Carmo:2007:QPI, author = "Renato Carmo and Tom{\'a}s Feder and Yoshiharu Kohayakawa and Eduardo Laber and Rajeev Motwani and Liadan O'Callaghan and Rina Panigrahy and Dilys Thomas", title = "Querying priced information in databases: {The} conjunctive case", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "9", } @Article{Ciriani:2007:DSS, author = "Valentina Ciriani and Paolo Ferragina and Fabrizio Luccio and S. Muthukrishnan", title = "A data structure for a sequence of string accesses in external memory", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "6", } @Article{Cormode:2007:SED, author = "Graham Cormode and S. Muthukrishnan", title = "The string edit distance matching problem with moves", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", abstract = "The edit distance between two strings $S$ and $R$ is defined to be the minimum number of character inserts, deletes, and changes needed to convert $R$ to S. Given a text string $t$ of length $n$, and a pattern string $p$ of length $m$, informally, the string edit distance matching problem is to compute the smallest edit distance between $p$ and substrings of $t$. We relax the problem so that: (a) we allow an additional operation, namely, substring moves; and (b) we allow approximation of this string edit distance. Our result is a near-linear time deterministic algorithm to produce a factor of $O(\log n \log\star n)$ approximation to the string edit distance with moves. This is the first known significantly subquadratic algorithm for a string edit distance problem in which the distance involves nontrivial alignments. Our results are obtained by embedding strings into $L_1$ vector space using a simplified parsing technique, which we call edit-sensitive parsing (ESP).", acknowledgement = ack-nhfb, articleno = "2", } @Article{Czumaj:2007:TBW, author = "Artur Czumaj and Berthold V{\"o}cking", title = "Tight bounds for worst-case equilibria", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "4", } @Article{Elkin:2007:IAR, author = "Michael Elkin and Guy Kortsarz", title = "An improved algorithm for radio broadcast", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "8", } @Article{Eppstein:2007:FSI, author = "David Eppstein", title = "Foreword to special issue on {SODA 2002}", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "1", } @Article{Hershberger:2007:DSS, author = "John Hershberger and Subhash Suri and Amit Bhosle", title = "On the difficulty of some shortest path problems", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "5", } @Article{Pandurangan:2007:EBB, author = "Gopal Pandurangan and Eli Upfal", title = "Entropy-based bounds for online algorithms", journal = j-TALG, volume = "3", number = "1", pages = "??--??", month = feb, year = "2007", CODEN = "????", ISSN = "1549-6325", bibdate = "Sat Apr 14 10:58:14 MDT 2007", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "7", } @Article{Voronenko:2007:MMC, author = "Yevgen Voronenko and Markus P{\"u}schel", title = "Multiplierless multiple constant multiplication", journal = j-TALG, volume = "3", number = "2", pages = "11:1--11:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240234", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "A variable can be multiplied by a given set of fixed-point constants using a multiplier block that consists exclusively of additions, subtractions, and shifts. The generation of a multiplier block from the set of constants is known as the multiple constant multiplication (MCM) problem. Finding the optimal solution, namely, the one with the fewest number of additions and subtractions, is known to be NP-complete. We propose a new algorithm for the MCM problem, which produces solutions that require up to 20\% less additions and subtractions than the best previously known algorithm. At the same time our algorithm, in contrast to the closest competing algorithm, is not limited by the constant bitwidths. We present our algorithm using a unifying formal framework for the best, graph-based MCM algorithms and provide a detailed runtime analysis and experimental evaluation. We show that our algorithm can handle problem sizes as large as 100 32-bit constants in a time acceptable for most applications. The implementation of the new algorithm is available at \url{www.spiral.net}.", acknowledgement = ack-nhfb, articleno = "11", keywords = "Addition chains; directed graph; FIR filter; fixed-point arithmetic; strength reduction", } @Article{Chern:2007:PCR, author = "Hua-Huai Chern and Michael Fuchs and Hsien-Kuei Hwang", title = "Phase changes in random point quadtrees", journal = j-TALG, volume = "3", number = "2", pages = "12:1--12:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240235", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We show that a wide class of linear cost measures (such as the number of leaves) in random $d$-dimensional point quadtrees undergo a change in limit laws: If the dimension $d = 1, \ldots, 8$, then the limit law is normal; if $d \geq 9$ then there is no convergence to a fixed limit law. Stronger approximation results such as convergence rates and local limit theorems are also derived for the number of leaves, additional phase changes being unveiled. Our approach is new and very general, and also applicable to other classes of search trees. A brief discussion of Devroye's grid trees (covering $m$-ary search trees and quadtrees as special cases) is given. We also propose an efficient numerical procedure for computing the constants involved to high precision.", acknowledgement = ack-nhfb, articleno = "12", keywords = "analysis in distribution of algorithms; Asymptotic transfer; central limit theorems; depth; differential equations; grid trees; local limit theorems; Mellin transforms; page usage; phase transitions; quadtrees; total path length", } @Article{Demaine:2007:RDS, author = "Erik D. Demaine and John Iacono and Stefan Langerman", title = "Retroactive data structures", journal = j-TALG, volume = "3", number = "2", pages = "13:1--13:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240236", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present, but also in the past. In this new paradigm, called retroactive data structures, the historical sequence of operations performed on the data structure is not fixed. The data structure allows arbitrary insertion and deletion of operations at arbitrary times, subject only to consistency requirements. We initiate the study of retroactive data structures by formally defining the model and its variants. We prove that, unlike persistence, efficient retroactivity is not always achievable. Thus, we present efficient retroactive data structures for queues, doubly ended queues, priority queues, union-find, and decomposable search structures.", acknowledgement = ack-nhfb, articleno = "13", keywords = "History; persistence; point location; rollback; time travel", } @Article{Hayward:2007:IAW, author = "Ryan B. Hayward and Jeremy P. Spinrad and R. Sritharan", title = "Improved algorithms for weakly chordal graphs", journal = j-TALG, volume = "3", number = "2", pages = "14:1--14:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240237", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from $O(mn^2)$ to $O(m^2)$ and the space complexity from $O(n^3)$ to $O(m + n)$, and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from $O(mn^2)$ to $O(n^3)$ and the complexity of the independent set and clique cover problems is improved from $O(n^4)$ to $O(mn)$. The space complexity of our optimization algorithms is $O(m + n)$.", acknowledgement = ack-nhfb, articleno = "14", keywords = "coloring; graph algorithms; Perfect graphs; recognition; weakly chordal", } @Article{Kavitha:2007:SSM, author = "Telikepalli Kavitha and Kurt Mehlhorn and Dimitrios Michail and Katarzyna E. Paluch", title = "Strongly stable matchings in time {$O(nm)$} and extension to the hospitals-residents problem", journal = j-TALG, volume = "3", number = "2", pages = "15:1--15:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240238", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "An instance of the stable marriage problem is an undirected bipartite graph $G = (X \cup W, E)$ with linearly ordered adjacency lists with ties allowed in the ordering. A matching $M$ is a set of edges, no two of which share an endpoint. An edge $e = (a, b) \in E \setminus M$ is a blocking edge for $M$ if $a$ is either unmatched or strictly prefers $b$ to its partner in $M$, and $b$ is unmatched, strictly prefers $a$ to its partner in $M$, or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We give an $O(nm)$ algorithm for computing strongly stable matchings, where $n$ is the number of vertices and $m$ the number of edges. The previous best algorithm had running time $O(m^2)$. We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. We give an $O(m \sum_{h \in H} p_h)$ algorithm for computing a strongly stable matching in the hospitals-residents problem, where $p_h$ is the quota of a hospital $h$. The previous best algorithm had running time $O(m^2)$.", acknowledgement = ack-nhfb, articleno = "15", keywords = "Bipartite matching; level maximal; stable marriage; strong stability", } @Article{Bagchi:2007:DSR, author = "Amitabha Bagchi and Amitabh Chaudhary and David Eppstein and Michael T. Goodrich", title = "Deterministic sampling and range counting in geometric data streams", journal = j-TALG, volume = "3", number = "2", pages = "16:1--16:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240239", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We present memory-efficient deterministic algorithms for constructing $\epsilon$-nets and $\epsilon$-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are at least inverse-polylogarithmic. We also include a lower bound for noniceberg geometric queries.", acknowledgement = ack-nhfb, articleno = "16", keywords = "Data streams; epsilon nets; geometric data; iceberg queries; range counting; robust statistics; sampling; streaming algorithms", } @Article{Arya:2007:SEB, author = "Sunil Arya and Theocharis Malamatos and David M. Mount", title = "A simple entropy-based algorithm for planar point location", journal = j-TALG, volume = "3", number = "2", pages = "17:1--17:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240240", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability p z that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in $O(H)$ average time. We also present empirical evidence for the practical efficiency of this approach.", acknowledgement = ack-nhfb, articleno = "17", keywords = "entropy; expected-case complexity; Point location; polygonal subdivision; randomized algorithms; trapezoidal maps", } @Article{Kauers:2007:ADZ, author = "Manuel Kauers", title = "An algorithm for deciding zero equivalence of nested polynomially recurrent sequences", journal = j-TALG, volume = "3", number = "2", pages = "18:1--18:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240241", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We introduce the class of nested polynomially recurrent sequences which includes a large number of sequences that are of combinatorial interest. We present an algorithm for deciding zero equivalence of these sequences, thereby providing a new algorithm for proving identities among combinatorial sequences: In order to prove an identity, decide by the algorithm whether the difference of lefthand-side and righthand-side is identically zero. This algorithm is able to treat mathematical objects which are not covered by any other known symbolic method for proving combinatorial identities. Despite its theoretical flavor and high complexity, an implementation of the algorithm can be successfully applied to nontrivial examples.", acknowledgement = ack-nhfb, articleno = "18", keywords = "combinatorial sequences; nested polynomially recurrent sequences; Symbolic computation; zero equivalence", } @Article{Amir:2007:DTS, author = "Amihood Amir and Gad M. Landau and Moshe Lewenstein and Dina Sokol", title = "Dynamic text and static pattern matching", journal = j-TALG, volume = "3", number = "2", pages = "19:1--19:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240242", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "In this article, we address a new version of dynamic pattern matching. The dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all new occurrences of the pattern in the text after each text update. We present an algorithm for solving the problem where the text update operation is changing the symbol value of a text location. Given a text of length $n$ and a pattern of length $m$, our algorithm preprocesses the text in time $O(n \log \log m)$, and the pattern in time $O (m \log m)$. The extra space used is $O(n + m \log m)$. Following each text update, the algorithm deletes all prior occurrences of the pattern that no longer match, and reports all new occurrences of the pattern in the text in $O(\log \log m)$ time. We note that the complexity is not proportional to the number of pattern occurrences, since all new occurrences can be reported in a succinct form.", acknowledgement = ack-nhfb, articleno = "19", keywords = "border trees; Dynamic text; static pattern", } @Article{Ferragina:2007:CRS, author = "Paolo Ferragina and Giovanni Manzini and Veli M{\"a}kinen and Gonzalo Navarro", title = "Compressed representations of sequences and full-text indexes", journal = j-TALG, volume = "3", number = "2", pages = "20:1--20:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240243", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Given a sequence $S = s_1 s_2 \ldots s_n$ of integers smaller than $r = O(\polylog(n))$, we show how $S$ can be represented using $nH_0(S) + o(n)$ bits, so that we can know any $s_q$, as well as answer rank and select queries on $S$, in constant time. $H_0(S)$ is the zero-order empirical entropy of $S$ and $nH_0(S)$ provides an information-theoretic lower bound to the bit storage of any sequence $S$ via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in $O(\log r)$ time. For larger $r$, we can still represent $S$ in $nH_0(S) + o(n \log r)$ bits and answer queries in $O(\log r / \log \log n)$ time.\par Another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet $\Sigma$. Specifically, we design a variant of the FM-index that indexes a string $T[1,n]$ within $nH_k(T) + o(n)$ bits of storage, where $H_k(T)$ is the $k$th-order empirical entropy of $T$. This space bound holds simultaneously for all $k \leq \alpha \log |\Sigma| n$, constant $0 < \alpha < 1$, and $|\Sigma| = O(\polylog(n))$. This index counts the occurrences of an arbitrary pattern $P[1,p]$ as a substring of $T$ in $O(p)$ time; it locates each pattern occurrence in $O(\log 1+\varepsilon n)$ time for any constant $0 < \varepsilon < 1$; and reports a text substring of length $\ell$ in $O(\ell + \log 1+\varepsilon n)$ time.\par Compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. Still, our index uses essentially the same space of the $k$th-order entropy of the text $T$, which is the best space obtained in previous work. We can also handle larger alphabets of size $|\Sigma| = O(n \beta)$, for any $0 < \beta < 1$, by paying $o(n \log |\Sigma|)$ extra space and multiplying all query times by $O(\log |\Sigma|/ \log \log n)$.", acknowledgement = ack-nhfb, articleno = "20", keywords = "Burrows-Wheeler transform; compression boosting; entropy; rank and select; text compression; Text indexing; wavelet tree", } @Article{Chan:2007:CID, author = "Ho-Leung Chan and Wing-Kai Hon and Tak-Wah Lam and Kunihiko Sadakane", title = "Compressed indexes for dynamic text collections", journal = j-TALG, volume = "3", number = "2", pages = "21:1--21:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240244", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Let $T$ be a string with $n$ characters over an alphabet of constant size. A recent breakthrough on compressed indexing allows us to build an index for $T$ in optimal space (i.e., $O(n)$ bits), while supporting very efficient pattern matching [Ferragina and Manzini 2000; Grossi and Vitter 2000]. Yet the compressed nature of such indexes also makes them difficult to update dynamically.\par This article extends the work on optimal-space indexing to a dynamic collection of texts. Our first result is a compressed solution to the library management problem, where we show an index of $O(n)$ bits for a text collection $L$ of total length $n$, which can be updated in $O(| T | \log n)$ time when a text $T$ is inserted or deleted from $L$; also, the index supports searching the occurrences of any pattern $P$ in all texts in $L$ in $O(|P| log n + {\rm occ} \log 2 n)$ time, where {\rm occ} is the number of occurrences.\par Our second result is a compressed solution to the dictionary matching problem, where we show an index of $O(d)$ bits for a pattern collection $D$ of total length $d$, which can be updated in $O(|P| \log 2 d)$ time when a pattern $P$ is inserted or deleted from $D$; also, the index supports searching the occurrences of all patterns of $D$ in any text $T$ in $O((|T| + {\rm occ})\log 2 d)$ time. When compared with the $O(d \log d)$-bit suffix-tree-based solution of Amir et al. [1995], the compact solution increases the query time by roughly a factor of $\log d$ only.\par The solution to the dictionary matching problem is based on a new compressed representation of a suffix tree. Precisely, we give an $O(n)$-bit representation of a suffix tree for a dynamic collection of texts whose total length is $n$, which supports insertion and deletion of a text $T$ in $O(|T| \log 2 n)$ time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. In the study of the aforementioned result, we also derive the first $O(n)$-bit representation for maintaining $n$ pairs of balanced parentheses in $O(\log n / \log \log n)$ time per operation, matching the time complexity of the previous $O(n \log n)$-bit solution.", acknowledgement = ack-nhfb, articleno = "21", keywords = "Compressed suffix tree; string matching", } @Article{Boyar:2007:RWO, author = "Joan Boyar and Lene M. Favrholdt", title = "The relative worst order ratio for online algorithms", journal = j-TALG, volume = "3", number = "2", pages = "22:1--22:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240245", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We define a new measure for the quality of online algorithms, the relative worst order ratio, using ideas from the max/max ratio [Ben-David and Borodin 1994] and from the random order ratio [Kenyon 1996]. The new ratio is used to compare online algorithms directly by taking the ratio of their performances on their respective worst permutations of a worst-case sequence.\par Two variants of the bin packing problem are considered: the classical bin packing problem, where the goal is to fit all items in as few bins as possible, and the dual bin packing problem, which is the problem of maximizing the number of items packed in a fixed number of bins. Several known algorithms are compared using this new measure, and a new, simple variant of first-fit is proposed for dual bin packing.\par Many of our results are consistent with those previously obtained with the competitive ratio or the competitive ratio on accommodating sequences, but new separations and easier proofs are found.", acknowledgement = ack-nhfb, articleno = "22", keywords = "bin packing; dual bin packing; Online; quality measure; relative worst order ratio", } @Article{Becchetti:2007:SCM, author = "L. Becchetti and J. K{\"o}nemann and S. Leonardi and M. P{\'a}al", title = "Sharing the cost more efficiently: {Improved} approximation for multicommodity rent-or-buy", journal = j-TALG, volume = "3", number = "2", pages = "23:1--23:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240246", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "In the multicommodity rent-or-buy (MROB) network design problems, we are given a network together with a set of $k$ terminal pairs $(s_1, t_1), \ldots, (s_k, t_k)$. The goal is to provision the network so that a given amount of flow can be shipped between $s_i$ and $t_i$ for all $1 \leq i \leq k$ simultaneously. In order to provision the network, one can either rent capacity on edges at some cost per unit of flow, or buy them at some larger fixed cost. Bought edges have no incremental, flow-dependent cost. The overall objective is to minimize the total provisioning cost.\par Recently, Gupta et al. [2003a] presented a 12-approximation for the MROB problem. Their algorithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate Steiner forest for these pairs. This technique had previously been introduced [Gupta et al. 2003b] for the single-sink rent-or-buy network design problem.\par In this article we give a 6.828-approximation for the MROB problem by refining the algorithm of Gupta et al. and simplifying their analysis. The improvement in our article is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the Steiner forest problem due to Agrawal et al. [1995]. Our result significantly reduces the gap between the single-sink and multisink case.", acknowledgement = ack-nhfb, articleno = "23", keywords = "Approximation algorithms; cost sharing; network design; Steiner forests", } @Article{Johnson:2007:NCC, author = "David S. Johnson", title = "The {NP}-completeness column: {Finding} needles in haystacks", journal = j-TALG, volume = "3", number = "2", pages = "24:1--24:??", month = may, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1240233.1240247", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:54:42 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "This is the 26th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book ``Computers and Intractability: A Guide to the Theory of NP-Completeness,'' W. H. Freeman {\&} Co., New York, 1979, hereinafter referred to as ``[G{\&}J].'' Previous columns, the first 23 of which appeared in J. Algorithms, will be referred to by a combination of their sequence number and year of appearance, e.g., ``Column 1 [1981].'' Full bibliographic details on the previous columns, as well as downloadable unofficial versions of them, can be found at \url{http://www.research.att.com/~dsj/columns/}. This column discusses the question of whether finding an object can be computationally difficult even when we know that the object exists.", acknowledgement = ack-nhfb, articleno = "24", keywords = "fixed point; game theory; local search; Nash equilibrium; PLS; PPAD", } @Article{Feng:2007:FAS, author = "Jianxing Feng and Daming Zhu", title = "Faster algorithms for sorting by transpositions and sorting by block interchanges", journal = j-TALG, volume = "3", number = "3", pages = "25:1--25:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273341", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity $O(n^{3/2} \sqrt{\log n})$. By means of the permutation tree, we can improve this algorithm to achieve time complexity $O(n \log n)$. We can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from $O(n^2)$ down to $O(n \log n)$.", acknowledgement = ack-nhfb, articleno = "25", keywords = "Block interchange; genome; permutation; time complexity; transposition; tree", } @Article{Gupta:2007:CPD, author = "Himanshu Gupta and Rephael Wenger", title = "Constructing pairwise disjoint paths with few links", journal = j-TALG, volume = "3", number = "3", pages = "26:1--26:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273342", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Let $P$ be a simple polygon and let $\{(u_1, u{\prime}_1), (u_2, u{\prime}_2), \ldots, (u_m, u{\prime}_m)\}$ be a set of $m$ pairs of distinct vertices of $P$, where for every distinct $i, $j \leq m$, there exist pairwise disjoint (nonintersecting) paths connecting $u_i$ to $u\prime_i$ and $u_j$ to $u\prime_j$. We wish to construct $m$ pairwise disjoint paths in the interior of $P$ connecting $u_i$ to $u\prime_i$ for $i = 1, \ldots, m$, with a minimal total number of line segments. We give an approximation algorithm that constructs such a set of paths using $O(M)$ line segments in $O(n \log m + M \log m)$ time, where $M$ is the number of line segments in the optimal solution and $n$ is the size of the polygon.", acknowledgement = ack-nhfb, articleno = "26", keywords = "isomorphic triangulations; Link paths; noncrossing; polygon", } @Article{Chekuri:2007:MDF, author = "Chandra Chekuri and Marcelo Mydlarz and F. Bruce Shepherd", title = "Multicommodity demand flow in a tree and packing integer programs", journal = j-TALG, volume = "3", number = "3", pages = "27:1--27:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273343", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider requests for capacity in a given tree network T =(V, E) where each edge e of the tree has some integer capacity u e. Each request f is a node pair with an integer demand d f and a profit w f which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and $b$-matching problems.\par When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing.\par We then consider the problem with arbitrary demands. When the maximum demand $d_{\rm max} is at most the minimum edge capacity $u_{\rm min}, we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.", acknowledgement = ack-nhfb, articleno = "27", keywords = "approximation algorithm; Integer multicommodity flow; integrality gap; packing integer program; tree", } @Article{Bar-Noy:2007:WSR, author = "Amotz Bar-Noy and Richard E. Ladner and Tami Tamir", title = "Windows scheduling as a restricted version of bin packing", journal = j-TALG, volume = "3", number = "3", pages = "28:1--28:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273344", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Given a sequence of $n$ positive integers $w_1, w_2, \ldots, w_n$ that are associated with the items $1, 2, \ldots n$, respectively. In the windows scheduling problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page $i$ on any of the channels is at most $w_i$ slots (a slot is the transmission time of one page). In the unit-fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item $i$ is $1 / w_i$. The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least $1 / w_i$ of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing.\par Let $H = \lceil \sum_{i=1}^n (1/ w_i)$ be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used $H + O(\ln H)$ channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most $H + 1$ bins. In the online setting, this article presents algorithms for both problems with $H + O(\sqrt{H})$ channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least $H + \Omega(\ln H)$ bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem.", acknowledgement = ack-nhfb, articleno = "28", keywords = "approximation algorithms; bin-packing; online algorithms; Periodic scheduling", } @Article{Hazay:2007:APM, author = "Carmit Hazay and Moshe Lewenstein and Dina Sokol", title = "Approximate parameterized matching", journal = j-TALG, volume = "3", number = "3", pages = "29:1--29:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273345", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Two equal length strings $s$ and $s\prime$ , over alphabets ${\Sigma} s$ and ${\Sigma} s \prime$, parameterize match if there exists a bijection ${\pi} : {\Sigma} s \rightarrow {\Sigma} s \prime$ such that ${\pi}(s) = s \prime$, where ${\pi} (s)$ is the renaming of each character of $s$ via ${\pi}$. Parameterized matching is the problem of finding all parameterized matches of a pattern string $p$ in a text $t$, and approximate parameterized matching is the problem of finding at each location a bijection ${\pi}$ that maximizes the number of characters that are mapped from $p$ to the appropriate $|p|$-length substring of $t$.\par Parameterized matching was introduced as a model for software duplication detection in software maintenance systems and also has applications in image processing and computational biology. For example, approximate parameterized matching models image searching with variable color maps in the presence of errors.\par We consider the problem for which an error threshold, $k$, is given, and the goal is to find all locations in $t$ for which there exists a bijection ${\pi}$ which maps $p$ into the appropriate $|p|$-length substring of $t$ with at most $k$ mismatched mapped elements. Our main result is an algorithm for this problem with $O(nk^{1.5} + mk \log m)$ time complexity, where $m = | p |$ and $n = | t |$. We also show that when $| p | = | t | = m$, the problem is equivalent to the maximum matching problem on graphs, yielding a $O(m + k^{1.5})$ solution.", acknowledgement = ack-nhfb, articleno = "29", keywords = "Hamming distance; maximum matching; mismatch pair; parameterize match", } @Article{Halldorsson:2007:IAR, author = "Magn{\'u}s M. Halld{\'o}rsson and Kazuo Iwama and Shuichi Miyazaki and Hiroki Yanagisawa", title = "Improved approximation results for the stable marriage problem", journal = j-TALG, volume = "3", number = "3", pages = "30:1--30:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273346", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm.\par In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of $2/(1 + L - 2)$ for instances in which only men have ties of length at most $L$. When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of $13/7(< 1.858)$. We also improve the lower bound on the approximation ratio to $21/19(> 1.1052)$.", acknowledgement = ack-nhfb, articleno = "30", keywords = "Approximation algorithms; incomplete lists; stable marriage problem; ties", } @Article{Indyk:2007:NNP, author = "Piotr Indyk and Assaf Naor", title = "Nearest-neighbor-preserving embeddings", journal = j-TALG, volume = "3", number = "3", pages = "31:1--31:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273347", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean metrics with low ``intrinsic'' dimension. Combining the embeddings with known data structures yields the best-known approximate nearest-neighbor data structures for such metrics.", acknowledgement = ack-nhfb, articleno = "31", keywords = "dimensionality reduction; doubling spaces; embeddings; Nearest neighbor", } @Article{Even-Dar:2007:CTN, author = "Eyal Even-Dar and Alex Kesselman and Yishay Mansour", title = "Convergence time to {Nash} equilibrium in load balancing", journal = j-TALG, volume = "3", number = "3", pages = "32:1--32:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273348", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We study the number of steps required to reach a pure Nash equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models, including identical, restricted, related, and unrelated machines. Our results have a crucial dependence on the weights assigned to jobs. We consider arbitrary weights, integer weights, k distinct weights, and identical (unit) weights. We look both at an arbitrary schedule (where the only restriction is that a job migrates to a machine which lowers its cost) and specific efficient schedulers (e.g., allowing the largest weight job to move first). A by-product of our results is establishing a connection between various scheduling models and the game-theoretic notion of potential games. We show that load balancing in unrelated machines is a generalized ordinal potential game, load balancing in related machines is a weighted potential game, and load balancing in related machines and unit weight jobs is an exact potential game.", acknowledgement = ack-nhfb, articleno = "32", keywords = "convergence time; game theory; Nash equilibrium", } @Article{Andrews:2007:RSM, author = "Matthew Andrews and Lisa Zhang", title = "Routing and scheduling in multihop wireless networks with time-varying channels", journal = j-TALG, volume = "3", number = "3", pages = "33:1--33:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273349", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We study routing and scheduling in multihop wireless networks. When data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. The data transmission is node constrained, that is, every node can transmit data to at most one neighboring node per time step. The transmission rates are time varying as a result of changing wireless channel conditions.\par In this article, we assume that data arrivals and transmission rates are governed by an adversary. The power of the adversary is limited by an admissibility condition which forbids the adversary from overloading any wireless node a priori. The node-constrained transmission and time-varying nature of the transmission rates make our model different from and harder than the standard adversarial queueing model which relates to wireline networks.\par For the case in which the adversary specifies the paths that the data must follow, we design scheduling algorithms that ensure network stability. These algorithms try to give priority to the data that is closest to its source node. However, at each time step only a subset of the data queued at a node is eligible for scheduling. One of our algorithms is fully distributed.\par For the case in which the adversary does not dictate the data paths, we show how to route data so that the admissibility condition is satisfied. We can then schedule data along the chosen paths using our stable scheduling algorithms.", acknowledgement = ack-nhfb, articleno = "33", keywords = "routing; Scheduling; stability; time-varying; wireless network", } @Article{Naor:2007:NAP, author = "Moni Naor and Udi Wieder", title = "Novel architectures for {P2P} applications: {The} continuous-discrete approach", journal = j-TALG, volume = "3", number = "3", pages = "34:1--34:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273350", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We propose a new approach for constructing P2P networks based on a dynamic decomposition of a continuous space into cells corresponding to servers. We demonstrate the power of this approach by suggesting two new P2P architectures and various algorithms for them. The first serves as a DHT (distributed hash table) and the other is a dynamic expander network. The DHT network, which we call Distance Halving, allows logarithmic routing and load while preserving constant degrees. It offers an optimal tradeoff between degree and path length in the sense that degree d guarantees a path length of $O(\log d n)$. Another advantage over previous constructions is its relative simplicity. A major new contribution of this construction is a dynamic caching technique that maintains low load and storage, even under the occurrence of hot spots. Our second construction builds a network that is guaranteed to be an expander. The resulting topologies are simple to maintain and implement. Their simplicity makes it easy to modify and add protocols. A small variation yields a DHT which is robust against random Byzantine faults. Finally we show that, using our approach, it is possible to construct any family of constant degree graphs in a dynamic environment, though with worse parameters. Therefore, we expect that more distributed data structures could be designed and implemented in a dynamic environment.", acknowledgement = ack-nhfb, articleno = "34", keywords = "Peer-to-peer networks; routing", } @Article{Khuller:2007:PC, author = "Samir Khuller", title = "Problems column", journal = j-TALG, volume = "3", number = "3", pages = "35:1--35:??", month = aug, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1273340.1273351", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:11 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "35", } @Article{Gabow:2007:ISS, author = "H. N. Gabow and Michael A. Bender and Martin Farach-Colton", title = "Introduction to {SODA} 2002 and 2003 special issue", journal = j-TALG, volume = "3", number = "4", pages = "36:1--36:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290673", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "36", } @Article{Aspnes:2007:SG, author = "James Aspnes and Gauri Shah", title = "Skip graphs", journal = j-TALG, volume = "3", number = "4", pages = "37:1--37:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290674", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors within it introduced due to node failures.", acknowledgement = ack-nhfb, articleno = "37", keywords = "overlay networks; Peer-to-peer; skip lists", } @Article{Han:2007:OPS, author = "Yijie Han", title = "Optimal parallel selection", journal = j-TALG, volume = "3", number = "4", pages = "38:1--38:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290675", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We present an optimal parallel selection algorithm on the EREW PRAM. This algorithm runs in $O(\log n)$ time with $n / \log n$ processors. This complexity matches the known lower bound for parallel selection on the EREW PRAM model. We therefore close this problem which has been open for more than a decade.", acknowledgement = ack-nhfb, articleno = "38", keywords = "EREW PRAM; Parallel algorithms; selection", } @Article{Bansal:2007:MWF, author = "Nikhil Bansal and Kedar Dhamdhere", title = "Minimizing weighted flow time", journal = j-TALG, volume = "3", number = "4", pages = "39:1--39:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290676", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is $O(k)$-competitive for $k$ weight classes. This implies an $O (\log W)$-competitive algorithm, where $W$ is the maximum to minimum ratio of weights. This algorithm also implies an $O(\log n + \log P)$-approximation ratio for the problem, where $P$ is the ratio of the maximum to minimum job size and $n$ is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a $(1 + \varepsilon)$-speed, $(1 +1/\varepsilon)$-competitive online algorithm.", acknowledgement = ack-nhfb, articleno = "39", keywords = "nonclairvoyant scheduling; online algorithms; response time; Scheduling", } @Article{Fakcharoenphol:2007:TRP, author = "Jittat Fakcharoenphol and Chris Harrelson and Satish Rao", title = "The $k$-traveling repairmen problem", journal = j-TALG, volume = "3", number = "4", pages = "40:1--40:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290677", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider the $k$-traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time $8.497 \alpha$-approximation algorithm for this generalization, where $\alpha$ denotes the best achievable approximation factor for the problem of finding the least-cost rooted tree spanning i vertices of a metric. For the latter problem, a $(2 + \varepsilon)$-approximation is known. Our results can be compared with the best-known approximation algorithm using similar techniques for the case $k = 1$, which is $3.59\alpha$. Moreover, recent work of Chaudry et al. [2003] shows how to remove the factor of $\alpha$, thus improving all of these results by that factor. We are aware of no previous work on the approximability of the present problem. In addition, we give a simple proof of the $3.59 \alpha$-approximation result that can be more easily extended to the case of multiple repairmen, and may be of independent interest.", acknowledgement = ack-nhfb, articleno = "40", keywords = "Traveling salesman; vehicle routing", } @Article{Irani:2007:APS, author = "Sandy Irani and Sandeep Shukla and Rajesh Gupta", title = "Algorithms for power savings", journal = j-TALG, volume = "3", number = "4", pages = "41:1--41:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290678", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve $P(s)$ which indicates the power consumption level given a particular speed. We assume that $P(s)$ is convex, nondecreasing, and nonnegative for $s \geq 0$. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.", acknowledgement = ack-nhfb, articleno = "41", keywords = "dynamic speed scaling; online algorithms; Power savings", } @Article{Alon:2007:GSE, author = "Noga Alon and Venkatesan Guruswami and Tali Kaufman and Madhu Sudan", title = "Guessing secrets efficiently via list decoding", journal = j-TALG, volume = "3", number = "4", pages = "42:1--42:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290679", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider the guessing secrets problem defined by Chung et al. [2001]. This is a variant of the standard 20 questions game where the player has a set of $k > 1$ secrets from a universe of $N$ possible secrets. The player is asked Boolean questions about the secret. For each question, the player picks one of the $k$ secrets adversarially, and answers according to this secret.\par We present an explicit set of $O(\log N)$ questions together with an efficient (i.e., ${\rm poly}(\log N)$ time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by Chung et al. [2001]. The main techniques we use are small $\epsilon$-biased spaces and the notion of list decoding.\par We also establish bounds on the number of questions needed to solve the $k-secrets game for $k > 2$, and discuss how list decoding can be used to get partial information about the secrets, specifically to find a small core of secrets that must intersect the actual set of $k$ secrets.", acknowledgement = ack-nhfb, articleno = "42", keywords = "20 questions; $\epsilon$-biased spaces; decoding algorithms; error-correcting codes; $k$-universal sets", } @Article{Raman:2007:SID, author = "Rajeev Raman and Venkatesh Raman and Srinivasa Rao Satti", title = "Succinct indexable dictionaries with applications to encoding $k$-ary trees, prefix sums and multisets", journal = j-TALG, volume = "3", number = "4", pages = "43:1--43:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290680", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider the indexable dictionary problem, which consists of storing a set $S \subseteq \{0, \ldots , m - 1\}$ for some integer $m$ while supporting the operations of $\rank(x)$, which returns the number of elements in $S$ that are less than $x$ if $x \in S$, and $-1$ otherwise; and $\select(i)$, which returns the $i$th smallest element in $S$. We give a data structure that supports both operations in $O(1)$ time on the RAM model and requires $B(n,m) + o(n) + O(\lg \lg m)$ bits to store a set of size $n$, where $B(n, m) = \lfloor \lg (m / n)\rfloor$ is the minimum number of bits required to store any $n$-element subset from a universe of size $m$. Previous dictionaries taking this space only supported (yes/no) membership queries in $O (1)$ time. In the cell probe model we can remove the $O (\lg \lg m)$ additive term in the space bound, answering a question raised by Fich and Miltersen [1995] and Pagh [2001].\par We present extensions and applications of our indexable dictionary data structure, including:\par --- an information-theoretically optimal representation of a $k$-ary cardinal tree that supports standard operations in constant time;\par --- a representation of a multiset of size $n$ from $\{0, \ldots , m - 1\}$ in $B(n, m + n) + o(n)$ bits that supports (appropriate generalizations of) rank and select operations in constant time; and $+ O(\lg \lg m)$\par --- a representation of a sequence of $n$ nonnegative integers summing up to $m$ in $B(n, m + n) + o(n)$ bits that supports prefix sum queries in constant time.", acknowledgement = ack-nhfb, articleno = "43", keywords = "Dictionaries; multisets; perfect hashing; prefix sums; sets; succinct data structures; tries", } @Article{Janson:2007:PFS, author = "Svante Janson and Wojciech Szpankowski", title = "Partial fillup and search time in {LC} tries", journal = j-TALG, volume = "3", number = "4", pages = "44:1--44:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290681", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Andersson and Nilsson introduced in 1993 a level-compressed trie (for short, LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent experimental results indicated a ``dramatic improvement'' when full subtrees are replaced by ``partially filled subtrees.'' In this article, we provide a theoretical justification of these experimental results, showing, among others, a rather moderate improvement in search time over the original LC tries. For such an analysis, we assume that n strings are generated independently by a binary memoryless source, with p denoting the probability of emitting a ``1'' (and $q = 1 - p$). We first prove that the so-called {$\alpha$}-fillup level $F_n (\alpha)$ (i.e., the largest level in a trie with $\alpha$ fraction of nodes present at this level) is concentrated on two values with high probability: either $F_n(\alpha) = k_n$ or $F_n ({\alpha}) = k_n + 1$, where $k_n = \log 1/\sqrt{pq} n - |ln(p/q)|/2 ln 3/2 (1 \sqrt{pq}) {\Phi} - 1 (\alpha) \sqrt{ \ln n} + O(1)$ is an integer and $\Phi(x)$ denotes the normal distribution function. This result directly yields the typical depth (search time) $D_n (\alpha)$ in the $\alpha$-LC tries, namely, we show that with high probability $D_n(\alpha) \sim C_2 \log \log n$, where $C_2 = 1/|log(1 - h / \log(1/\sqrt{pq}))|$ for $p \neq q$ and $h = -p \log p - q \log q$ is the Shannon entropy rate. This should be compared with recently found typical depth in the original LC tries, which is $C_1 \log \log n$, where $C_1 = 1/|log(1 - h) / log(1/\min\{p, 1 - p\})|$. In conclusion, we observe that $\alpha$ affects only the lower term of the $\alpha$-fillup level $F_n(\alpha)$, and the search time in $\alpha$-LC tries is of the same order as in the original LC tries.", acknowledgement = ack-nhfb, articleno = "44", keywords = "Digital trees; level-compressed tries; partial fillup; Poissonization; probabilistic analysis; strings; trees", } @Article{Hershberger:2007:FSS, author = "John Hershberger and Matthew Maxel and Subhash Suri", title = "Finding the $k$ shortest simple paths: {A} new algorithm and its implementation", journal = j-TALG, volume = "3", number = "4", pages = "45:1--45:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290682", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We describe a new algorithm to enumerate the $k$ shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed by Hershberger and Suri [2001], and can yield a factor $\Theta(n)$ improvement for this problem. But there is a caveat: The fast replacement paths subroutine is known to fail for some directed graphs. However, the failure is easily detected, and so our k shortest paths algorithm optimistically uses the fast subroutine, then switches to a slower but correct algorithm if a failure is detected. Thus, the algorithm achieves its $\Theta(n)$ speed advantage only when the optimism is justified. Our empirical results show that the replacement paths failure is a rare phenomenon, and the new algorithm outperforms the current best algorithms; the improvement can be substantial in large graphs. For instance, on GIS map data with about 5,000 nodes and 12,000 edges, our algorithm is 4--8 times faster. In synthetic graphs modeling wireless ad hoc networks, our algorithm is about 20 times faster.", acknowledgement = ack-nhfb, articleno = "45", keywords = "directed paths; Loop-free paths; path equivalence class; replacement paths", } @Article{Chekuri:2007:EDP, author = "Chandra Chekuri and Sanjeev Khanna", title = "Edge-disjoint paths revisited", journal = j-TALG, volume = "3", number = "4", pages = "46:1--46:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290683", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an $\Omega(m^{1/2} - \epsilon)$-hardness result of Guruswami et al. [2003], and an $O (\sqrt{m})$ approximation achievable via a natural multicommodity-flow-based LP relaxation as well as a greedy algorithm. Here $m$ is the number of edges in the graph. We observe that the $\Omega(m^{1/2} - {\epsilon})$-hardness of approximation applies to sparse graphs, and hence when expressed as a function of $n$, that is, the number of vertices, only an $\Omega(n^{1/2} - \epsilon)$-hardness follows. On the other hand, $O(\sqrt{m})$-approximation algorithms do not guarantee a sublinear (in terms of $n$) approximation algorithm for dense graphs. We note that a similar gap exists in the known results on the integrality gap of the flow-based LP relaxation: an $\Omega(\sqrt{n})$ lower bound and $O(\sqrt{m})$ upper bound. Motivated by this discrepancy in the upper and lower bounds, we study algorithms for EDP in directed and undirected graphs and obtain improved approximation ratios. We show that the greedy algorithm has an approximation ratio of $O(\min(n^{2/3}, \sqrt{m}))$ in undirected graphs and a ratio of $O (\min(n^{4/5}, \sqrt{m}))$ in directed graphs. For acyclic graphs we give an $O(\sqrt{n} \ln n)$ approximation via LP rounding. These are the first sublinear approximation ratios for EDP. The results also extend to EDP with weights and to the uniform-capacity unsplittable flow problem (UCUFP).", acknowledgement = ack-nhfb, articleno = "46", keywords = "approximation algorithm; Edge-disjoint paths; greedy algorithm; multicommodity flow relaxation", } @Article{Cheriyan:2007:PED, author = "Joseph Cheriyan and Mohammad R. Salavatipour", title = "Packing element-disjoint steiner trees", journal = j-TALG, volume = "3", number = "4", pages = "47:1--47:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290684", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Given an undirected graph $G(V, E)$ with terminal set $T \subseteq V$, the problem of packing element-disjoint Steiner trees is to find the maximum number of Steiner trees that are disjoint on the nonterminal nodes and on the edges. The problem is known to be NP-hard to approximate within a factor of $\Omega(\log n)$, where $n$ denotes $|V|$. We present a randomized $O(\log n)$-approximation algorithm for this problem, thus matching the hardness lower bound. Moreover, we show a tight upper bound of $O(\log n)$ on the integrality ratio of a natural linear programming relaxation.", acknowledgement = ack-nhfb, articleno = "47", keywords = "approximation algorithms; element-disjoint; hardness of approximation; Packing; Steiner trees", } @Article{Krivelevich:2007:AAH, author = "Michael Krivelevich and Zeev Nutov and Mohammad R. Salavatipour and Jacques Verstraete Yuster and Raphael Yuster", title = "Approximation algorithms and hardness results for cycle packing problems", journal = j-TALG, volume = "3", number = "4", pages = "48:1--48:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290685", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "The cycle packing number $\nu e(G)$ of a graph $G$ is the maximum number of pairwise edge-disjoint cycles in $G$. Computing $\nu e(G)$ is an NP-hard problem. We present approximation algorithms for computing $\nu e (G)$ in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and show that it has approximation ratio $\Theta(\sqrt{\log n})$, where $n = |V(G)|$. This improves upon the previous $O(\log n)$ upper bound for the approximation ratio of this algorithm. In the directed case we present a $\sqrt{n}$-approximation algorithm. Finally, we give an $O(n^{2/3})$-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset $S$ of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of $\nu e(G)$ in directed graphs. Specifically, we prove a lower bound of $\Omega(\log n / \log \log n)$ for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate $\nu e(G)$ within a factor of $O(\log 1 - \varepsilon n)$ for any constant $\varepsilon > 0$. This improves upon the previously known APX-hardness result for this problem.", acknowledgement = ack-nhfb, articleno = "48", keywords = "approximation algorithms; Cycle packing; edge-disjoint; hardness of approximation; integrality gap", } @Article{Albers:2007:EEA, author = "Susanne Albers and Hiroshi Fujiwara", title = "Energy-efficient algorithms for flow time minimization", journal = j-TALG, volume = "3", number = "4", pages = "49:1--49:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290686", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs.\par We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.", acknowledgement = ack-nhfb, articleno = "49", keywords = "competitive analysis; dynamic programming; flow time; offline algorithms; online algorithms; Variable-speed processor", } @Article{Chrobak:2007:IOA, author = "Marek Chrobak and Wojciech Jawor and Ji{\v{r}}{\'\i} Sgall and Tom{\'a}{\v{s}} Tich{\'y}", title = "Improved online algorithms for buffer management in {QoS} switches", journal = j-TALG, volume = "3", number = "4", pages = "50:1--50:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290687", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online $64/33 \approx 1.939$-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio $\approx 1.377$ and a matching lower bound.", acknowledgement = ack-nhfb, articleno = "50", keywords = "Online algorithms; scheduling", } @Article{Hajiaghayi:2007:ORN, author = "Mohammad Taghi Hajiaghayi and Robert D. Kleinberg and Harald R{\"a}cke and Tom Leighton", title = "Oblivious routing on node-capacitated and directed graphs", journal = j-TALG, volume = "3", number = "4", pages = "51:1--51:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290688", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Oblivious routing algorithms for general undirected networks were introduced by R{\"a}cke [2002], and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities.\par We present the first nontrivial upper bounds for both these cases, providing algorithms for $k$-commodity oblivious routing problems with competitive ratio $O(\sqrt{k \log(n)})$ for undirected node-capacitated graphs and $O(\sqrt{k_n} 1/4 \log(n))$ for directed graphs. In the special case that all commodities have a common source or sink, our upper bound becomes $O(\sqrt{n} \log(n))$ in both cases, matching the lower bound up to a factor of $\log(n)$. The lower bound (which first appeared in Azar et al. [2003]) is obtained on a graph with very high degree. We show that, in fact, the degree of a graph is a crucial parameter for node-capacitated oblivious routing in undirected graphs, by providing an $O (\Delta \polylog(n))$-competitive oblivious routing scheme for graphs of degree $\Delta$. For the directed case, however, we show that the lower bound of $\Omega(\sqrt{n})$ still holds in low-degree graphs.\par Finally, we settle an open question about routing problems in which all commodities share a common source or sink. We show that even in this simplified scenario there are networks in which no oblivious routing algorithm can achieve a competitive ratio better than $\Omega(\log n)$.", acknowledgement = ack-nhfb, articleno = "51", keywords = "communication networks; directed graphs; node-capacitated graphs; Oblivious routing", } @Article{Auletta:2007:RSU, author = "Vincenzo Auletta and Roberto De Prisco and Paolo Penna and Giuseppe Persiano", title = "Routing selfish unsplittable traffic", journal = j-TALG, volume = "3", number = "4", pages = "52:1--52:??", month = nov, year = "2007", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1290672.1290689", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:55:31 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider general resource assignment games involving selfish users/agents in which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which minimize the latency of their own traffic). We propose and study a mechanism design approach in which an allocation mechanism assigns users to resources and charges the users for using the resources so as to induce each user to truthfully report a private piece of information he/she holds (e.g., how much traffic he/she needs to transmit). This information is crucial for computing optimal (or close to optimal) allocations and an agent could misreport his/her information to induce the underlying allocation algorithm to output a solution which he/she likes more (e.g., which assigns better resources to him/her).\par For our resource allocation problems, we give an algorithmic characterization of the solutions for which truth-telling is a Nash equilibrium. A natural application of these results is to a scheduling/routing problem which is the mechanism design counterpart of the selfish routing game of Koutsoupias and Papadimitriou [1999]: Each selfish user wants to route a piece of unsplittable traffic using one of $m$ links of different speeds so as to minimize his/her own latency. Our mechanism design counterpart can be seen as the problem of scheduling selfish jobs on parallel related machines and is the dual of the problem of scheduling (unselfish) jobs on parallel selfish machines studied by Archer and Tardos [2001].\par Koutsoupias and Papadimitriou studied an ``anarchic'' scenario in which each user chooses his/her own link, and this may produce Nash equilibria of cost $\Omega(\log m / \log \log m)$ times the optimum. Our mechanism design counterpart is a possible way of reducing the effect of selfish behavior via suitable incentives to the agents (i.e., taxes for using the links). We indeed show that in the resulting game, it is possible to guarantee an approximation factor of 8 for any number of links/machines (this solution also works for online settings). However, it remains impossible to guarantee arbitrarily good approximate solutions, even for 2 links/machines and even if the allocation algorithm is allowed superpolynomial time. This result shows that our scheduling problem with selfish jobs is more difficult than the scheduling problem with selfish machines by Archer and Tardos (which admits exact solutions).\par We also study some generalizations of this basic problem.", acknowledgement = ack-nhfb, articleno = "52", keywords = "Algorithmic mechanism design; Nash equilibrium; scheduling; selfish routing", } @Article{Ruzic:2008:UDD, author = "Milan Ru{\v{z}}i{\'c}", title = "Uniform deterministic dictionaries", journal = j-TALG, volume = "4", number = "1", pages = "1:1--1:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328912", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting ``good'' hash functions. The main motivation is realization of deterministic dictionaries with fast lookups and reasonably fast updates. The model of computation is the Word RAM, and it is assumed that the machine word-size matches the size of keys in bits. Many of the modern solutions to the dictionary problem are weakly nonuniform, that is, they require a number of constants to be computed at ``compile time'' for the stated time bounds to hold. The currently fastest deterministic dictionary uses constants not known to be computable in polynomial time. In contrast, our dictionaries do not require any special constants or instructions, and running times are independent of word (and key) length. Our family of dynamic dictionaries achieves a performance of the following type: lookups in time $O(t)$ and updates in amortized time $O(n^{1/t})$, for an appropriate parameter function $t$. Update procedures require division, whereas searching uses multiplication only.", acknowledgement = ack-nhfb, articleno = "1", keywords = "Deterministic algorithms; perfect hashing", } @Article{Franceschini:2008:NSB, author = "Gianni Franceschini and Roberto Grossi", title = "No sorting? better searching!", journal = j-TALG, volume = "4", number = "1", pages = "2:1--2:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328913", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Questions about order versus disorder in systems and models have been fascinating scientists over the years. In computer science, order is intimately related to sorting, commonly meant as the task of arranging keys in increasing or decreasing order with respect to an underlying total order relation. The sorted organization is amenable for searching a set of n keys, since each search requires $\Theta(\log n)$ comparisons in the worst case, which is optimal if the cost of a single comparison can be considered a constant. Nevertheless, we prove that disorder implicitly provides more information than order does. For the general case of searching an array of multidimensional keys whose comparison cost is proportional to their length (and hence which cannot be considered a constant), we demonstrate that ``suitable'' disorder gives better bounds than those derivable by using the natural lexicographic order.\par We start from previous work done by Andersson et al. [2001], who proved that $\Theta(k \log \log n / \log \log(4 + k \log \log n / \log n) + k + \log n)$ character comparisons (or probes) comprise the tight complexity for searching a plain sorted array of $n$ keys, each of length $k$, arranged in lexicographic order. We describe a novel permutation of the n keys that is different from the sorted order. When keys are kept ``unsorted'' in the array according to this permutation, the complexity of searching drops to $\Theta(k + \log n)$ character comparisons (or probes) in the worst case, which is optimal among all possible permutations, up to a constant factor. Consequently, disorder carries more information than does order; this fact was not observable before, since the latter two bounds are $\Theta(\log n)$ when $k = O(1)$. More implications are discussed in the article, including searching in the bit-probe model.", acknowledgement = ack-nhfb, articleno = "2", keywords = "Implicit data structures; in-place algorithms; searching; sorting", } @Article{Kaplan:2008:THT, author = "Haim Kaplan and Robert Endre Tarjan", title = "Thin heaps, thick heaps", journal = j-TALG, volume = "4", number = "1", pages = "3:1--3:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328914", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asymptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of H{\o}yer [1995], we describe three heap implementations (two versions of thin heaps and one of thick heaps) that have the same amortized efficiency as Fibonacci heaps, but need less space and promise better practical performance. As part of our development, we fill in a gap in H{\o}yer's analysis.", acknowledgement = ack-nhfb, articleno = "3", keywords = "binomial queue; Data structure; decrease key operation; Fibonacci heap; heap; melding; priority queue; thick heap; thin heap", } @Article{Barbay:2008:ARA, author = "J{\'e}r{\'e}my Barbay and Claire Kenyon", title = "Alternation and redundancy analysis of the intersection problem", journal = j-TALG, volume = "4", number = "1", pages = "4:1--4:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328915", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "The intersection of sorted arrays problem has applications in search engines such as Google. Previous work has proposed and compared deterministic algorithms for this problem, in an adaptive analysis based on the encoding size of a certificate of the result (cost analysis). We define the alternation analysis, based on the nondeterministic complexity of an instance. In this analysis we prove that there is a deterministic algorithm asymptotically performing as well as any randomized algorithm in the comparison model. We define the redundancy analysis, based on a measure of the internal redundancy of the instance. In this analysis we prove that any algorithm optimal in the redundancy analysis is optimal in the alternation analysis, but that there is a randomized algorithm which performs strictly better than any deterministic algorithm in the comparison model. Finally, we describe how these results can be extended beyond the comparison model.", acknowledgement = ack-nhfb, articleno = "4", keywords = "Adaptive analysis; alternation analysis; intersection; intersection of sorted arrays; randomized algorithm; redundancy analysis", } @Article{Pettie:2008:RMS, author = "Seth Pettie and Vijaya Ramachandran", title = "Randomized minimum spanning tree algorithms using exponentially fewer random bits", journal = j-TALG, volume = "4", number = "1", pages = "5:1--5:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328916", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the MST sensitivity analysis problem, the parallel connected components and parallel minimum spanning tree problems, and the local sorting and set maxima problems. (For the first two problems there are provably optimal deterministic algorithms with unknown, and possibly superlinear, running times.) One downside of the randomized methods for solving these problems is that they use a number of random bits linear in the size of input. In this article we develop some general methods for reducing exponentially the consumption of random bits in comparison-based algorithms. In some cases we are able to reduce the number of random bits from linear to nearly constant, without affecting the expected running time.\par Most of our results are obtained by adjusting or reorganizing existing randomized algorithms to work well with a pairwise or $O(1)$-wise independent sampler. The prominent exception, and the main focus of this article, is a linear-time randomized minimum spanning tree algorithm that is not derived from the well-known Karger-Klein-Tarjan algorithm. In many ways it resembles more closely the deterministic minimum spanning tree algorithms based on soft heaps. Further, using our algorithm as a guide, we present a unified view of the existing ``nongreedy'' minimum spanning tree algorithms. Concepts from the Karger-Klein-Tarjan algorithm, such as F-lightness, MST verification, and sampled graphs, are related to the concepts of edge corruption, subgraph contractibility, and soft heaps, which are the basis of the deterministic MST algorithms of Chazelle and Pettie-Ramachandran.", acknowledgement = ack-nhfb, articleno = "5", keywords = "Graph algorithms; minimum spanning trees; random sampling", } @Article{Roditty:2008:FSF, author = "Liam Roditty", title = "A faster and simpler fully dynamic transitive closure", journal = j-TALG, volume = "4", number = "1", pages = "6:1--6:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328917", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We obtain a new fully dynamic algorithm for maintaining the transitive closure of a directed graph. Our algorithm maintains the transitive closure matrix in a total running time of $O(mn +({\rm ins} + {\rm del}) {\cdot} n^2)$, where ins(del) is the number of insert (delete) operations performed. Here $n$ is the number of vertices in the graph and $m$ is the initial number of edges in the graph. Obviously, reachability queries can be answered in constant time. The algorithm uses only $O(n^2)$ time which is essentially optimal for maintaining the transitive closure matrix. Our algorithm can also support path queries. If $v$ is reachable from $u$, the algorithm can produce a path from $u$ to $v$ in time proportional to the length of the path. The best previously known algorithm for the problem is due to Demetrescu and Italiano [2000]. Their algorithm has a total running time of $O(n^3 +({\rm ins} + {\rm del}) {\cdot} n^2)$. The query time is also constant. In addition, we also present a simple algorithm for directed acyclic graphs (DAGs) with a total running time of $O(mn + {\rm ins} {\cdot} n^2 + {\rm del})$. Our algorithms are obtained by combining some new ideas with techniques of Italiano [1986, 1988], King [1999], King and Thorup [2001] and Frigioni et al. [2001]. We also note that our algorithms are extremely simple and can be easily implemented.", acknowledgement = ack-nhfb, articleno = "6", keywords = "directed graph; Dynamic graph algorithms; reachability", } @Article{Gabow:2008:FLD, author = "Harold N. Gabow and Shuxin Nie", title = "Finding a long directed cycle", journal = j-TALG, volume = "4", number = "1", pages = "7:1--7:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328918", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Consider a digraph with n vertices. For any fixed value k, we present linear- and almost-linear-time algorithms to find a cycle of length $\geq k$, if one exists. We also find a cycle that has length $\geq \log n / \log \log n$ in polynomial time, if one exists. Under an appropriate complexity assumption it is known to be impossible to improve this guarantee by more than a $\log \log n$ factor. Our approach is based on depth-first search.", acknowledgement = ack-nhfb, articleno = "7", keywords = "Approximation algorithms; circumference; cycles; Hamiltonian cycles; long cycles", } @Article{Buchsbaum:2008:RLC, author = "Adam L. Buchsbaum and Emden R. Gansner and Cecilia M. Procopiuc and Suresh Venkatasubramanian", title = "Rectangular layouts and contact graphs", journal = j-TALG, volume = "4", number = "1", pages = "8:1--8:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328919", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding rectangular layouts is a key problem. We study the area-optimization problem and show that it is NP-hard to find a minimum-area rectangular layout of a given contact graph. We present $O(n)$-time algorithms that construct $O(n^2)$-area rectangular layouts for general contact graphs and $O(n \log n)$-area rectangular layouts for trees. (For trees, this is an $O(\log n)$-approximation algorithm.) We also present an infinite family of graphs (respectively, trees) that require $\Omega(n^2)$ (respectively, $\Omega(n \log n))$ area.\par We derive these results by presenting a new characterization of graphs that admit rectangular layouts, using the related concept of rectangular duals. A corollary to our results relates the class of graphs that admit rectangular layouts to rectangle-of-influence drawings.", acknowledgement = ack-nhfb, articleno = "8", keywords = "Contact graphs; rectangular duals; rectangular layouts", } @Article{Arge:2008:PRT, author = "Lars Arge and Mark De Berg and Herman Haverkort and Ke Yi", title = "The priority {R-tree}: {A} practically efficient and worst-case optimal {R-tree}", journal = j-TALG, volume = "4", number = "1", pages = "9:1--9:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328920", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We present the priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using $O((N / B) 1 - 1/ d + T / B)$ I/Os, where $N$ is the number of $d$-dimensional (hyper-) rectangles stored in the R-tree, $B$ is the disk block size, and $T$ is the output size. This is provably asymptotically optimal and significantly better than other R-tree variants, where a query may visit all $N / B$ leaves in the tree even when $T = 0$. We also present an extensive experimental study of the practical performance of the PR-tree using both real-life and synthetic data. This study shows that the PR-tree performs similarly to the best-known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.", acknowledgement = ack-nhfb, articleno = "9", keywords = "R-trees", } @Article{Gudmundsson:2008:ADO, author = "Joachim Gudmundsson and Christos Levcopoulos and Giri Narasimhan and Michiel Smid", title = "Approximate distance oracles for geometric spanners", journal = j-TALG, volume = "4", number = "1", pages = "10:1--10:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328921", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Given an arbitrary real constant $\varepsilon > 0$, and a geometric graph $G$ in $d$-dimensional Euclidean space with $n$ points, $O(n)$ edges, and constant dilation, our main result is a data structure that answers $(1 + \varepsilon)$-approximate shortest-path-length queries in constant time. The data structure can be constructed in $O(n \log n)$ time using $O(n \log n)$ space. This represents the first data structure that answers $(1 + \varepsilon)$-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with ``rounded'' obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer $(1 + \varepsilon)$-approximate shortest-path-length queries in constant time for geometric spanner graphs with $m = \omega(n)$ edges. The resulting data structure can be constructed in $O(m + n \log n)$ time using $O(n \log n)$ space.", acknowledgement = ack-nhfb, articleno = "10", keywords = "approximation algorithm; computational geometry; geometric graphs; Shortest paths; spanners", } @Article{Gandhi:2008:IBS, author = "Rajiv Gandhi and Magn{\'u}s M. Halld{\'o}rsson and Guy Kortsarz and Hadas Shachnai", title = "Improved bounds for scheduling conflicting jobs with minsum criteria", journal = j-TALG, volume = "4", number = "1", pages = "11:1--11:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328922", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider a general class of scheduling problems where a set of conflicting jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. The conflicts among jobs are formed as an arbitrary conflict graph.\par Building on the framework of Queyranne and Sviridenko [2002b], we present a general technique for reducing the weighted sum of completion-times problem to the classical makespan minimization problem. Using this technique, we improve the best-known results for scheduling conflicting jobs with the min-sum objective, on several fundamental classes of graphs, including line graphs, $(k + 1)$-claw-free graphs, and perfect graphs. In particular, we obtain the first constant-factor approximation ratio for nonpreemptive scheduling on interval graphs. We also improve the results of Kim [2003] for scheduling jobs on line graphs and for resource-constrained scheduling.", acknowledgement = ack-nhfb, articleno = "11", keywords = "Approximation algorithms; coloring; linear programming; LP rounding; scheduling; sum multicoloring", } @Article{Guerraoui:2008:CMA, author = "Rachid Guerraoui and Ron R. Levy and Bastian Pochon and Jim Pugh", title = "The collective memory of amnesic processes", journal = j-TALG, volume = "4", number = "1", pages = "12:1--12:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328923", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "This article considers the problem of robustly emulating a shared atomic memory over a distributed message-passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context and introduce a generic algorithm that emulates an atomic memory. The algorithm is instantiated for various settings according to whether processes have access to local stable storage, and whether, in every execution of the algorithm, a sufficient number of processes are assumed not to crash. We establish the optimality of specific instances of our algorithm in terms of resilience, log complexity (number of stable storage accesses needed in every read or write operation), as well as time complexity (number of communication steps needed in every read or write operation). The article also discusses the impact of considering a multiwriter versus a single-writer memory, as well as the impact of weakening the consistency of the memory by providing safe or regular semantics instead of atomicity.", acknowledgement = ack-nhfb, articleno = "12", keywords = "Atomic registers; crash recovery; \log complexity; shared-memory emulation", } @Article{Karakostas:2008:FAS, author = "George Karakostas", title = "Faster approximation schemes for fractional multicommodity flow problems", journal = j-TALG, volume = "4", number = "1", pages = "13:1--13:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328924", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k. We show that by modifying the algorithms by Garg and K{\"o}nemann [1998] and Fleischer [2000], we can reduce their running time on a graph with n vertices and m edges from $\tilde{O}(\varepsilon - 2(m^2 + km))$ to $\tilde{O}(\varepsilon - 2 m^2)$ for an implicit representation of the output, or $\tilde{O}(\varepsilon 2(m^2 + kn))$ for an explicit representation, where $\tilde{O}(f)$ denotes a quantity that is $O(f \log O(1) m)$. The implicit representation consists of a set of trees rooted at sources (there can be more than one tree per source), and with sinks as their leaves, together with flow values for the flow directed from the source to the sinks in a particular tree. Given this implicit representation, the approximate value of the concurrent flow is known, but if we want the explicit flow per commodity per edge, we would have to combine all these trees together, and the cost of doing so may be prohibitive. In case we want to calculate explicitly the solution flow, we modify our schemes so that they run in time polylogarithmic in nk(n is the number of nodes in the network). This is within a polylogarithmic factor of the trivial lower bound of time $\Omega(nk)$ needed to explicitly write down a multicommodity flow of $k$ commodities in a network of $n$ nodes. Therefore our schemes are within a polylogarithmic factor of the minimum possible dependencies of the running time on the number of commodities $k$.", acknowledgement = ack-nhfb, articleno = "13", keywords = "fully-polynomial time approximation schemes; Multicommodity flows", } @Article{Lemire:2008:HBO, author = "Daniel Lemire and Owen Kaser", title = "Hierarchical bin buffering: {Online} local moments for dynamic external memory arrays", journal = j-TALG, volume = "4", number = "1", pages = "14:1--14:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328925", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "For a massive I/O array of size n, we want to compute the first $N$ local moments, for some constant $N$. Our simpler algorithms partition the array into consecutive ranges called bins, and apply not only to local-moment queries, but also to algebraic queries. With $N$ buffers of size $\sqrt{n}$, time complexity drops to $O(\sqrt{n})$. A more sophisticated approach uses hierarchical buffering and has a logarithmic time complexity ($O(b \log b n)$), when using $N$ hierarchical buffers of size $n / b$. Using overlapped bin buffering, we show that only one buffer is needed, as with wavelet-based algorithms, but using much less storage.", acknowledgement = ack-nhfb, articleno = "14", keywords = "hierarchical buffers; polynomial fitting; statistical queries; Very large arrays", } @Article{Anshelevich:2008:PDU, author = "Elliot Anshelevich and Lisa Zhang", title = "Path decomposition under a new cost measure with applications to optical network design", journal = j-TALG, volume = "4", number = "1", pages = "15:1--15:??", month = mar, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1328911.1328926", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:15 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We introduce a problem directly inspired by its application to DWDM (dense wavelength division multiplexing) network design. We are given a set of demands to be carried over a network. Our goal is to choose a route for each demand and to decompose the network into a collection of edge-disjoint simple paths. These paths are called optical line systems. The cost of routing one unit of demand is the number of line systems with which the demand route overlaps; our design objective is to minimize the total cost over all demands. This cost metric is motivated by the need to minimize O-E-O (optical-electrical-optical) conversions in optical transmission.\par For given line systems, it is easy to find the optimal demand routes. On the other hand, for given demand routes designing the optimal line systems can be NP-hard. We first present a 2-approximation for general network topologies. As optical networks often have low node degrees, we offer an algorithm that finds the optimal solution for the special case in which the node degree is at most 3. Our solution is based on a local greedy approach.\par If neither demand routes nor line systems are fixed, the situation becomes much harder. Even for a restricted scenario on a 3-regular Hamiltonian network, no efficient algorithm can guarantee a constant approximation better than 2. For general topologies, we offer a simple algorithm with an $O(\log K)$- and an $O(\log n)$-approximation, where $K$ is the number of demands and $n$ the number of nodes. This approximation ratio is almost tight. For rings, a common special topology, we offer a more complex 3/2-approximation algorithm.", acknowledgement = ack-nhfb, articleno = "15", keywords = "approximation algorithms; Optical network design; path decomposition", } @Article{Buchsbaum:2008:GE, author = "Adam L. Buchsbaum", title = "Guest editorial", journal = j-TALG, volume = "4", number = "2", pages = "16:1--16:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361193", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", acknowledgement = ack-nhfb, articleno = "16", } @Article{Blandford:2008:CDV, author = "Daniel K. Blandford and Guy E. Blelloch", title = "Compact dictionaries for variable-length keys and data with applications", journal = j-TALG, volume = "4", number = "2", pages = "17:1--17:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361194", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We consider the problem of maintaining a dynamic dictionary $T$ of keys and associated data for which both the keys and data are bit strings that can vary in length from zero up to the length w of a machine word. We present a data structure for this variable-bit-length dictionary problem that supports constant time lookup and expected amortized constant-time insertion and deletion. It uses $O(m + 3 n - n \log 2 n)$ bits, where $n$ is the number of elements in $T$, and $m$ is the total number of bits across all strings in $T$ (keys and data). Our dictionary uses an array $A[1 \ldots n]$ in which locations store variable-bit-length strings. We present a data structure for this variable-bit-length array problem that supports worst-case constant-time lookups and updates and uses $O(m + n)$ bits, where $m$ is the total number of bits across all strings stored in $A$.\par The motivation for these structures is to support applications for which it is helpful to efficiently store short varying-length bit strings. We present several applications, including representations for semidynamic graphs, order queries on integers sets, cardinal trees with varying cardinality, and simplicial meshes of $d$ dimensions. These results either generalize or simplify previous results.", acknowledgement = ack-nhfb, articleno = "17", keywords = "Compression", } @Article{Kolluri:2008:PGM, author = "Ravikrishna Kolluri", title = "Provably good moving least squares", journal = j-TALG, volume = "4", number = "2", pages = "18:1--18:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361195", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We analyze a moving least squares (MLS) interpolation scheme for reconstructing a surface from point cloud data. The input is a sufficiently dense set of sample points that lie near a closed surface F with approximate surface normals. The output is a reconstructed surface passing near the sample points. For each sample point $s$ in the input, we define a linear point function that represents the local shape of the surface near $s$. These point functions are combined by a weighted average, yielding a three-dimensional function $I$. The reconstructed surface is implicitly defined as the zero set of $I$.\par We prove that the function $I$ is a good approximation to the signed distance function of the sampled surface $F$ and that the reconstructed surface is geometrically close to and isotopic to $F$. Our sampling requirements are derived from the local feature size function used in Delaunay-based surface reconstruction algorithms. Our analysis can handle noisy data provided the amount of noise in the input dataset is small compared to the feature size of $F$.", acknowledgement = ack-nhfb, articleno = "18", keywords = "implicit surfaces; interpolation; Reconstruction", } @Article{Fusy:2008:DOT, author = "{\'E}ric Fusy and Gilles Schaeffer and Dominique Poulalhon", title = "Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling", journal = j-TALG, volume = "4", number = "2", pages = "19:1--19:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361196", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees with interesting consequences for enumeration, mesh compression, and graph sampling. Our bijection yields an efficient uniform random sampler for 3-connected planar graphs, which turns out to be determinant for the quadratic complexity of the current best-known uniform random sampler for labelled planar graphs. It also provides an encoding for the set $P(n)$ of $n$-edge 3-connected planar graphs that matches the entropy bound $1/ n \log 2 | P(n)| = 2 + o (1)$ bits per edge (bpe). This solves a theoretical problem recently raised in mesh compression as these graphs abstract the combinatorial part of meshes with spherical topology. We also achieve the optimal parametric rate $1 / n \log 2 | P(n, i, j)|$ bpe for graphs of $P(n)$ with $i$ vertices and $j$ faces, matching in particular the optimal rate for triangulations. Our encoding relies on a linear time algorithm to compute an orientation associated with the minimal Schnyder wood of a 3-connected planar map. This algorithm is of independent interest, and it is, for instance, a key ingredient in a recent straight line drawing algorithm for 3-connected planar graphs.", acknowledgement = ack-nhfb, articleno = "19", keywords = "Bijection; coding; counting; random generation", } @Article{VeghVegh:2008:PDA, author = "L{\'a}szl{\'o} A. V{\'e}ghV{\'e}gh and Andr{\'a}s A. Bencz{\'u}r", title = "Primal-dual approach for directed vertex connectivity augmentation and generalizations", journal = j-TALG, volume = "4", number = "2", pages = "20:1--20:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361197", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "In their seminal paper, Frank and Jord{\'a}n [1995] show that a large class of optimization problems, including certain directed graph augmentation, fall into the class of covering supermodular functions over pairs of sets. They also give an algorithm for such problems, however, it relies on the ellipsoid method. Prior to our result, combinatorial algorithms existed only for the 0--1 valued problem. Our key result is a combinatorial algorithm for the general problem that includes directed vertex or S-T connectivity augmentation. The algorithm is based on Bencz{\'u}r's previous algorithm for the 0--1 valued case [Bencz{\'u}r 2003].\par Our algorithm uses a primal-dual scheme for finding covers of partially ordered sets that satisfy natural abstract properties as in Frank and Jord{\'a}n. For an initial (possibly greedy) cover, the algorithm searches for witnesses for the necessity of each element in the cover. If no two (weighted) witnesses have a common cover, the solution is optimal. As long as this is not the case, the witnesses are gradually exchanged for smaller ones. Each witness change defines an appropriate change in the solution; these changes are finally unwound in a shortest-path manner to obtain a solution of size one less.", acknowledgement = ack-nhfb, articleno = "20", keywords = "combinatorial algorithm; Vertex connectivity augmentation", } @Article{Sanders:2008:AAS, author = "Peter Sanders and David Steurer", title = "An asymptotic approximation scheme for multigraph edge coloring", journal = j-TALG, volume = "4", number = "2", pages = "21:1--21:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361198", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "The edge coloring problem considers the assignment of colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge coloring of multigraphs, that is, parallel edges are allowed. The best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. One of our algorithms achieves solution quality ${\rm opt} + \sqrt{9 {\rm opt}/2}$ and has execution time polynomial in the number of nodes and the logarithm of the maximum edge multiplicity.", acknowledgement = ack-nhfb, articleno = "21", keywords = "chromatic index; data migration; Edge coloring; multigraphs", } @Article{Chawla:2008:ENT, author = "Shuchi Chawla and Anupam Gupta and Harald R{\"a}cke", title = "Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut", journal = j-TALG, volume = "4", number = "2", pages = "22:1--22:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361199", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "In this article, we study metrics of negative type, which are metrics $(V, d)$ such that $\sqrt{d}$ is an Euclidean metric; these metrics are thus also known as $\ell_2$-squared metrics. We show how to embed $n$-point negative-type metrics into Euclidean space $\ell_2$ with distortion $D = O(\log 3/4 n)$. This embedding result, in turn, implies an $O(\log 3/4 k)$-approximation algorithm for the Sparsest Cut problem with nonuniform demands. Another corollary we obtain is that $n$-point subsets of $\ell_1$ embed into $\ell_2$ with distortion $O(\log 3/4 n)$.", acknowledgement = ack-nhfb, articleno = "22", keywords = "Approximation algorithm; embedding; metrics; negative-type metric; sparsest cut", } @Article{Chuzhoy:2008:ASN, author = "Julia Chuzhoy and Anupam Gupta and Joseph (Seffi) Naor and Amitabh Sinha", title = "On the approximability of some network design problems", journal = j-TALG, volume = "4", number = "2", pages = "23:1--23:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361200", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "Consider the following classical network design problem: a set of terminals $T = \{ t_i \}$ wishes to send traffic to a root $r$ in an $n$-node graph $G =(V, E)$. Each terminal $t_i$ sends $d_i$ units of traffic and enough bandwidth has to be allocated on the edges to permit this. However, bandwidth on an edge e can only be allocated in integral multiples of some base capacity $u_e$ and hence provisioning $k {\times} u_e$ bandwidth on edge $e$ incurs a cost of $\lceil k \rceil$ times the cost of that edge. The objective is a minimum-cost feasible solution.\par This is one of many network design problems widely studied where the bandwidth allocation is governed by side constraints: edges can only allow a subset of cables to be purchased on them or certain quality-of-service requirements may have to be met.\par In this work, we show that this problem and, in fact, several basic problems in this general network design framework cannot be approximated better than $\Omega(\log \log n)$ unless ${\rm NP} \subseteq {\rm DTIME}(n O(\log \log \log n))$, where $|V| = n$. In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem, (ii) the (single-sink) Cost-Distance problem, and (iii) the single-sink version of an even more fundamental problem, Fixed Charge Network Flow. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first nonconstant hardness results known for all these problems.", acknowledgement = ack-nhfb, articleno = "23", keywords = "cost-distance; fixed charge network flow; Hardness of approximation; network design; priority Steiner tree", } @Article{Immorlica:2008:LCM, author = "Nicole Immorlica and Mohammad Mahdian and Vahab S. Mirrokni", title = "Limitations of cross-monotonic cost-sharing schemes", journal = j-TALG, volume = "4", number = "2", pages = "24:1--24:??", month = may, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1361192.1361201", ISSN = "1549-6325", bibdate = "Mon Jun 16 11:56:51 MDT 2008", bibsource = "http://portal.acm.org/", abstract = "A cost-sharing scheme is a set of rules defining how to share the cost of a service (often computed by solving a combinatorial optimization problem) among serviced customers. A cost-sharing scheme is cross-monotonic if it satisfies the property that everyone is better off when the set of people who receive the service expands. In this article, we develop a novel technique for proving upper bounds on the budget-balance factor of cross-monotonic cost-sharing schemes or the worst-case ratio of recovered cost to total cost. We apply this technique to games defined, based on several combinatorial optimization problems, including the problems of edge cover, vertex cover, set cover, and metric facility location and, in each case, derive tight or nearly-tight bounds. In particular, we show that for the facility location game, there is no cross-monotonic cost-sharing scheme that recovers more than a third of the total cost. This result, together with a recent 1/3-budget-balanced cross-monotonic cost-sharing scheme of P{\'a}l and Tardos [2003] closes the gap for the facility location game. For the vertex cover and set cover games, we show that no cross-monotonic cost-sharing scheme can recover more than a $O(n - 1/3)$ and $O(1 / n)$ fraction of the total cost, respectively. Finally, we study the implications of our results on the existence of group-strategyproof mechanisms. We show that every group-strategyproof mechanism corresponds to a cost-sharing scheme that satisfies a condition weaker than cross-monotonicity. Using this, we prove that group-strategyproof mechanisms satisfying additional properties give rise to cross-monotonic cost-sharing schemes and therefore our upper bounds hold.", acknowledgement = ack-nhfb, articleno = "24", keywords = "Cross-monotonic cost-sharing schemes; group-strategyproof mechanism design; probabilistic method", } @Article{Dinitz:2008:OAS, author = "Yefim Dinitz and Shay Solomon", title = "Optimality of an algorithm solving the {Bottleneck Tower of Hanoi} problem", journal = j-TALG, volume = "4", number = "3", pages = "25:1--25:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367065", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We study the Bottleneck Tower of Hanoi puzzle posed by D. Wood in 1981. There, a relaxed placement rule allows a larger disk to be placed {\em higher\/} than a smaller one if their size difference is less than a pregiven value $k$. A shortest sequence of moves (optimal algorithm) transferring all the disks placed on some peg in decreasing order of size, to another peg in the same order is in question. In 1992, D. Poole suggested a natural disk-moving strategy for this problem, and computed the length of the shortest move sequence under its framework. However, other strategies were overlooked, so the lower bound/optimality question remained open. In 1998, Benditkis, Berend, and Safro proved the optimality of Poole's algorithm for the first nontrivial case $k = 2$. We prove Poole's algorithm to be optimal in the general case.", acknowledgement = ack-nhfb, articleno = "25", keywords = "Optimality proofs; Tower of Hanoi", } @Article{Alonso:2008:DP, author = "Laurent Alonso and Edward M. Reingold", title = "Determining plurality", journal = j-TALG, volume = "4", number = "3", pages = "26:1--26:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367066", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Given a set of $n$ elements, each of which is colored one of $c$ colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that $(c - 1)(n - c)/2$ color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring $(0.775 c + 5.9) n + O(c^2)$ color comparisons for $c \geq 9$.", acknowledgement = ack-nhfb, articleno = "26", keywords = "Algorithm analysis; majority problem; plurality problem", } @Article{Alonso:2008:ACL, author = "Laurent Alonso and Edward M. Reingold", title = "Average-case lower bounds for the plurality problem", journal = j-TALG, volume = "4", number = "3", pages = "27:1--27:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367067", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Given a set of $n$ elements, each of which is colored one of $c \geq 2$ colors, we have to determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We derive lower bounds for the expected number of color comparisons when the $c^n$ colorings are equally probable. We prove a general lower bound of $c / 3 n - O(\sqrt n)$ for $c \geq 2$; we prove the stronger particular bounds of $7/6 n - O(\sqrt n)$ for $c = 3$, $54/35 n - O(\sqrt n)$ for $c = 4$, $607/315 n O(\sqrt n)$ for $c = 5$, $1592/693 n - O(\sqrt n)$ for $c = 6$, $7985/3003 n - O(\sqrt n)$ for $c = 7$, and $19402/6435 n - O(\sqrt n)$ for $c = 8$.", acknowledgement = ack-nhfb, articleno = "27", keywords = "Algorithm analysis; majority problem; plurality problem", } @Article{Lu:2008:BPS, author = "Hsueh-I Lu and Chia-Chi Yeh", title = "Balanced parentheses strike back", journal = j-TALG, volume = "4", number = "3", pages = "28:1--28:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367068", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "An {\em ordinal tree\/} is an arbitrary rooted tree where the children of each node are ordered. Succinct representations for ordinal trees with efficient query support have been extensively studied. The best previously known result is due to Geary et al. [2004b, pages 1--10]. The number of bits required by their representation for an $n$-node ordinal tree $T$ is $2 n + o(n)$, whose first-order term is information-theoretically optimal. Their representation supports a large set of $O(1)$-time queries on $T$. Based upon a balanced string of $2 n$ parentheses, we give an improved $2 n + o(n)$-bit representation for $T$. Our improvement is two-fold: First, the set of $O(1)$-time queries supported by our representation is a proper superset of that supported by the representation of Geary, Raman, and Raman. Second, it is also much easier for our representation to support new queries by simply adding new auxiliary strings.", acknowledgement = ack-nhfb, articleno = "28", keywords = "Succinct data structures; XML document representation", } @Article{Roditty:2008:RSR, author = "Iam Roditty and Mikkel Thorup and Uri Zwick", title = "Roundtrip spanners and roundtrip routing in directed graphs", journal = j-TALG, volume = "4", number = "3", pages = "29:1--29:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367069", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We introduce the notion of {\em roundtrip-spanners\/} of weighted {\em directed\/} graphs and describe efficient algorithms for their construction. We show that for every integer $k \geq 1$ and any $\epsilon > 0$, any directed graph on $n$ vertices with edge weights in the range $[1, W]$ has a $(2 k + \epsilon)$-roundtrip-spanner with $O(\min(k^2 /\epsilon)) n^{1 + 1/ k} (\log(nW), (k /\epsilon)^2 n^{1 + 1/ k} ,(log n)^{2-1/k})$ edges. We then extend these constructions and obtain compact roundtrip routing schemes. For every integer $k$ \geq 1 and every $\epsilon > 0$, we describe a roundtrip routing scheme that has stretch $4 k + \epsilon$ , and uses at each vertex a routing table of size $\Otilde((k^2 / \epsilon) n^{1/k} \log(nW))$. We also show that any weighted directed graph with {\em arbitrary/\/} positive edge weights has a 3-roundtrip-spanner with $O(n^{3/2})$ edges. This result is optimal. Finally, we present a stretch 3 roundtrip routing scheme that uses local routing tables of size $\Otilde(n^{1/2})$. This routing scheme is essentially optimal. The roundtrip-spanner constructions and the roundtrip routing schemes for directed graphs that we describe are only slightly worse than the best available spanners and routing schemes for undirected graphs. Our roundtrip routing schemes substantially improve previous results of Cowen and Wagner. Our results are obtained by combining ideas of Cohen, Cowen and Wagner, Thorup and Zwick, with some new ideas.", acknowledgement = ack-nhfb, articleno = "29", keywords = "distances; roundtrip; Routing; shortest paths; spanners", } @Article{Gu:2008:OBD, author = "Qian-Ping Gu and Hisao Tamaki", title = "Optimal branch-decomposition of planar graphs in {$O(n^3)$} time", journal = j-TALG, volume = "4", number = "3", pages = "30:1--30:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367070", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We give an $O(n^3)$ time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with $n$ vertices. This is achieved through a refinement to the previously best known algorithm of Seymour and Thomas, which runs in $O(n^4)$ time.", acknowledgement = ack-nhfb, articleno = "30", keywords = "Branch-decompositions; planar graphs", } @Article{Czumaj:2008:TEM, author = "Artur Czumaj and Christian Sohler", title = "Testing {Euclidean} minimum spanning trees in the plane", journal = j-TALG, volume = "4", number = "3", pages = "31:1--31:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367071", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Given a Euclidean graph $G$ over a set $P$ of $n$ points in the plane, we are interested in verifying whether $G$ is a Euclidean minimum spanning tree (EMST) of $P$ or $G$ differs from it in more than $\epsilon n$ edges. We assume that $G$ is given in adjacency list representation and the point/vertex set $P$ is given in an array. We present a property testing algorithm that accepts graph $G$ if it is an EMST of $P$ and that rejects with probability at least $2/3$ if $G$ differs from every EMST of $P$ in more than $\epsilon, n$ edges. Our algorithm runs in $O(\sqrt n / \epsilon \cdot \log^2(n / \epsilon))$ time and has a query complexity of $O(\sqrt n / \epsilon \cdot \log(n / \epsilon))$.", acknowledgement = ack-nhfb, articleno = "31", keywords = "Euclidean minimum spanning tree; property testing; randomized algorithms", } @Article{Makinen:2008:DEC, author = "Veli M{\"a}kinen and Gonzalo Navarro", title = "Dynamic entropy-compressed sequences and full-text indexes", journal = j-TALG, volume = "4", number = "3", pages = "32:1--32:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367072", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We give new solutions to the Searchable Partial Sums with Indels problem. Given a sequence of $n$ $k$-bit numbers, we present a structure taking $kn + o(kn)$ bits of space, able of performing operations {\em sum}, {\em search}, {\em insert}, and {\em delete}, all in $O(\log n)$ worst-case time, for any $k = O(\log n)$. This extends previous results by Hon et al. [2003c] achieving the same space and $O (\log n / \log \log n)$ time complexities for the queries, yet offering complexities for {\em insert\/} and {\em delete\/} that are amortized and worse than ours, and supported only for $k = O(1)$. Our result matches an existing lower bound for large values of $k$.\par We also give new solutions to the Dynamic Sequence problem. Given a sequence of $n$ symbols in the range $[1,\sigma]$ with binary zero-order entropy $H_0$, we present a dynamic data structure that requires $n_0 + o(n \log \sigma)$ bits of space, which is able of performing {\em rank\/} and {\em select}, as well as inserting and deleting symbols at arbitrary positions, in $O(\log n log \sigma)$ time. Our result is the {\em first\/} entropy-bound dynamic data structure for {\em rank\/} and {\em select\/} over general sequences.\par In the case $\sigma = 2$, where both previous problems coincide, we improve the dynamic solution of Hon et al. [2003c] in that we compress the sequence. The only previous result with entropy-bound space for dynamic binary sequences is by Blandford and Blelloch [2004], which has the same complexities as our structure, but does not achieve constant 1 multiplying the entropy term in the space complexity.\par Finally, we present a new dynamic compressed full-text self-index, for a collection of texts over an alphabet of size {\sigma}, of overall length $n$ and $h$th order empirical entropy $H_h$. The index requires $nH_h + o(n \log \sigma)$ bits of space, for any $h \leq \alpha \log_\sigma n$ and constant $0$.\par An important result we prove in this paper is that the wavelet tree of the Burrows-Wheeler transform of a text, if compressed with a technique that achieves zero-order compression locally (e.g., Raman et al. [2002]), automatically achieves $h$th order entropy space for any $h$. This unforeseen relation is essential for the results of the previous paragraph, but it also derives into significant simplifications on many existing static compressed full-text self-indexes that build on wavelet trees.", acknowledgement = ack-nhfb, articleno = "32", keywords = "Compressed dynamic data structures; compressed text databases; entropy; partial sums; sequences", } @Article{Kowalski:2008:WAD, author = "Dariusz R. Kowalski and Alexander A. Shvartsman", title = "Writing-all deterministically and optimally using a nontrivial number of asynchronous processors", journal = j-TALG, volume = "4", number = "3", pages = "33:1--33:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367073", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "The problem of performing $n$ tasks on $p$ asynchronous or undependable processors is a basic problem in distributed computing. This article considers an abstraction of this problem called {\em Write-All: using p processors write 1's into all locations of an array of size n}. In this problem writing 1 abstracts the notion of performing a simple task. Despite substantial research, there is a dearth of efficient deterministic asynchronous algorithms for {\em Write-All/}. Efficiency of algorithms is measured in terms of {\em work\/} that accounts for all local steps performed by the processors in solving the problem. Thus, an optimal algorithm would have work $\Theta(n)$, however it is known that optimality cannot be achieved when $p = \Omega(n)$. The quest then is to obtain work-optimal solutions for this problem using a nontrivial, compared to $n$, number of processors $p$. The algorithm presented in this article has work complexity of $O(n + p^{2 + \epsilon})$, and it achieves work optimality for $p = O(n^{1/(2 + \epsilon)})$ for any $\epsilon > 0$, while the previous best result achieved optimality for $p \leq 4 \sqrt n / \log n$. Additionally, the new result uses {\em only\/} the atomic read/write memory, without resorting to using the test-and-set primitive that was necessary in the previous solution.", acknowledgement = ack-nhfb, articleno = "33", keywords = "Asynchrony; distributed algorithms; shared memory; work; Write-All", } @Article{Even:2008:ACR, author = "Guy Even and Retsef Levi and Dror Rawitz and Baruch Schieber and Shimon (Moni) Shahar and Maxim Sviridenko", title = "Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs", journal = j-TALG, volume = "4", number = "3", pages = "34:1--34:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367074", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. In this article, we study the capacitated version of this problem in which the input includes an integral capacity for each line. The capacity of a line bounds the number of rectangles that the line can cover. We consider two versions of this problem. In the first, one is allowed to use only a single copy of each line ({\em hard capacities\/}), and in the second, one is allowed to use multiple copies of every line, but the multiplicities are counted in the size (or weight) of the solution ({\em soft capacities\/}).\par We present an exact polynomial-time algorithm for the weighted one dimensional case with hard capacities that can be extended to the one dimensional weighted case with soft capacities. This algorithm is also extended to solve a certain capacitated multi-item {\em lot-sizing\/} inventory problem with joint set-up costs. For the case of $d$-dimensional rectangle stabbing with soft capacities, we present a $3d$-approximation algorithm for the unweighted case. For $d$-dimensional rectangle stabbing problem with hard capacities, we present a bi-criteria algorithm that computes $4d$-approximate solutions that use at most two copies of every line. Finally, we present hardness results for rectangle stabbing when the dimension is part of the input and for a two-dimensional weighted version with hard capacities.", acknowledgement = ack-nhfb, articleno = "34", keywords = "Approximation algorithms; capacitated covering; lot sizing; rectangle stabbing", } @Article{Zhang:2008:CCP, author = "Cun-Quan Zhang and Yongbin Ou", title = "Clustering, community partition and disjoint spanning trees", journal = j-TALG, volume = "4", number = "3", pages = "35:1--35:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367075", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Clustering method is one of the most important tools in statistics. In a graph theory model, clustering is the process of finding all dense subgraphs. A mathematically well-defined measure for graph density is introduced in this article as follows. Let $G = (V, E)$ be a graph (or multi-graph) and $H$ be a subgraph of $G$. The dynamic density of $H$ is the greatest integer $k$ such that $\min_\forall P \{| E (H / P)|/| V (H / P)| - 1\} > k$ where the minimum is taken over all possible partitions $P$ of the vertex set of $H$, and $H / P$ is the graph obtained from $H$ by contracting each part of $P$ into a single vertex. A subgraph $H$ of $G$ is a level-$k$ community if $H$ is a maximal subgraph of $G$ with dynamic density at least $k$. An algorithm is designed in this paper to detect all level-$h$ communities of an input multi-graph $G$. The worst-case complexity of this algorithm is upper bounded by $O(|V(G)|^2 h^2)$. This new method is one of few available clustering methods that are mathematically well-defined, supported by rigorous mathematical proof and able to achieve the optimization goal with polynomial complexity. As a byproduct, this algorithm also can be applied for finding edge-disjoint spanning trees of a multi-graph. The worst-case complexity is lower than all known algorithms for multi-graphs.", acknowledgement = ack-nhfb, articleno = "35", keywords = "clustering; community; dense subgraph; dynamic density; hierarchical clustering; polynomial algorithm; Spanning trees", } @Article{Yu:2008:IAM, author = "Hung-I. Yu and Tzu-Chin Lin and Biing-Feng Wang", title = "Improved algorithms for the minmax-regret 1-center and 1-median problems", journal = j-TALG, volume = "4", number = "3", pages = "36:1--36:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367076", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In this article, efficient algorithms are presented for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. For the minmax-regret 1-center problem on a general graph, we improve the previous upper bound from $O(mn^2 \log n)$ to $O(mn \log n)$. For the problem on a tree, we improve the upper bound from $O(n^2)$ to $O(n \log^2 n)$. For the minmax-regret 1-median problem on a general graph, we improve the upper bound from $O(mn^2 \log n)$ to $O(mn^2 + n^3 \log n)$. For the problem on a tree, we improve the upper bound from $O(n \log^2 n)$ to $O(n \log n)$.", acknowledgement = ack-nhfb, articleno = "36", keywords = "centers; general graphs; Location theory; medians; minmax-regret optimization; trees", } @Article{Abraham:2008:CNI, author = "Ittai Abraham and Cyril Gavoille and Dahlia Malkhi and Noam Nisan and Mikkel Thorup", title = "Compact name-independent routing with minimum stretch", journal = j-TALG, volume = "4", number = "3", pages = "37:1--37:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367077", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a $\Otilde(\sqrt n)$ space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is optimal in a very strong sense. It is known that no compact routing using $o(n)$ space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires $\Omega (\sqrt n)$ space per node.", acknowledgement = ack-nhfb, articleno = "37", keywords = "Compact routing", } @Article{Pruhs:2008:GBR, author = "Kirk Pruhs and Patchrawat Uthaisombut and Gerhard Woeginger", title = "Getting the best response for your erg", journal = j-TALG, volume = "4", number = "3", pages = "38:1--38:??", month = jun, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1367064.1367078", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:06 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider the speed scaling problem of minimizing the average response time of a collection of dynamically released jobs subject to a constraint $A$ on energy used. We propose an algorithmic approach in which an energy optimal schedule is computed for a huge $A$, and then the energy optimal schedule is maintained as $A$ decreases. We show that this approach yields an efficient algorithm for equi-work jobs. We note that the energy optimal schedule has the surprising feature that the job speeds are not monotone functions of the available energy. We then explain why this algorithmic approach is problematic for arbitrary work jobs. Finally, we explain how to use the algorithm for equi-work jobs to obtain an algorithm for arbitrary work jobs that is $O(1)$-approximate with respect to average response time, given an additional factor of $(1 + \epsilon)$ energy.", acknowledgement = ack-nhfb, articleno = "38", keywords = "frequency scaling; power management; scheduling; Speed scaling; voltage scaling", } @Article{Ajwani:2008:AIT, author = "Deepak Ajwani and Tobias Friedrich and Ulrich Meyer", title = "An {$O(n^{2.75})$} algorithm for incremental topological ordering", journal = j-TALG, volume = "4", number = "4", pages = "39:1--39:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383370", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present a simple algorithm which maintains the topological order of a directed acyclic graph (DAG) with $n$ nodes, under an online edge insertion sequence, in $O(n^{2.75})$ time, independent of the number $m$ of edges inserted. For dense DAGs, this is an improvement over the previous best result of $O(\min m^{3/2} \log n, m^{3/2} + n^2 \log n)$ by Katriel and Bodlaender [2006]. We also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting.", acknowledgement = ack-nhfb, articleno = "39", keywords = "Dynamic algorithms; graphs; online algorithms; topological order", } @Article{Ibarra:2008:FDA, author = "Louis Ibarra", title = "Fully dynamic algorithms for chordal graphs and split graphs", journal = j-TALG, volume = "4", number = "4", pages = "40:1--40:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383371", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality; and (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in $O(n)$ time, where $n$ is the number of vertices. In the second, an insertion query runs in $O(\log^2 n)$ time, an insertion in $O(n)$ time, a deletion query in $O(n)$ time, and a deletion in $O(n \log n)$ time. We also present a data structure that allows a deletion query to run in $O(\sqrt m)$ time in either implementation, where $m$ is the current number of edges. Updating this data structure after a deletion or insertion requires $O(m)$ time.\par We also present a very simple dynamic algorithm that supports each of the following operations in $O(1)$ time on a general graph: (1) query whether the graph is split, and (2) delete or insert an arbitrary edge.", acknowledgement = ack-nhfb, articleno = "40", keywords = "chordal graphs; clique trees; Dynamic graph algorithms; split graphs", } @Article{Korman:2008:DRS, author = "Amos Korman and David Peleg", title = "Dynamic routing schemes for graphs with low local density", journal = j-TALG, volume = "4", number = "4", pages = "41:1--41:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383372", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "This article studies approximate distributed routing schemes on dynamic communication networks. The work focuses on dynamic weighted general graphs where the vertices of the graph are fixed, but the weights of the edges may change. Our main contribution concerns bounding the cost of adapting to dynamic changes. The update efficiency of a routing scheme is measured by the time needed in order to update the routing scheme following a weight change. A naive dynamic routing scheme, which updates all vertices following a weight change, requires $\Omega(\hbox{\em Diam\/})$ time in order to perform the updates after every weight change, where {\em Diam\/} is the diameter of the underlying graph. In contrast, this article presents approximate dynamic routing schemes with average time complexity $\Thetatilde(d)$ per topological change, where $d$ is the local density parameter of the underlying graph. Following a weight change, our scheme never incurs more than {\em Diam\/} time; thus, our scheme is particularly efficient on graphs which have low local density and large diameter. The article also establishes upper and lower bounds on the size of the databases required by the scheme at each site.", acknowledgement = ack-nhfb, articleno = "41", keywords = "distributed algorithms; dynamic networks; Routing schemes", } @Article{Cohen:2008:LGG, author = "Reuven Cohen and Pierre Fraigniaud and David Ilcinkas and Amos Korman and David Peleg", title = "Label-guided graph exploration by a finite automaton", journal = j-TALG, volume = "4", number = "4", pages = "42:1--42:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383373", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "A finite automaton, simply referred to as a {\em robot}, has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any $k$-state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot $R$, and a way to color in black or white the nodes of any bounded-degree graph $G$, so that $R$ can explore the colored graph $G$. Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).", acknowledgement = ack-nhfb, articleno = "42", keywords = "Distributed algorithms; graph exploration; labeling schemes", } @Article{Suzuki:2008:DSP, author = "Akiko Suzuki and Takeshi Tokuyama", title = "Dense subgraph problems with output-density conditions", journal = j-TALG, volume = "4", number = "4", pages = "43:1--43:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383374", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider the dense subgraph problem that extracts a subgraph, with a prescribed number of vertices, having the maximum number of edges (or total edge weight, in the weighted case) in a given graph. We give approximation algorithms with improved theoretical approximation ratios assuming that the density of the optimal output subgraph is high, where density is the ratio of number of edges (or sum of edge weights) to the number of edges in the clique on the same number of vertices. Moreover, we investigate the case where the input graph is bipartite and design a randomized pseudopolynomial time approximation scheme that can become a randomized PTAS, even if the size of the optimal output graph is comparatively small. This is a significant improvement in a theoretical sense, since no constant-ratio approximation algorithm was known previously if the output graph has o(n) vertices.", acknowledgement = ack-nhfb, articleno = "43", keywords = "approximation algorithms; Combinatorial optimization; dense subgraph; randomized algorithms", } @Article{Bar-Noy:2008:DCF, author = "Amotz Bar-Noy and Panagiotis Cheilaris and Shakhar Smorodinsky", title = "Deterministic conflict-free coloring for intervals: {From} offline to online", journal = j-TALG, volume = "4", number = "4", pages = "44:1--44:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383375", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We investigate deterministic algorithms for a frequency assignment problem in cellular networks. The problem can be modeled as a special vertex coloring problem for hypergraphs: In every hyperedge there must exist a vertex with a color that occurs exactly once in the hyperedge (the conflict-free property). We concentrate on a special case of the problem, called conflict-free coloring for intervals. We introduce a hierarchy of four models for the aforesaid problem: (i) static, (ii) dynamic offline, (iii) dynamic online with absolute positions, and (iv) dynamic online with relative positions. In the dynamic offline model, we give a deterministic algorithm that uses at most log$_{3/2}$ $n$ + 1 \&;approx; 1.71 log$_2$ n colors and show inputs that force any algorithm to use at least 3 log$_5$ $n$ + 1 {\SGMLapprox} 1.29 log$_2$ $n$ colors. For the online absolute-positions model, we give a deterministic algorithm that uses at most 3\lceil log$_3$ $n$ {\rceil} {\SGMLapprox} 1.89 log$_2$ $n$ colors. To the best of our knowledge, this is the first deterministic online algorithm using $O(\log n)$ colors in a nontrivial online model. In the online relative-positions model, we resolve an open problem by showing a tight analysis on the number of colors used by the first-fit greedy online algorithm. We also consider conflict-free coloring only with respect to intervals that contain at least one of the two extreme points.", acknowledgement = ack-nhfb, articleno = "44", keywords = "cellular networks; coloring; conflict free; frequency assignment; Online algorithms", } @Article{Chandran:2008:IAO, author = "Nishanth Chandran and Ryan Moriarty and Rafail Ostrovsky and Omkant Pandey and Mohammad Ali Safari and Amit Sahai", title = "Improved algorithms for optimal embeddings", journal = j-TALG, volume = "4", number = "4", pages = "45:1--45:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383376", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. The notion of embedding is, given two metric spaces on the same number of points, to find a bijection that minimizes maximum Lipschitz and bi-Lipschitz constants. One reason for the popularity of the notion is that algorithms designed for one metric space can be applied to a different one, given an embedding with small distortion. The better distortion, the better the effectiveness of the original algorithm applied to a new metric space.\par The goal recently studied by Kenyon et al. [2004] is to consider all possible embeddings between two {\em finite\/} metric spaces and to find the best possible one; that is, consider a single objective function over the space of all possible embeddings that minimizes the distortion. In this article we continue this important direction. In particular, using a theorem of Albert and Atkinson [2005], we are able to provide an algorithm to find the optimal bijection between two line metrics, provided that the optimal distortion is smaller than 13.602. This improves the previous bound of 3 + 2\sqrt 2, solving an open question posed by Kenyon et al. [2004]. Further, we show an inherent limitation of algorithms using the ``forbidden pattern'' based dynamic programming approach, in that they cannot find optimal mapping if the optimal distortion is more than 7 + 4\sqrt 3 ({\SGMLsime} 13.928). Thus, our results are almost optimal for this method. We also show that previous techniques for general embeddings apply to a (slightly) more general class of metrics.", acknowledgement = ack-nhfb, articleno = "45", keywords = "dynamic programming; forbidden patterns; line embeddings; metric spaces; Optimal metric embeddings; shape matching", } @Article{Alon:2008:OEM, author = "Noga Alon and Mihai B{\~a}doiu and Erik D. Demaine and Martin Farach-Colton and Mohammadtaghi Hajiaghayi and Anastasios Sidiropoulos", title = "Ordinal embeddings of minimum relaxation: {General} properties, trees, and ultrametrics", journal = j-TALG, volume = "4", number = "4", pages = "46:1--46:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383377", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We introduce a new notion of embedding, called {\em minimum-relaxation ordinal embedding}, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and not the distances themselves, that must be preserved as much as possible. The (multiplicative) relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. We develop several worst-case bounds and approximation algorithms on ordinal embedding. In particular, we establish that ordinal embedding has many qualitative differences from metric embedding, and we capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.", acknowledgement = ack-nhfb, articleno = "46", keywords = "distortion; Metrics; ordinal embedding; relaxation", } @Article{Blaser:2008:NAA, author = "Markus Bl{\"a}ser", title = "A new approximation algorithm for the asymmetric {TSP} with triangle inequality", journal = j-TALG, volume = "4", number = "4", pages = "47:1--47:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383378", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present a polynomial time factor 0.999 {\SGMLcdot} log $n$ approximation algorithm for the asymmetric traveling salesperson problem with triangle inequality.", acknowledgement = ack-nhfb, articleno = "47", keywords = "Approximation algorithm; cycle cover; traveling salesman problem; TSP", } @Article{Boyar:2008:RWO, author = "Joan Boyar and Paul Medvedev", title = "The relative worst order ratio applied to seat reservation", journal = j-TALG, volume = "4", number = "4", pages = "48:1--48:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383379", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "The seat reservation problem is the problem of assigning passengers to seats on a train with $n$ seats and $k$ stations enroute in an online manner. The performance of algorithms for this problem is studied using the relative worst order ratio, a fairly new measure for the quality of online algorithms, which allows for direct comparisons between algorithms. This study has yielded new separations between algorithms. For example, for both variants of the problem considered, using the relative worst order ratio, First-Fit and Best-Fit are shown to be better than Worst-Fit.", acknowledgement = ack-nhfb, articleno = "48", keywords = "Online; quality measure; relative worst order ratio; seat reservation", } @Article{Nieberg:2008:ASW, author = "Tim Nieberg and Johann Hurink and Walter Kern", title = "Approximation schemes for wireless networks", journal = j-TALG, volume = "4", number = "4", pages = "49:1--49:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383380", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Wireless networks are created by the communication links between a collection of radio transceivers. The nature of wireless transmissions does not lead to arbitrary undirected graphs but to structured graphs which we characterize by the polynomially bounded growth property. In contrast to many existing graph models for wireless networks, the property of polynomially bounded growth is defined independently of geometric data such as positional information.\par On such wireless networks, we present an approach that can be used to create polynomial-time approximation schemes for several optimization problems called the local neighborhood-based scheme. We apply this approach to the problems of seeking maximum (weight) independent sets and minimum dominating sets. These are two important problems in the area of wireless communication networks and are also used in many applications ranging from clustering to routing strategies. However, the approach is presented in a general fashion since it can be applied to other problems as well.\par The approach for the approximation schemes is robust in the sense that it accepts any undirected graph as input and either outputs a solution of desired quality or correctly asserts that the graph presented as input does not satisfy the structural assumption of a wireless network (an NP-hard problem).", acknowledgement = ack-nhfb, articleno = "49", keywords = "bounded growth; maximum independent set; minimum dominating set; PTAS; Wireless ad-hoc networks", } @Article{Massberg:2008:AAF, author = "Jens Ma{\ss}berg and Jens Vygen", title = "Approximation algorithms for a facility location problem with service capacities", journal = j-TALG, volume = "4", number = "4", pages = "50:1--50:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383381", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present the first constant-factor approximation algorithms for the following problem. Given a metric space $(V, c)$, a finite set $d \subseteq V$ of terminals/customers with demands $d: d \rightarrow R_+$, a facility opening cost $f \in R_+$ and a capacity $u \in R_+$, find a partition $d = D_1 {\SGMLcupdot} \ldots{} {\SGMLcupdot} D_k$ and Steiner trees $T_i$ for $D_i(i = 1, \ldots{}, k)$ with $c(E (T_i)) + d (D_i) \leq u$ for $i = 1, \ldots{}, k$ such that $\sum_i = 1^{k} c (E(T_i)) + kf$ is minimum. This problem arises in VLSI design. It generalizes the bin-packing problem and the Steiner tree problem. In contrast to other network design and facility location problems, it has the additional feature of upper bounds on the service cost that each facility can handle. Among other results, we obtain a 4.1-approximation in polynomial time, a 4.5-approximation in cubic time, and a 5-approximation as fast as computing a minimum spanning tree on $(D, c)$.", acknowledgement = ack-nhfb, articleno = "50", keywords = "Approximation algorithm; facility location; network design; VLSI design", } @Article{Swamy:2008:FTF, author = "Chaitanya Swamy and David B. Shmoys", title = "Fault-tolerant facility location", journal = j-TALG, volume = "4", number = "4", pages = "51:1--51:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383382", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client $j$ has a requirement that $r_j$ {\em distinct\/} facilities serve it, instead of just one. We give a 2.076-approximation algorithm for this problem using LP rounding, which is currently the best-known performance guarantee. Our algorithm exploits primal and dual complementary slackness conditions and is based on {\em clustered randomized rounding}. A technical difficulty that we overcome is the presence of terms with negative coefficients in the dual objective function, which makes it difficult to bound the cost in terms of dual variables. For the case where all requirements are the same, we give a primal-dual 1.52-approximation algorithm.\par We also consider a fault-tolerant version of the $k$-median problem. In the metric $k$-median problem, we are given $n$ points in a metric space. We must select $k$ of these to be centers, and then assign each input point $j$ to the selected center that is closest to it. In the fault-tolerant version we want $j$ to be assigned to $r_j$ distinct centers. The goal is to select the $k$ centers so as to minimize the sum of assignment costs. The primal-dual algorithm for fault-tolerant facility location with uniform requirements also yields a 4-approximation algorithm for the fault-tolerant $k$-median problem for this case. This the first constant-factor approximation algorithm for the uniform requirements case.", acknowledgement = ack-nhfb, articleno = "51", keywords = "Approximation algorithms; facility location; k-median problem", } @Article{Fotakis:2008:ACG, author = "Dimitris Fotakis and Spyros Kontogiannis and Paul Spirakis", title = "Atomic congestion games among coalitions", journal = j-TALG, volume = "4", number = "4", pages = "52:1--52:??", month = aug, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1383369.1383383", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:03:43 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider algorithmic questions concerning the existence, tractability, and quality of Nash equilibria, in atomic congestion games among users participating in selfish coalitions.\par We introduce a coalitional congestion model among atomic players and demonstrate many interesting similarities with the noncooperative case. For example, there exists a potential function proving the existence of pure Nash equilibria (PNE) in the unrelated parallel links setting; in the network setting, the finite improvement property collapses as soon as we depart from linear delays, but there is an exact potential (and thus PNE) for linear delays. The price of anarchy on identical parallel links demonstrates a quite surprising threshold behavior: It persists on being asymptotically equal to that in the case of the noncooperative KP-model, unless the number of coalitions is {\em sublogarithmic}.\par We also show crucial differences, mainly concerning the hardness of algorithmic problems that are solved efficiently in the noncooperative case. Although we demonstrate convergence to robust PNE, we also prove the hardness of computing them. On the other hand, we propose a generalized fully mixed Nash equilibrium that can be efficiently constructed in most cases. Finally, we propose a natural improvement policy and prove its convergence in pseudopolynomial time to PNE which are robust against (even dynamically forming) coalitions of small size.", acknowledgement = ack-nhfb, articleno = "52", keywords = "Algorithmic game theory; congestion games; convergence to equilibria; price of anarchy", } @Article{Torng:2008:SOU, author = "Eric Torng and Jason McCullough", title = "{SRPT} optimally utilizes faster machines to minimize flow time", journal = j-TALG, volume = "5", number = "1", pages = "1:1--1:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435376", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We analyze the shortest remaining processing time (SRPT) algorithm with respect to the problem of scheduling $n$ jobs with release times on $m$ identical machines to minimize total flow time. It is known that SRPT is optimal if $m$ = 1 but that SRPT has a worst-case approximation ratio of $\Theta(\min(=log n/m, \log \Delta))$ for this problem, where $\Delta$ is the ratio of the length of the longest job divided by the length of the shortest job. It has previously been shown that SRPT is able to use faster machines to produce a schedule {\em as good as\/} an optimal algorithm using slower machines. We now show that SRPT {\em optimally\/} uses these faster machines with respect to the worst-case approximation ratio. That is, if SRPT is given machines that are $s \geq 2 - 1 / m$ times as fast as those used by an optimal algorithm, SRPT's flow time is at least $s$ {\em times smaller\/} than the flow time incurred by the optimal algorithm. Clearly, no algorithm can offer a better worst-case guarantee, and we show that existing algorithms with similar performance guarantees to SRPT without resource augmentation do not optimally use extra resources.", acknowledgement = ack-nhfb, articleno = "1", keywords = "flow time; parallel machines; resource augmentation; scheduling; SRPT", } @Article{Goldwasser:2008:ONS, author = "Michael H. Goldwasser and Mark Pedigo", title = "Online nonpreemptive scheduling of equal-length jobs on two identical machines", journal = j-TALG, volume = "5", number = "1", pages = "2:1--2:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435377", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as $P 2 | p_j = p, 4_j | \sum{\SGMLUhorbar}_j$. The problem is known to be polynomially solvable in an offline setting.\par In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is $3/2$-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.", acknowledgement = ack-nhfb, articleno = "2", keywords = "Admission control; competitive analysis; scheduling", } @Article{Aiello:2008:CBM, author = "William Aiello and Alex Kesselman and Yishay Mansour", title = "Competitive buffer management for shared-memory switches", journal = j-TALG, volume = "5", number = "1", pages = "3:1--3:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435378", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider buffer management policies for shared memory switches. We study the case of overloads resulting in packet loss, where the constraint is the limited shared memory capacity. The goal of the buffer management policy is that of maximizing the number of packets transmitted. The problem is online in nature, and thus we use competitive analysis to measure the performance of the buffer management policies. Our main result is to show that the well-known preemptive Longest Queue Drop ({\em LQD\/}) policy is at most 2-competitive and at least $\sqrt 2$-competitive. We also demonstrate a general lower bound of $4/3$ on the performance of any deterministic online policy. Finally, we consider some other popular non-preemptive policies including Complete Partition, Complete Sharing, Static Threshold and Dynamic Threshold and derive almost tight bounds on their performance.", acknowledgement = ack-nhfb, articleno = "3", keywords = "Buffer management; competitive analysis; shared memory", } @Article{Agarwal:2008:KDD, author = "Pankaj K. Agarwal and Haim Kaplan and Micha Sharir", title = "Kinetic and dynamic data structures for closest pair and all nearest neighbors", journal = j-TALG, volume = "5", number = "1", pages = "4:1--4:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435379", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of $n$ moving points in the plane; insertions and deletions of points are also allowed. If no insertions or deletions take place, the structure for the closest pair uses $O(n \log n)$ space, and processes $O(n^2 \beta_ + 2(n) \log n)$ critical events, each in $O(\log^2 n)$ time. Here $s$ is the maximum number of times where the distances between any two specific pairs of points can become equal, $\beta_s(q) = \lambda_s(q)/q$, and $\lambda_s(q)$ is the maximum length of Davenport-Schinzel sequences of order $s$ on $q$ symbols. The dynamic version of the problem incurs a slight degradation in performance: If $m$ \geq $n$ insertions and deletions are performed, the structure still uses $O(n \log n)$ space, and processes $O(m n \beta_s +2(n) \log^3 n)$ events, each in $O(\log^3 n)$ time.\par Our kinetic data structure for all nearest neighbors uses $O(n \log^2 n)$ space, and processes $O(n^2 \beta^{2_s +2}(n) \log^3 n)$ critical events. The expected time to process all events is $O(n^2 \beta_{s +2}^2(n) \log^4 n)$, though processing a single event may take $\Theta(n)$ expected time in the worst case. If $m \geq n$ insertions and deletions are performed, then the expected number of events is $O(m n \beta^2_{s +2}(n) \log^3 n)$ and processing them all takes $O(m n \beta^2_{s + 2} (n) \log^4 n)$. An insertion or deletion takes $O(n)$ expected time.", acknowledgement = ack-nhfb, articleno = "4", keywords = "closest pair; computational geometry; Kinetic data structures; nearest neighbors", } @Article{Agarwal:2008:ACT, author = "Pankaj K. Agarwal and Micha Sharir and Emo Welzl", title = "Algorithms for center and {Tverberg} points", journal = j-TALG, volume = "5", number = "1", pages = "5:1--5:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435380", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Given a set $s$ of $n$ points in $R^3$, a point $x$ in $R^3$ is called {\em center point of $S$\/} if every closed halfspace whose bounding hyperplane passes through $x$ contains at least $\lceil n / 4 \rceil$ points from $S$. We present a near-quadratic algorithm for computing the {\em center region}, that is the set of all center points, of a set of $n$ points in $R^3$. This is nearly tight in the worst case since the center region can have $\Omega(n^2)$ complexity.\par We then consider sets $s$ of $3 n$ points in the plane which are the union of three disjoint sets consisting respectively of $n$ red, $n$ blue, and $n$ green points. A point $x$ in $R^2$ is called a {\em colored Tverberg point of $S$\/} if there is a partition of $s$ into $n$ triples with one point of each color, so that $x$ lies in all triangles spanned by these triples. We present a first polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such a 3-colored set $S$.", acknowledgement = ack-nhfb, articleno = "5", keywords = "Arrangements; center point; Tverberg point", } @Article{Grandoni:2008:DWV, author = "Fabrizio Grandoni and Jochen K{\"o}nemann and Alessandro Panconesi", title = "Distributed weighted vertex cover via maximal matchings", journal = j-TALG, volume = "5", number = "1", pages = "6:1--6:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435381", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "In this article, we consider the problem of computing a minimum-weight vertex-cover in an $n$-node, weighted, undirected graph $G = (V, E)$. We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of $O(\log n + \log \SGMLWcirc)$ communication rounds, where $\SGMLWcirc$ is the average vertex-weight. The previous best algorithm for this problem requires $O(\log n (\log n + \log \SGMLWcirc))$ rounds and it is not fully distributed.\par For a maximal matching $m$ in $G$, it is a well-known fact that any vertex-cover in $G$ needs to have at least $|m|$ vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting.", acknowledgement = ack-nhfb, articleno = "6", keywords = "Approximation algorithms; distributed algorithms; maximal matching; vertex cover", } @Article{Vishwanathan:2008:HIA, author = "Sundar Vishwanathan", title = "On hard instances of approximate vertex cover", journal = j-TALG, volume = "5", number = "1", pages = "7:1--7:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435382", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We show that if there is a $2 - \epsilon$ approximation algorithm for vertex cover on graphs with vector chromatic number at most $2 + \delta$, then there is a $2 - f(\epsilon, \delta)$ approximation algorithm for vertex cover for all graphs.", acknowledgement = ack-nhfb, articleno = "7", keywords = "Approximation algorithms; vertex cover", } @Article{Berend:2008:CDG, author = "Daniel Berend and Steven S. Skiena and Yochai Twitto", title = "Combinatorial dominance guarantees for problems with infeasible solutions", journal = j-TALG, volume = "5", number = "1", pages = "8:1--8:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435383", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "The design and analysis of approximation algorithms for {\em NP\/}-hard problems is perhaps the most active research area in the theory of combinatorial algorithms. In this article, we study the notion of a {\em combinatorial dominance guarantee\/} as a way for assessing the performance of a given approximation algorithm. An $f(n)$ dominance bound is a guarantee that the heuristic always returns a solution not worse than at least $f(n)$ solutions. We give tight analysis of many heuristics, and establish novel and interesting dominance guarantees even for certain inapproximable problems and heuristic search algorithms. For example, we show that the maximal matching heuristic of VERTEX COVER offers a combinatorial dominance guarantee of $2^n - (1.839 + o(1))^n$. We also give inapproximability results for most of the problems we discuss.", acknowledgement = ack-nhfb, articleno = "8", keywords = "algorithms analysis; approximation algorithms; Computation complexity; dominance analysis", } @Article{Fomin:2008:CBM, author = "Fedor V. Fomin and Fabrizio Grandoni and Artem V. Pyatkin and Alexey A. Stepanov", title = "Combinatorial bounds via measure and conquer: {Bounding} minimal dominating sets and applications", journal = j-TALG, volume = "5", number = "1", pages = "9:1--9:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435384", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We provide an algorithm listing all minimal dominating sets of a graph on $n$ vertices in time $O(1.7159^n)$. This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on $n$ vertices is at most $1.7159^n$, thus improving on the trivial $O(2^n / \sqrt n)$ bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms.\par Based on this result, we derive an $O(2.8718^n)$ algorithm for the domatic number problem.", acknowledgement = ack-nhfb, articleno = "9", keywords = "domatic number; Exact exponential algorithms; listing algorithms; measure and conquer; minimum dominating set; minimum set cover", } @Article{Oum:2008:ARW, author = "Sang-Il Oum", title = "Approximating rank-width and clique-width quickly", journal = j-TALG, volume = "5", number = "1", pages = "10:1--10:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435385", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Rank-width was defined by Oum and Seymour [2006] to investigate clique-width. They constructed an algorithm that either outputs a rank-decomposition of width at most $f(k)$ for some function f or confirms that rank-width is larger than $k$ in time $O(|V|^9 \log |V|)$ for an input graph $G = (V, E)$ and a fixed $k$. We develop three separate algorithms of this kind with faster running time. We construct an $O(|V|^4)$-time algorithm with $f(k) = 3 k + 1$ by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by Oum and Seymour. Another one is an $O(|V|^3)$-time algorithm with $f(k) = 24 k$, achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hlin{\^e}n{\'y} [2005]. Finally we construct an $O(|V|^3)$-time algorithm with $f(k) = 3 k - 1$ by combining the ideas of the two previously cited papers.", acknowledgement = ack-nhfb, articleno = "10", keywords = "Approximation algorithms; branch-width; clique-width; matroids; rank-width", } @Article{Brandstadt:2008:SLT, author = "Andreas Brandst{\"a}dt and Van Bang Le and R. Sritharan", title = "Structure and linear-time recognition of 4-leaf powers", journal = j-TALG, volume = "5", number = "1", pages = "11:1--11:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435386", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "A graph $G$ is the $k$-{\em leaf power\/} of a tree $T$ if its vertices are leaves of $T$ such that two vertices are adjacent in $G$ if and only if their distance in $T$ is at most $k$. Then $T$ is a $k$-{\em leaf root\/} of $G$. This notion was introduced and studied by Nishimura, Ragde, and Thilikos [2002], motivated by the search for underlying phylogenetic trees. Their results imply an $O(n^3)$-time recognition algorithm for 4-leaf powers. Recently, Rautenbach [2006] as well as Dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. We give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. As a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers.", acknowledgement = ack-nhfb, articleno = "11", keywords = "Graph powers; leaf powers; phylogenetic trees; squares of trees; trees", } @Article{Chen:2008:MCI, author = "Xin Chen and Lan Liu and Zheng Liu and Tao Jiang", title = "On the minimum common integer partition problem", journal = j-TALG, volume = "5", number = "1", pages = "12:1--12:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435387", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We introduce a new combinatorial optimization problem in this article, called the {\em minimum common integer partition\/} (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint assembly. A {\em partition\/} of a positive integer $n$ is a multiset of positive integers that add up to exactly $n$, and an {\em integer partition\/} of a multiset $s$ of integers is defined as the multiset union of partitions of integers in $S$. Given a sequence of multisets $s_1, s_2, \ldots, S_k$ of integers, where $k \geq 2$, we say that a multiset is a {\em common integer partition\/} if it is an integer partition of every multiset $S_i, 1 \leq i \leq k$. The MCIP problem is thus defined as to find a common integer partition of $s_1, s_2, \ldots, S_k$ with the minimum cardinality, denoted as MCIP($s_1$, $S_2$, \ldots{}, $S_k$). It is easy to see that the MCIP problem is NP-hard, since it generalizes the well-known subset sum problem. We can in fact show that it is APX-hard. We will also present a $5/4$-approximation algorithm for the MCIP problem when $k = 2$, and a $3 k (k - 1) / 3 k - 2$-approximation algorithm for $k \geq 3$.", acknowledgement = ack-nhfb, articleno = "12", keywords = "approximation algorithm; combinatorial optimization; computational biology; integer partition; NP-hard; Subset sum", } @Article{Azriel:2008:IFS, author = "Dany Azriel and Noam Solomon and Shay Solomon", title = "On an infinite family of solvable {Hanoi} graphs", journal = j-TALG, volume = "5", number = "1", pages = "13:1--13:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435388", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "The Tower of Hanoi problem is generalized by placing pegs on the vertices of a given directed graph $G$ with two distinguished vertices, $s$ and $D$, and allowing moves only along arcs of this graph. An optimal solution for such a graph $G$ is an algorithm that completes the task of moving a tower of any given number of disks from $s$ to $d$ in a minimal number of disk moves.\par In this article we present an algorithm which solves the problem for two infinite families of graphs, and prove its optimality. To the best of our knowledge, this is the first optimality proof for an {\em infinite\/} family of graphs.\par Furthermore, we present a unified algorithm that solves the problem for a wider family of graphs and conjecture its optimality.", acknowledgement = ack-nhfb, articleno = "13", keywords = "Optimality proofs; Tower of Hanoi", } @Article{Elmasry:2008:MPQ, author = "Amr Elmasry and Claus Jensen and Jyrki Katajainen", title = "Multipartite priority queues", journal = j-TALG, volume = "5", number = "1", pages = "14:1--14:??", month = nov, year = "2008", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1435375.1435389", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:04:20 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost of $O(1)$ per minimum finding and insertion, and the worst-case cost of $O(\log n)$ with at most $\log n + O(1)$ element comparisons per deletion, improving the bound of $2 \log n + O(1)$ known for binomial queues. Here, $n$ denotes the number of elements stored in the data structure prior to the operation in question, and $\log n$ equals $\log_2(\max\{2, n\})$. As an immediate application of the priority queue developed, we obtain a sorting algorithm that is optimally adaptive with respect to the inversion measure of disorder, and that sorts a sequence having $n$ elements and $I$ inversions with at most $n \log (I / n) + O(n)$ element comparisons.", acknowledgement = ack-nhfb, articleno = "14", keywords = "constant factors; heaps; meticulous analysis; Priority queues", } @Article{Eppstein:2009:TBG, author = "David Eppstein", title = "Testing bipartiteness of geometric intersection graphs", journal = j-TALG, volume = "5", number = "2", pages = "15:1--15:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497291", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We show how to test the bipartiteness of an intersection graph of $n$ line segments or simple polygons in the plane, or of an intersection graph of balls in $d$-dimensional Euclidean space, in time $O(n \log n)$. More generally, we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric objects. Our algorithms for these problems return either a bipartition of the input or an odd cycle in its intersection graph. We also consider lower bounds for connectivity and $k$-colorability problems of geometric intersection graphs. For unit balls in $d$ dimensions, connectivity testing has equivalent randomized complexity to construction of Euclidean minimum spanning trees, and for line segments in the plane connectivity testing has the same lower bounds as Hopcroft's point-line incidence testing problem; therefore, for these problems, connectivity is unlikely to be solved as efficiently as bipartiteness. For line segments or planar disks, testing $k$-colorability of intersection graphs for $k$ > 2 is NP-complete.", acknowledgement = ack-nhfb, articleno = "15", keywords = "Bipartite graph; coin graph; disks; geometric thickness; graph coloring; Hopcroft's problem; intersection graph; line segments; minimum spanning tree", } @Article{Chen:2009:OCF, author = "Ke Chen and Haim Kaplan and Micha Sharir", title = "Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles", journal = j-TALG, volume = "5", number = "2", pages = "16:1--16:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497292", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use $O(\log n) colors, with high probability.\par We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using $O(\log^3 n)$ colors. This is the first efficient (i.e, using $\polylog(n)$ colors) deterministic online CF coloring algorithm for this problem.", acknowledgement = ack-nhfb, articleno = "16", keywords = "coloring; Conflict free coloring; online algorithms", } @Article{Alonso:2009:ACA, author = "Laurent Alonso and Edward M. Reingold", title = "Average-case analysis of some plurality algorithms", journal = j-TALG, volume = "5", number = "2", pages = "17:1--17:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497293", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Given a set of $n$ elements, each of which is colored one of $c$ colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected number of color comparisons when the $c^n$ colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is $c^2 + c - 2/2 c n - O(c^2)$, with variance $\Theta(c^2 n)$. We present and analyze an algorithm for the case $c = 3$ colors whose average complexity on the $3^n$ equally probable inputs is $7083/5425 n + O(\sqrt n) = 1.3056\ldots{} n + O(\sqrt n)$, substantially better than the expected complexity $5/3 n + O(1) = 1.6666\ldots{} n + O(1)$ of the obvious algorithm. We describe a similar algorithm for $c = 4$ colors whose average complexity on the $4^n$ equally probable inputs is $761311/402850 n + O(\log n) = 1.8898\ldots{} n + O(\log n)$, substantially better than the expected complexity $9/4 n + O(1) = 2.25 n + O(1)$ of the obvious algorithm.", acknowledgement = ack-nhfb, articleno = "17", keywords = "Algorithm analysis; majority problem; plurality problem", } @Article{Bar-Noy:2009:TMR, author = "Amotz Bar-Noy and Sudipto Guha and Yoav Katz and Joseph (Seffi) Naor and Baruch Schieber and Hadas Shachnai", title = "Throughput maximization of real-time scheduling with batching", journal = j-TALG, volume = "5", number = "2", pages = "18:1--18:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497294", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and $k$ parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + \epsilon) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + \epsilon , respectively. We also give approximation algorithms for two special cases when all release times are the same.", acknowledgement = ack-nhfb, articleno = "18", keywords = "batching; local ratio technique; Scheduling", } @Article{Rabani:2009:BAT, author = "Yuval Rabani and Gabriel Scalosub", title = "Bicriteria approximation tradeoff for the node-cost budget problem", journal = j-TALG, volume = "5", number = "2", pages = "19:1--19:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497295", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a $(2, O(\log n))$ bicriteria approximation, that is, the solution's profit is at least a fraction of $1 / O(\log n)$ of an optimum solution respecting the budget, while its cost is at most twice the given budget. We improve these results and present a bicriteria tradeoff that, given any $\epsilon \in (0,1]$, guarantees a $(1 + \epsilon, O(1/\epsilon \log n))$-approximation.", acknowledgement = ack-nhfb, articleno = "19", keywords = "Approximation algorithms; bicriteria approximation", } @Article{Li:2009:PTA, author = "Guojun Li and Xiaotie Deng and Ying Xu", title = "A polynomial-time approximation scheme for embedding hypergraph in a cycle", journal = j-TALG, volume = "5", number = "2", pages = "20:1--20:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497296", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized.\par The {\em minimum congestion hypergraph embedding in a cycle\/} problem is known to be NP-hard and its graph version, the {\em minimum congestion graph embedding in a cycle}, is solvable in polynomial-time. Furthermore, for the graph problem, a polynomial-time approximation scheme for the weighted version is known. For the hypergraph model, several approximation algorithms with a ratio of two have been previously published. A recent paper reduced the approximation ratio to 1.5. We present a polynomial-time approximation scheme in this article, settling the debate regarding whether the problem is polynomial-time approximable.", acknowledgement = ack-nhfb, articleno = "20", keywords = "Hypergraph embedding; minimum congestion; NP-hard; polynomial-time approximation scheme", } @Article{Even:2009:AAA, author = "Guy Even and Jon Feldman and Guy Kortsarz and Zeev Nutov", title = "A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2", journal = j-TALG, volume = "5", number = "2", pages = "21:1--21:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497297", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph $G = (V, E)$ and an edge set $E$ on $V$ disjoint to $E$, find a minimum-size subset of edges $F \subseteq E$ such that $(V, E \cup f)$ is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio $1.875 + \epsilon$ of Nagamochi.", acknowledgement = ack-nhfb, articleno = "21", keywords = "Approximation algorithms; connectivity; graphs", } @Article{Marko:2009:ADP, author = "Sharon Marko and Dana Ron", title = "Approximating the distance to properties in bounded-degree and general sparse graphs", journal = j-TALG, volume = "5", number = "2", pages = "22:1--22:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497298", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "We address the problem of approximating the distance of bounded-degree and general sparse graphs from having some predetermined graph property $p$. That is, we are interested in sublinear algorithms for estimating the fraction of edge modifications (additions or deletions) that must be performed on a graph so that it obtains $p$. This fraction is taken with respect to a given upper bound $m$ on the number of edges. In particular, for graphs with degree bound $d$ over $n$ vertices, $m = dn$. To perform such an approximation the algorithm may ask for the degree of any vertex of its choice, and may ask for the neighbors of any vertex.\par The problem of estimating the distance to having a property was first explicitly addressed by Parnas et al. [2006]. In the context of graphs this problem was studied by Fischer and Newman [2007] in the dense graphs model. In this model the fraction of edge modifications is taken with respect to $n^2$, and the algorithm may ask for the existence of an edge between any pair of vertices of its choice. Fischer and Newman showed that every graph property that has a testing algorithm in this model, with query complexity independent of the size of the graph, also has a distance approximation algorithm with query complexity that is independent of the size of graph.\par In this work we focus on bounded-degree and general sparse graphs, and give algorithms for all properties shown to have efficient testing algorithms by Goldreich and Ron [2002]. Specifically, these properties are $k$-edge connectivity, subgraph freeness (for constant-size subgraphs), being an Eulerian graph, and cycle freeness. A variant of our subgraph-freeness algorithm approximates the size of a minimum vertex cover of a graph in sublinear time. This approximation improves on a recent result of Parnas and Ron [2007].", acknowledgement = ack-nhfb, articleno = "22", keywords = "distance approximation; graph properties; property testing; Sublinear approximation algorithms", } @Article{Berry:2009:LTA, author = "Vincent Berry and Christophe Paul and Sylvain Guillemot and Fran{\c{c}}ois Nicolas", title = "Linear time 3-approximation for the {MAST} problem", journal = j-TALG, volume = "5", number = "2", pages = "23:1--23:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497299", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Given a set of leaf-labeled trees with identical leaf sets, the well-known Maximum Agreement SubTree (MAST) problem consists in finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its variant called Maximum Compatible Tree (MCT) are of particular interest in computational biology. This article presents a linear-time approximation algorithm to solve the complement version of MAST, namely identifying the smallest set of leaves to remove from input trees to obtain isomorphic trees. We also present an $O(n^2 + kn)$ algorithm to solve the complement version of MCT. For both problems, we thus achieve significantly lower running times than previously known algorithms. Fast running times are especially important in phylogenetics where large collections of trees are routinely produced by resampling procedures, such as the nonparametric bootstrap or Bayesian MCMC methods.", acknowledgement = ack-nhfb, articleno = "23", keywords = "Approximation algorithm; maximum agreement subtree; maximum compatible subtree; phylogenetic tree", } @Article{Condon:2009:ADA, author = "Anne Condon and Amol Deshpande and Lisa Hellerstein and Ning Wu", title = "Algorithms for distributional and adversarial pipelined filter ordering problems", journal = j-TALG, volume = "5", number = "2", pages = "24:1--24:??", month = mar, year = "2009", CODEN = "????", DOI = "http://doi.acm.org/10.1145/1497290.1497300", ISSN = "1549-6325", bibdate = "Tue Jul 14 19:05:00 MDT 2009", bibsource = "http://portal.acm.org/", abstract = "Pipelined filter ordering is a central problem in database query optimization. The problem is to determine the optimal order in which to apply a given set of commutative filters (predicates) to a set of elements (the tuples of a relation), so as to find, as efficiently as possible, the tuples that satisfy all of the filters. Optimization of pipelined filter ordering has recently received renewed attention in the context of environments such as the Web, continuous high-speed data streams, and sensor networks. Pipelined filter ordering problems are also studied in areas such as fault detection and machine learning under names such as learning with attribute costs, minimum-sum set cover, and satisficing search. We present algorithms for two natural extensions of the classical pipelined filter ordering problem: (1) a {\em distributional-type\/} problem where the filters run in parallel and the goal is to maximize throughput, and (2) an {\em adversarial-type\/} problem where the goal is to minimize the expected value of {\em multiplicative regret}. We present two related algorithms for solving (1), both running in time $O(n^2)$, which improve on the $O(n 3 \log n)$ algorithm of Kodialam. We use techniques from our algorithms for (1) to obtain an algorithm for 1.", acknowledgement = ack-nhfb, articleno = "24", keywords = "flow algorithms; Pipelined filter ordering; query optimization; selection ordering", }