enter search term and/or author name
Adaptive data structures for IP lookups
Ioannis Ioannidis, Mikhail Atallah, Ananth Grama
Article No.: 1.1
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
A. McMahon, N. Lesh, M. Mitzenmacher, J. Marks
Article No.: 1.2
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
Thomas Willhalm, Dorothea Wagner, Christos Zaroliagis
Article No.: 1.3
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, Mohammad Ali Safari, Hossein Sheikhattar, Mehdi Mirzazadeh
Article No.: 1.4
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...
Using random sampling to build approximate tries for efficient string sorting
Justin Zobel, Ranjan Sinha
Article No.: 2.10
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...
A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique
F. K. Miyazawa, Luis A. A. Meira, Evandro C. Bracht
Article No.: 2.11
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
Guido Araujo, Cid C. de Souza, Andre M. Lima, Nahri B. Moreano
Article No.: 2.2
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
Stavros G. Kolliopoulos, Jingde Du
Article No.: 2.3
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
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
Thomas Willhalm, Frank Schulz, Dorothea Wagner, Martin Holzer
Article No.: 2.5
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
Kimmo Fredriksson, Heikki Hyyrö, Gonzalo Navarro
Article No.: 2.6
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
Jürgen Branke, Alexandre Tarassov, Nikola S. Nikolov
Article No.: 2.7
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, Rajiv Raman, Sriram Penumatcha
Article No.: 2.8
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:V → N, the interval-coloring...
A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem
Luiz S. Ochi, Haroldo G. Santos, Marcone J.F. Souza
Article No.: 2.9
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...