ACM Transactions on Algorithms, Volume 5

Volume 5, Number 1, November 2008

• Eric Torng, Jason McCullough:
  SRPT optimally utilizes faster machines to minimize flow time.
  
• Michael H. Goldwasser, Mark Pedigo:
  Online nonpreemptive scheduling of equal-length jobs on two identical machines.
  
• William Aiello, Alexander Kesselman, Yishay Mansour:
  Competitive buffer management for shared-memory switches.
  
• Pankaj K. Agarwal, Haim Kaplan, Micha Sharir:
  Kinetic and dynamic data structures for closest pair and all nearest neighbors.
  
• Pankaj K. Agarwal, Micha Sharir, Emo Welzl:
  Algorithms for center and Tverberg points.
  
• Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi:
  Distributed weighted vertex cover via maximal matchings.
  
• Sundar Vishwanathan:
  On hard instances of approximate vertex cover.
  
• Daniel Berend, Steven Skiena, Yochai Twitto:
  Combinatorial dominance guarantees for problems with infeasible solutions.
  
• Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, Alexey A. Stepanov:
  Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications.
  
• Sang-il Oum:
  Approximating rank-width and clique-width quickly.
  
• Andreas Brandstädt, Van Bang Le, R. Sritharan:
  Structure and linear-time recognition of 4-leaf powers.
  
• Xin Chen, Lan Liu, Zheng Liu, Tao Jiang:
  On the minimum common integer partition problem.
  
• Dany Azriel, Noam Solomon, Shay Solomon:
  On an infinite family of solvable Hanoi graphs.
  
• Amr Elmasry, Claus Jensen, Jyrki Katajainen:
  Multipartite priority queues.
  

Volume 5, Number 2, March 2009

• David Eppstein:
  Testing bipartiteness of geometric intersection graphs.
  
• Ke Chen, Haim Kaplan, Micha Sharir:
  Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles.
  
• Laurent Alonso, Edward M. Reingold:
  Average-case analysis of some plurality algorithms.
  
• Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai:
  Throughput maximization of real-time scheduling with batching.
  
• Yuval Rabani, Gabriel Scalosub:
  Bicriteria approximation tradeoff for the node-cost budget problem.
  
• Guojun Li, Xiaotie Deng, Ying Xu:
  A polynomial-time approximation scheme for embedding hypergraph in a cycle.
  
• Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov:
  A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2.
  
• Sharon Marko, Dana Ron:
  Approximating the distance to properties in bounded-degree and general sparse graphs.
  
• Vincent Berry, Christophe Paul, Sylvain Guillemot, François Nicolas:
  Linear time 3-approximation for the MAST problem.
  
• Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu:
  Algorithms for distributional and adversarial pipelined filter ordering problems.
  

Volume 5, Number 3, July 2009

• Harold N. Gabow:
  Foreword to special issue on SODA 2007.
  
• Milan Ruzic:
  Making deterministic signatures quickly.
  
• Robert D. Carr, Goran Konjevod, Greg Little, Venkatesh Natarajan, Ojas Parekh:
  Compacting cuts: A new linear formulation for minimum cut.
  
• Yoav Giyora, Haim Kaplan:
  Optimal dynamic vertical ray shooting in rectilinear planar subdivisions.
  
• David Eppstein:
  Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition.
  
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam:
  Minimizing movement.
  
• Glencora Borradaile, Philip N. Klein, Claire Mathieu:
  An O(n log n) approximation scheme for Steiner tree in planar graphs.
  
• Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  Near-optimal algorithms for maximum constraint satisfaction problems.
  
• Matthew Andrews:
  Instability of FIFO in the permanent sessions model at arbitrarily small network loads.