Search ACM DL

Search Issue

enter search term and/or author name

**Adaptive data structures for IP lookups**

Ioannis Ioannidis, Mikhail Atallah, Ananth Grama

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

A. McMahon, N. Lesh, M. Mitzenmacher, J. Marks

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

Thomas Willhalm, Dorothea Wagner, 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, Mohammad Ali Safari, Hossein Sheikhattar, Mehdi Mirzazadeh

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

**Using random sampling to build approximate tries for efficient string sorting**

Justin Zobel, Ranjan Sinha

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

F. K. Miyazawa, Luis A. A. Meira, Evandro C. Bracht

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

Guido Araujo, Cid C. de Souza, Andre M. Lima, 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**

Stavros G. Kolliopoulos, Jingde Du

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

Thomas Willhalm, Frank Schulz, Dorothea Wagner, Martin Holzer

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

Kimmo Fredriksson, Heikki Hyyrö, 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**

Jürgen Branke, Alexandre Tarassov, Nikola S. Nikolov

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, Rajiv Raman, Sriram Penumatcha

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

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