Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 5 Issue 1, November 2008

SRPT optimally utilizes faster machines to minimize flow time
Eric Torng, Jason McCullough
Article No.: 1
DOI: 10.1145/1435375.1435376

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...

Online nonpreemptive scheduling of equal-length jobs on two identical machines
Michael H. Goldwasser, Mark Pedigo
Article No.: 2
DOI: 10.1145/1435375.1435377

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...

Competitive buffer management for shared-memory switches
William Aiello, Alex Kesselman, Yishay Mansour
Article No.: 3
DOI: 10.1145/1435375.1435378

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...

Kinetic and dynamic data structures for closest pair and all nearest neighbors
Pankaj K. Agarwal, Haim Kaplan, Micha Sharir
Article No.: 4
DOI: 10.1145/1435375.1435379

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...

Algorithms for center and Tverberg points
Pankaj K. Agarwal, Micha Sharir, Emo Welzl
Article No.: 5
DOI: 10.1145/1435375.1435380

Given a set S of n points in R3, a point x in R3 is called center point of S if every closed halfspace whose bounding hyperplane passes through x contains at least ⌈n/4⌉...

Distributed weighted vertex cover via maximal matchings
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi
Article No.: 6
DOI: 10.1145/1435375.1435381

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...

On hard instances of approximate vertex cover
Sundar Vishwanathan
Article No.: 7
DOI: 10.1145/1435375.1435382

We show that if there is a 2 − &epsis; approximation algorithm for vertex cover on graphs with vector chromatic number at most 2 + δ, then there is a 2 − f(&epsis;, δ) approximation algorithm for vertex cover for all...

Combinatorial dominance guarantees for problems with infeasible solutions
Daniel Berend, Steven S. Skiena, Yochai Twitto
Article No.: 8
DOI: 10.1145/1435375.1435383

The design and analysis of approximation algorithms for 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 combinatorial dominance guarantee...

Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications
Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, Alexey A. Stepanov
Article No.: 9
DOI: 10.1145/1435375.1435384

We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O(1.7159n). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a...

Approximating rank-width and clique-width quickly
Sang-Il Oum
Article No.: 10
DOI: 10.1145/1435375.1435385

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...

Structure and linear-time recognition of 4-leaf powers
Andreas Brandstädt, Van Bang Le, R. Sritharan
Article No.: 11
DOI: 10.1145/1435375.1435386

A graph G is the k-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-leaf...

On the minimum common integer partition problem
Xin Chen, Lan Liu, Zheng Liu, Tao Jiang
Article No.: 12
DOI: 10.1145/1435375.1435387

We introduce a new combinatorial optimization problem in this article, called the minimum common integer partition (MCIP) problem, which was inspired by computational biology applications including ortholog assignment and DNA fingerprint...

On an infinite family of solvable Hanoi graphs
Dany Azriel, Noam Solomon, Shay Solomon
Article No.: 13
DOI: 10.1145/1435375.1435388

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...

Multipartite priority queues
Amr Elmasry, Claus Jensen, Jyrki Katajainen
Article No.: 14
DOI: 10.1145/1435375.1435389

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...