Experimental Algorithmics (JEA)


Search Issue
enter search term and/or author name


Journal of Experimental Algorithmics (JEA), Volume 7, 2002

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 105 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 n vertices and m edges in time O(nm log n). Our algorithm is a variant of the algorithm of Galil, Micali and Gabow...

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 WEAK-HEAPSORT algorithm we establish the general and practical relevant sequential sorting algorithm INDEX-WEAK-HEAPSORT with exactly n⌈log n⌉ - 2⌈log n +...

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...