Fundamental Problems in Online, String, and Wireless Network Algorithms

Fundamental Problems in Online, String, and Wireless Network Algorithms (OSAW) is funded by a DKK 900,000.00 grant from the Danish Natural Science Research Council from January 1, 2008 through December 31, 2010.

Participants

Environment

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The group of participants are associated with the Ph.D. School on Efficient Algorithms and High Quality Solutions.

Publications

Peer-Reviewed International Journal Articles

Comparing First-Fit and Next-Fit for Online Edge Coloring.: Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, and Rodica Mihai.
Theoretical Computer Science. Accepted for publication.
Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model.: M. A. Bender, G. S. Brodal, R. Fagerberg, R. Jacob, and E. Vicari.
Theory of Computing Systems. Accepted for publication.
Comparing Online Algorithms for Bin Packing Problems.: Leah Epstein, Lene M. Favrholdt, and Jens S. Kohrt.
Journal of Scheduling. Accepted for publication.
Polytool: Polynomial Interpretations as a Basis for Termination Analysis of Logic Programs.: Manh Thang Nguyen, Danny De Schreye, Jürgen Giesl, and Peter Schneider-Kamp.
Theory and Practice of Logic Programming. Accepted for publication.
Scheduling jobs on Grid processors.: Joan Boyar and Lene M. Favrholdt.
Algorithmica. Accepted for publication.
Priority Algorithms for Graph Optimization Problems.: Allan Borodin, Joan Boyar, Kim S. Larsen, and Nazanin Mirmohammadi.
Theoretical Computer Science, 411(1): 239-258, 2010.
Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.: Philip Bille, Rolf Fagerberg, and Inge Li Gørtz.
ACM Transactions on Algorithms, 6(1): 1-14, 2009.
Automated Termination Proofs for Logic Programs by Term Rewriting.: Peter Schneider-Kamp, Jürgen Giesl, Alexander Serebrenik, and René Thiemann.
ACM Transactions on Computational Logic, 11(1): 1-52, 2009.
On the Adaptiveness of Quicksort.: Gerth Stølting Brodal, Rolf Fagerberg, and Gabriel Moruz.
ACM Journal of Experimental Algorithmics, 12, 2008.
The Relative Worst Order Ratio Applied to Seat Reservation.: Joan Boyar and Paul Medvedev.
ACM Transactions on Algorithms, 4(4), 2008. Article 48, 22 pages.
Computing the All-Pairs Quartet Distance on a Set of Evolutionary Trees.: M. Stissing, Thomas Mailund, Christian N. S. Pedersen, Gerth Stølting Brodal, and Rolf Fagerberg.
Journal of Bioinformatics and Computational Biology, 6(1): 37-50, 2008.
Tight Bounds For the Multiplicative Complexity of Symmetric Functions.: Joan Boyar and René Peralta.
Theoretical Computer Science, 396(1-3): 223-246, 2008.

Peer-Reviewed International Conference Articles

Parameterized Analysis of Paging and List Update Algorithms.: Reza Dorrigiv, Martin R. Ehmsen, and Alejandro López-Ortiz.
In 7th International Workshop on Approximation and Online Algorithms. Accepted for publication.
The Dependency Triple Framework for Termination of Logic Programs.: Peter Schneider-Kamp, Jürgen Giesl, and Manh Thang Nguyen.
In 19th International Symposium on Logic-Based Program Synthesis and Transformation, Lecture Notes in Computer Science. Springer. Accepted for publication.
Online Sorted Range Reporting.: Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro López-Ortiz.
In 20th International Symposium Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 173-182. Springer, 2009.
A Comparison of Performance Measures for Online Algorithms.: Joan Boyar, Sandy Irani, and Kim S. Larsen.
In Eleventh International Algorithms and Data Structures Symposium, volume 5664 of Lecture Notes in Computer Science, pages 119-130. Springer, 2009.
Termination Analysis by Dependency Pairs and Inductive Theorem Proving.: Stephan Swiderski, Michael Parting, Jürgen Giesl, Carsten Fuhs, and Peter Schneider-Kamp.
In 22nd International Conference on Automated Deduction, volume 5663 of Lecture Notes in Artificial Intelligence, pages 322-338. Springer, 2009.
Proving Termination of Integer Term Rewriting.: Carsten Fuhs, Jürgen Giesl, Martin Plücker, Peter Schneider-Kamp, and Stephan Falke.
In 20th International Conference on Rewriting Techniques and Applications, volume 5595 of Lecture Notes in Computer Science, pages 32-47. Springer, 2009.
On the Shortest Linear Straight-Line Program for Computing Linear Forms.: Joan Boyar and René Peralta.
In 33rd International Symposium on Mathematical Foundations of Computer Science, volume 5162 of Lecture Notes in Computer Science, pages 168-179. Springer, 2008.
Comparing First-Fit and Next-Fit for Online Edge Coloring.: Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, and Rodica Mihai.
In 19th International Symposium on Algorithms and Computation, volume 5369 of Lecture Notes in Computer Science, pages 89-99. Springer, 2008.

Book Contributions

String Sorting.: Rolf Fagerberg.
In Ming-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2008.
Cache-oblivious Model.: Rolf Fagerberg.
In Ming-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2008.
Cache-oblivious B-Tree.: Rolf Fagerberg.
In Ming-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2008.