enter search term and/or author name
A hybrid dynamic programming approach to the biobjective binary knapsack problem
Charles Delort, Olivier Spanjaard
Article No.: 1.2
This article is devoted to a study of the impact of using bound sets in biobjective dynamic programming. This notion, introduced by Villareal and Karwan , has been independently revisited by Ehrgott and Gandibleux , as well as by Sourd...
We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally define the problem of finding...
Minimum time-dependent travel times with contraction hierarchies
G. Veit Batz, Robert Geisberger, Peter Sanders, Christian Vetter
Article No.: 1.4
Time-dependent road networks are represented as weighted graphs, where the weight of an edge depends on the time one passes through that edge. This way, we can model periodic congestions during rush hour and similar effects. In this work we deal...
Maximizing the quality index modularity has become one of the primary methods for identifying the clustering structure within a graph. Since many contemporary networks are not static but evolve over time, traditional static approaches can...
Data structures resilient to memory faults: An experimental study of dictionaries
Umberto Ferraro-Petrillo, Fabrizio Grandoni, Giuseppe F. Italiano
Article No.: 1.6
We address the problem of implementing data structures resilient to memory faults, which may arbitrarily corrupt memory locations. In this framework, we focus on the implementation of dictionaries and perform a thorough experimental study using a...
Compressed suffix trees: Efficient computation and storage of LCP-values
Simon Gog, Enno Ohlebusch
Article No.: 2.1
The suffix tree is a very important data structure in string processing, but typical implementations suffer from huge space consumption. In large-scale applications, compressed suffix trees (CSTs) are therefore used instead. A CST consists of...
A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
Stefan Canzar, Khaled Elbassioni, Julián Mestre
Article No.: 2.2
We study the interval constrained coloring problem, a combinatorial problem arising in the interpretation of data on protein structure emanating from experiments based on hydrogen/deuterium exchange and mass spectrometry. The problem captures the...
Optimal selection and sorting via dynamic programming
Article No.: 2.3
We show how to find optimal algorithms for the selection of one or more order statistics over a small set of numbers, and as an extreme case, complete sorting. The criterion is using the smallest number of comparisons; separate derivations are...
Exact online two-dimensional pattern matching using multiple pattern matching algorithms
Charalampos S. Kouzinopoulos, Konstantinos G. Margaritis
Article No.: 2.4
Baker and Bird and Baeza-Yates and Regnier are two of the most efficient and widely used algorithms for exact online two-dimensional pattern matching. Both use the automaton of the Aho-Corasick multiple pattern matching algorithm to locate all the...
Faster reaction mapping through improved naming techniques
Tina M. Kouri, Dinesh P. Mehta
Article No.: 2.5
Automated reaction mapping is an important tool in cheminformatics where it may be used to classify reactions or validate reaction mechanisms. The reaction mapping problem is known to be NP-Hard and may be formulated as an optimization problem. In...
On branching rules for convex mixed-integer nonlinear optimization
Pierre Bonami, Jon Lee, Sven Leyffer, Andreas Wächter
Article No.: 2.6
Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the...
Listing All Maximal Cliques in Large Sparse Real-World Graphs
David Eppstein, Maarten Löffler, Darren Strash
Article No.: 3.1
An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms
Chandrashekhar Nagarajan, David P. Williamson
Article No.: 3.2
In this article, we consider different incremental and hierarchical k-median algorithms with provable performance guarantees and compare their running times and quality of output solutions on different benchmark k-median datasets. We...