enter search term and/or author name
Approximate minimum enclosing balls in high dimensions using core-sets
Piyush Kumar, Joseph S. B. Mitchell, E. Alper Yildirim
Article No.: 1.1
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
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
Fast prefix matching of bounded strings
Adam L. Buchsbaum, Glenn S. Fowler, Balachannder Kirishnamurthy, Kiem-Phong Vo, Jia Wang
Article No.: 1.3
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
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
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
Article No: 2.3
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...