ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 8, 2003

Section: Special Issue With Selected Articles from the Fourth Workshop on Algorithms and Engineering

Approximate minimum enclosing balls in high dimensions using core-sets
Piyush Kumar, Joseph S. B. Mitchell, E. Alper Yildirim
Article No.: 1.1
DOI: 10.1145/996546.996548
We study the minimum enclosing ball (MEB) problem for sets of points or balls in high dimensions. Using techniques of second-order cone programming and "core-sets", we have developed (1 + ε)-approximation algorithms that perform well in...

I/O-efficient point location using persistent B-trees
Lars Arge, Andrew Danner, Sha-Mayn Teh
Article No.: 1.2
DOI: 10.1145/996546.996549
We present an external planar point location data structure that is I/O-efficient both in theory and practice.The developed structure uses linear space and answers a query in optimal O(log BN) I/Os, where B is the disk...

Fast prefix matching of bounded strings
Adam L. Buchsbaum, Glenn S. Fowler, Balachannder Kirishnamurthy, Kiem-Phong Vo, Jia Wang
Article No.: 1.3
DOI: 10.1145/996546.996550
Longest Prefix Matching (LPM) is the problem of finding which string from a given set is the longest prefix of another, given string. LPM is a core problem in many applications, including IP routing, network data clustering, and telephone network...

Section: Regular Articles

A learning algorithm for the longest common subsequence problem
Eric A. Breimer, Mark K. Goldberg, Darren T. Lim
Article No.: 2.1
DOI: 10.1145/996546.996552
We present an experimental study of a learning algorithm for the longest common subsequence problem, LCS. Given an arbitrary input domain, the algorithm learns an LCS-procedure tailored to that domain. The learning is done with the help...

A blocked all-pairs shortest-paths algorithm
Gayathri Venkataraman, Sartaj Sahni, Srabani Mukhopadhyaya
Article No.: 2.2
DOI: 10.1145/996546.996553
We propose a blocked version of Floyd's all-pairs shortest-paths algorithm. The blocked algorithm makes better utilization of cache than does Floyd's original algorithm. Experiments indicate that the blocked algorithm delivers a speedup (relative to...

Experiments on the minimum linear arrangement problem
Jordi Petit
Article No: 2.3
DOI: 10.1145/996546.996554
This paper deals with the Minimum Linear Arrangement problem from an experimental point of view. Using a testsuite of sparse graphs, we experimentally compare several algorithms to obtain upper and lower bounds for this problem. The algorithms...