Search ACM DL

Search Issue

enter search term and/or author name

**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}}: S_{n}), 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*]^{d} → *R* 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...
*