Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 6 Issue 3, June 2010

Finding heaviest H-subgraphs in real weighted graphs, with applications
Virginia Vassilevska, Ryan Williams, Raphael Yuster
Article No.: 44
DOI: 10.1145/1798596.1798597

For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. Our main results are new strongly polynomial...

An explicit universal cycle for the (n-1)-permutations of an n-set
Frank Ruskey, Aaron Williams
Article No.: 45
DOI: 10.1145/1798596.1798598

We show how to construct an explicit Hamilton cycle in the directed Cayley graph &Cayrarr;({σn, σn−1}: Sn), where σk is the rotation (1 2...

An approximation algorithm for the maximum leaf spanning arborescence problem
Matthew Drescher, Adrian Vetta
Article No.: 46
DOI: 10.1145/1798596.1798599

We present an O(&sqrt;opt)-approximation algorithm for the maximum leaf spanning arborescence problem, where opt is the number of leaves in an optimal spanning arborescence. The result is based upon an O(1)-approximation algorithm...

The directed circular arrangement problem
Joseph (Seffi) Naor, Roy Schwartz
Article No.: 47
DOI: 10.1145/1798596.1798600

We consider the problem of embedding a directed graph onto evenly spaced points on a circle while minimizing the total weighted edge length. We present the first poly-logarithmic approximation factor algorithm for this problem which yields an...

Distributed error confinement
Yossi Azar, Shay Kutten, Boaz Patt-Shamir
Article No.: 48
DOI: 10.1145/1798596.1798601

We study error confinement in distributed applications, which can be viewed as an extreme case of various fault locality notions studied in the past. Error confinement means that to the external observer, only nodes that were directly hit by a...

Achieving anonymity via clustering
Gagan Aggarwal, Rina Panigrahy, Tomás Feder, Dilys Thomas, Krishnaram Kenthapadi, Samir Khuller, An Zhu
Article No.: 49
DOI: 10.1145/1798596.1798602

Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of deidentifying records is to remove identifying fields such as...

Competitive weighted throughput analysis of greedy protocols on DAGs
Eyal Gordon, Adi Rosén
Article No.: 50
DOI: 10.1145/1798596.1798603

The combination of the buffer sizes of routers deployed in the Internet, and the Internet traffic itself, leads routinely to the dropping of packets. Motivated by this, we are interested in the problem of maximizing the throughput of protocols...

A near-optimal algorithm for estimating the entropy of a stream
Amit Chakrabarti, Graham Cormode, Andrew Mcgregor
Article No.: 51
DOI: 10.1145/1798596.1798604

We describe a simple algorithm for approximating the empirical entropy of a stream of m values up to a multiplicative factor of (1+ε) using a single pass, O−2 log (δ−1) log...

Approximating the distance to monotonicity in high dimensions
Shahar Fattal, Dana Ron
Article No.: 52
DOI: 10.1145/1798596.1798605

In this article we study the problem of approximating the distance of a function f: [n]dR to monotonicity where [n] = {1,&ldots;,n} and R is some fully ordered range....

Adaptive sampling strategies for quickselects
Conrado Martínez, Daniel Panario, Alfredo Viola
Article No.: 53
DOI: 10.1145/1798596.1798606

Quickselect with median-of-3 is largely used in practice and its behavior is fairly well understood. However, the following natural adaptive variant, which we call proportion-from-3, had not been previously analyzed: “choose as pivot...

Balanced families of perfect hash functions and their applications
Noga Alon, Shai Gutner
Article No.: 54
DOI: 10.1145/1798596.1798607

The construction of perfect hash functions is a well-studied topic. In this article, this concept is generalized with the following definition. We say that a family of functions from [n] to [k] is a δ-balanced...

Ordering by weighted number of wins gives a good ranking for weighted tournaments
Don Coppersmith, Lisa K. Fleischer, Atri Rurda
Article No.: 55
DOI: 10.1145/1798596.1798608

We consider the following simple algorithm for feedback arc set problem in weighted tournaments: order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of 5 if the weights satisfy probability...

Approximating corridors and tours via restriction and relaxation techniques
Arturo Gonzalez-Gutierrez, Teofilo F. Gonzalez
Article No.: 56
DOI: 10.1145/1798596.1798609

Given a rectangular boundary partitioned into rectangles, the Minimum-Length Corridor (MLC-R) problem consists of finding a corridor of least total length. A corridor is a set of connected line segments, each of which must lie along the line...