Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 8 Issue 1, January 2012

Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems
Sudipto Guha, Kamesh Munagala
Article No.: 1
DOI: 10.1145/2071379.2071380

In several applications such as databases, planning, and sensor networks, parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system (as captured by some objective...

Online Optimization with Uncertain Information
Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi
Article No.: 2
DOI: 10.1145/2071379.2071381

We introduce a new framework for designing online algorithms that can incorporate additional information about the input sequence, while maintaining a reasonable competitive ratio if the additional information is incorrect. Within this framework,...

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert E. Tarjan
Article No.: 3
DOI: 10.1145/2071379.2071382

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in...

Cache-Oblivious Algorithms
Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran
Article No.: 4
DOI: 10.1145/2071379.2071383

This article presents asymptotically optimal algorithms for rectangular matrix transpose, fast Fourier transform (FFT), and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache...

Adversarial Queuing on the Multiple Access Channel
Bogdan S. Chlebus, Dariusz R. Kowalski, Mariusz A. Rokicki
Article No.: 5
DOI: 10.1145/2071379.2071384

We study deterministic broadcasting on multiple access channels when packets are injected continuously. The quality of service is considered in the framework of adversarial queuing. An adversary is determined by injection rate and burstiness, the...

Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching
Jianer Chen, Yang Liu, Songjian Lu, Sing-Hoi Sze, Fenghui Zhang
Article No.: 6
DOI: 10.1145/2071379.2071385

The research in the parameterized 3d-matching problem has yielded a number of new algorithmic techniques and an impressive list of improved algorithms. In this article, a new deterministic algorithm for the problem is developed that...

Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees
Sebastian Böcker, Quang Bao Anh Bui, Anke Truss
Article No.: 7
DOI: 10.1145/2071379.2071386

In computational phylogenetics, the problem of constructing a consensus tree for a given set of rooted input trees has frequently been addressed. In this article we study the Minimum-Flip Problem: the input trees are transformed into a...

Even Faster Exact Bandwidth
Marek Cygan, Marcin Pilipczuk
Article No.: 8
DOI: 10.1145/2071379.2071387

We deal with exact algorithms for Bandwidth, a long studied NP-hard problem. For a long time nothing better than the trivial O*(n!)1 exhaustive search was known. In 2000, Feige and Kilian [Feige 2000]...