ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 9 Issue 4, September 2013

Morphing orthogonal planar graph drawings
Therese Biedl, Anna Lubiw, Mark Petrick, Michael Spriggs
Article No.: 29
DOI: 10.1145/2500118

We give an algorithm to morph between two planar orthogonal drawings of a graph, preserving planarity and orthogonality. The morph uses a quadratic number of steps, where each step is a linear morph (a linear interpolation between two drawings)....

Finding small separators in linear time via treewidth reduction
Dáaniel Marx, Barry O'sullivan, Igor Razgon
Article No.: 30
DOI: 10.1145/2500119

We present a method for reducing the treewidth of a graph while preserving all of its minimal s-t separators up to a certain fixed size k. This technique allows us to solve s-t Cut and...

Optimal lower bounds for projective list update algorithms
Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel
Article No.: 31
DOI: 10.1145/2500120

The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized...

Submodular secretary problem and extensions
Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi, Morteza Zadimoghaddam
Article No.: 32
DOI: 10.1145/2500121

Online auction is the essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future...

On the matrix berlekamp-massey algorithm
Erich Kaltofen, George Yuhasz
Article No.: 33
DOI: 10.1145/2500122

We analyze the Matrix Berlekamp/Massey algorithm, which generalizes the Berlekamp/Massey algorithm [Massey 1969] for computing linear generators of scalar sequences. The Matrix Berlekamp/Massey algorithm computes a minimal matrix generator of a...

Corrigendum: Improved results for data migration and open shop scheduling
Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai
Article No.: 34
DOI: 10.1145/2500123

In Gandhi et al. [2006], we gave an algorithm for the data migration and non-deterministic open shop scheduling problems in the minimum sum version, that was claimed to achieve a 5.06-approximation. Unfortunately, it was pointed to us by Maxim...