Search ACM DL

Search Issue

enter search term and/or author name

**Heuristics on lattice basis reduction in practice**

Werner Backes, Susanne Wetzel

Page: 1

DOI: 10.1145/944618.944619

In this paper we provide a survey on LLL lattice basis reduction in practice. We introduce several new heuristics as to speed up known lattice basis reduction methods and improve the quality of the computed reduced lattice basis in practice. We...

**Parallelizing local search for CNF satisfiability using vectorization and PVM**

Kazuo Iwama, Daisuke Kawai, Shuichi Miyazaki, Yasuo Okabe, Jun Umemoto

Page: 2

DOI: 10.1145/944618.944620

The purpose of this paper is to speed up the local search algorithm for the CNF Satisfiability problem. Our basic strategy is to run some 10^{5} independent search paths simultaneously using PVM on a vector supercomputer VPP800, which...

**An experimental study of online scheduling algorithms**

Susanne Albers, Bianca Schröder

Page: 3

DOI: 10.1145/944618.944621

We present the first comprehensive experimental study of online algorithms for Graham's scheduling problem. Graham's scheduling problem is a fundamental problem in scheduling theory where a sequence of jobs has to be scheduled on *m* identical...

**Implementation of O(nmlogn) weighted matchings in general graphs**: the power of data structures

Kurt Mehlhorn, Guido Schäfer

Page: 4

DOI: 10.1145/944618.944622

We describe the implementation of an algorithm which solves the weighted matching problem in general graphs with

**Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons**

Stefan Edelkamp, Patrick Stiegeler

Page: 5

DOI: 10.1145/944618.944623

With refinements to the

**Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees**

Thomas Erlebach, Klaus Jansen

Page: 6

DOI: 10.1145/944618.944624

Given a set of weighted directed paths in a bidirected tree, the maximum weight edge-disjoint paths problem (MWEDP) is to select a subset of the given paths such that the selected paths are edge-disjoint and the total weight of the selected paths is...

**Portable list ranking**: an experimental study

Isabelle Guérin Lassous, Jens Gustedt

Page: 7

DOI: 10.1145/944618.944625

We present and analyze two portable algorithms for the List Ranking Problem in the Coarse Grained Multicomputer model (CGM). We report on implementations of these algorithms and experiments that were done with these on a variety of parallel and...

**Planar point location for large data sets**: to seek or not to seek

Jan Vahrenhold, Klaus H. Hinrichs

Page: 8

DOI: 10.1145/944618.944626

We present an algorithm for external memory planar point location that is both effective and easy to implement. The base algorithm is an external memory variant of the bucket method by Edahiro, Kokubo and Asano that is combined with Lee and Yang's...

**Efficient sorting using registers and caches**

Rajiv Wickremesinghe, Lars Arge, Jeffrey S. Chase, Jeffrey Scott Vitter

Page: 9

DOI: 10.1145/944618.944627

Modern computer systems have increasingly complex memory systems. Common machine models for algorithm analysis do not reflect many of the features of these systems, e.g., large register sets, lockup-free caches, cache hierarchies, associativity,...

**Finding the chromatic number by means of critical graphs**

Francine Herrmann, Alain Hertz

Page: 10

DOI: 10.1145/944618.944628

We propose a new exact algorithm for finding the chromatic number of a graph *G*. The algorithm attempts to determine the smallest possible induced subgraph *G'* of *G* which has the same chromatic number as *G*. Such a subgraph...

**Solving a "Hard" problem to approximate an "Easy" one**: heuristics for maximum matchings and maximum traveling salesman problems

Sándor P. Fekete, Henk Meijer, André Rohe, Walter Tietze

Page: 11

DOI: 10.1145/944618.944629

We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geometric duality relationship between MWMP, MTSP, and the...

**Relational concept learning by cooperative evolution**

Filippo Neri

Page: 12

DOI: 10.1145/944618.944630

Concept learning is a computationally demanding task that involves searching large hypothesis spaces containing candidate descriptions. Stochastic search combined with parallel processing provide a promising approach to successfully deal with such...