ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 10, 2005



Section: 1 - Regular Articles

Adaptive data structures for IP lookups
Ioannis Ioannidis, Ananth Grama, Mikhail Atallah
Article No.: 1.1
DOI: 10.1145/1064546.1064548
The problem of efficient data structures for IP lookups has been well studied in the literature. Techniques such as LC tries and extensible hashing are commonly used. In this paper, we address the problem of generalizing LC tries, based on traces of...

New heuristic and interactive approaches to 2D rectangular strip packing
N. Lesh, J. Marks, A. McMahon, M. Mitzenmacher
Article No.: 1.2
DOI: 10.1145/1064546.1083322
In this paper, we consider the two-dimensional rectangular strip packing problem. A standard simple heuristic, Bottom-Left-Decreasing (BLD), has been shown to perform quite well in practice. We introduce and demonstrate the effectiveness of BLD*,...

Geometric containers for efficient shortest-path computation
Dorothea Wagner, Thomas Willhalm, Christos Zaroliagis
Article No.: 1.3
DOI: 10.1145/1064546.1103378
A fundamental approach in finding efficiently best routes or optimal itineraries in traffic information systems is to reduce the search space (part of graph visited) of the most commonly used shortest path routine (Dijkstra's algorithm) on a suitably...

Fast string sorting using order-preserving compression
Alejandro López-Ortiz, Mehdi Mirzazadeh, Mohammad Ali Safari, Hossein Sheikhattar
Article No.: 1.4
DOI: 10.1145/1064546.1180611
We give experimental evidence for the benefits of order-preserving compression in sorting algorithms. While, in general, any algorithm might benefit from compressed data because of reduced paging requirements, we identified two natural candidates...

Section: 1 - Regular Articles

Using random sampling to build approximate tries for efficient string sorting
Ranjan Sinha, Justin Zobel
Article No.: 2.10
DOI: 10.1145/1064546.1180622
Algorithms for sorting large datasets can be made more efficient with careful use of memory hierarchies and reduction in the number of costly memory accesses. In earlier work, we introduced burstsort, a new string-sorting algorithm that on large sets...

Preface
Celso C. Ribeiro, Simone L. Martins
Article No.: 2.1
DOI: 10.1145/1064546.1180620

A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique
Evandro C. Bracht, Luis A. A. Meira, F. K. Miyazawa
Article No.: 2.11
DOI: 10.1145/1064546.1180623
We consider the uniform metric labeling problem. This NP-hard problem considers how to assign objects to labels respecting assignment and separation costs. The known approximation algorithms are based on solutions of large linear programs and are...

The datapath merging problem in reconfigurable systems: Complexity, dual bounds and heuristic evaluation
Cid C. de Souza, Andre M. Lima, Guido Araujo, Nahri B. Moreano
Article No.: 2.2
DOI: 10.1145/1064546.1180613
In this paper, we investigate the data path merging problem (DPM) in reconfigurable systems. DPM is modeled as a graph optimization problem and is shown to be NP-hard. An Integer Programming (IP) formulation of the problem is presented and...

Implementing approximation algorithms for the single-source unsplittable flow problem
Jingde Du, Stavros G. Kolliopoulos
Article No.: 2.3
DOI: 10.1145/1064546.1180614
In the single-source unsplittable flow problem, commodities must be routed simultaneously from a common source vertex to certain sinks in a given graph with edge capacities. The demand of each commodity must be routed along a single path so...

Improving the performance of multidimensional search using fingers
Amalia Duch, Conrado Martínez
Article No.: 2.4
DOI: 10.1145/1064546.1180615
We propose two variants of K-d trees where fingers are used to improve the performance of orthogonal range search and nearest neighbor queries when they exhibit locality of reference. The experiments show that the second alternative...

Combining speed-up techniques for shortest-path computations
Martin Holzer, Frank Schulz, Dorothea Wagner, Thomas Willhalm
Article No.: 2.5
DOI: 10.1145/1064546.1180616
In practice, computing a shortest path from one node to another in a directed graph is a very common task. This problem is classically solved by Dijkstra's algorithm. Many techniques are known to speed up this algorithm heuristically, while...

Increased bit-parallelism for approximate and multiple string matching
Heikki Hyyrö, Kimmo Fredriksson, Gonzalo Navarro
Article No.: 2.6
DOI: 10.1145/1064546.1180617
Bit-parallelism permits executing several operations simultaneously over a set of bits or numbers stored in a single computer word. This technique permits searching for the approximate occurrences of a pattern of length m in a text of length...

In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes
Nikola S. Nikolov, Alexandre Tarassov, Jürgen Branke
Article No.: 2.7
DOI: 10.1145/1064546.1180618
We propose two fast heuristics for solving the NP-hard problem of graph layering with the minimum width and consideration of dummy nodes. Our heuristics can be used at the layer-assignment phase of the Sugiyama method for drawing of directed graphs....

Approximating interval coloring and max-coloring in chordal graphs
Sriram V. Pemmaraju, Sriram Penumatcha, Rajiv Raman
Article No.: 2.8
DOI: 10.1145/1064546.1180619
We consider two coloring problems: interval coloring and max-coloring for chordal graphs. Given a graph G = (V, E) and positive-integral vertex weights w:VN, the interval-coloring...

A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem
Haroldo G. Santos, Luiz S. Ochi, Marcone J.F. Souza
Article No.: 2.9
DOI: 10.1145/1064546.1180621
The Class/Teacher Timetabling Problem (CTTP) deals with the weekly scheduling of encounters between teachers and classes of an educational institution. Since CTTP is a NP-hard problem for nearly all of its variants, the use of heuristic methods for...