Search ACM DL

Search Issue

enter search term and/or author name

**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 R^{3}, a point *x* in R^{3} 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.7159^{n}). 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...
*