Search ACM DL

Search Issue

enter search term and/or author name

Section:

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

**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: **Special Issue With Selected Articles from the Fourth Workshop on Algorithms and Engineering**

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