enter search term and/or author name
SRPT optimally utilizes faster machines to minimize flow time
Eric Torng, Jason McCullough
Article No.: 1
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
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
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
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...
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
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...
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
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
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...
Rank-width was defined by Oum and Seymour  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
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...
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...
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...
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...