Fundamental Problems in Online, String, and Wireless Network Algorithms

Fundamental Problems in Online, String, and Wireless Network Algorithms (OSAW) is funded by a DKK 994,875.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

SAT Solving for Termination Proofs with Recursive Path Orders and Dependency Pairs.: Michael Codish, Jürgen Giesl, Peter Schneider-Kamp, and René Thiemann.
Journal of Automated Reasoning. Accepted for publication.
Proving Termination by Dependency Pairs and Inductive Theorem Proving.: Carsten Fuhs, Michael Parting, Jürgen Giesl, Peter Schneider-Kamp, and Stephan Swiderski.
Journal of Automated Reasoning. Accepted for publication.
A Theoretical Comparison of LRU and LRU-K.: Joan Boyar, Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
Acta Informatica. Accepted for publication.
A New Variable-Sized Bin Packing Problem.: Joan Boyar and Lene M. Favrholdt.
Journal of Scheduling. Accepted for publication.
The Cost of Cache-Oblivious Searching.: Michael A. Bender, Gerth S. Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro López-Ortiz.
Algorithmica. Accepted for publication.
Finding All Sorting Tandem Duplication Random Loss Operations.: M. Bernt, K.-Y. K.Y. Chen, M.C. Chen, A.-C. Chu, D. Merkle, H.-L. Wang, K.-M. Chao, and M. Middendorf.
Journal of Discrete Algorithms. Accepted for publication.
Online Variable-Sized Bin Packing with Conflicts.: Leah Epstein, Lene M. Favrholdt, and Asaf Levin.
Discrete Optimization. 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.
Automated Termination Proofs for Haskell by Term Rewriting.: Jürgen Giesl, Matthias Raffelsieper, Peter Schneider-Kamp, Stephan Swiderski, and René Thiemann.
ACM Transactions on Programming Languages and Systems, 33(2), 2010.
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, 47(4): 934-962, 2010.
Static Termination Analysis for Prolog Using Term Rewriting and SAT Solving.: Peter Schneider-Kamp.
KI - Künstliche Intelligenz, 24(1): 79-81, 2010.
A Parameter-Adaptive Dynamic Programming Approach for Inferring Cophylogenies.: Daniel Merkle, Martin Middendorf, and Nicolas Wieseke.
BMC Bioinformatics, 11(S-1): 60, 2010.
Automated Termination Analysis for Logic Programs with Cut.: Peter Schneider-Kamp, Jürgen Giesl, Thomas Ströder, Alexander Serebrenik, and René Thiemann.
Theory and Practice of Logic Programming, 10(4-6): 365-381, 2010.
Competitive Analysis of the Online Inventory Problem.: Kim S. Larsen and Sanne Wøhlk.
European Journal of Operational Research, 207(2): 685-696, 2010.
Tight Results for Next Fit and Worst Fit with Resource Augmentation.: Joan Boyar, Leah Epstein, and Asaf Levin.
Theoretical Computer Sience, 411: 2572-2580, 2010.
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, 411(16-18): 1734-1741, 2010.
Scheduling Jobs on Grid Processors.: Joan Boyar and Lene M. Favrholdt.
Algorithmica, 57(4): 819-847, 2010.
Priority Algorithms for Graph Optimization Problems.: Allan Borodin, Joan Boyar, Kim S. Larsen, and Nazanin Mirmohammadi.
Theoretical Computer Science, 411(1): 239-258, 2010.
Extended Shapes for the Combinatorial Design of RNA Sequences.: M. Hellmuth, D. Merkle, and M. Middendorf.
International Journal of Computational Biology and Drug Design, 2(4): 371-384, 2009.
Adapting to Dynamic Environments: Polyethism in Response Threshold Models for Social Insects.: Konrad Diwold, Daniel Merkle, and Martin Middendorf.
Advances in Complex Systems, 12(3): 327-346, 2009.
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.
Solving the Preserving Reversal Median Problem.: Matthias Bernt, Daniel Merkle, and Martin Middendorf.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(3): 332-347, 2008.
Evolution of Mitochondrial Gene Orders in Echinoderms.: M. Perseke, F. Fritsch, K. Ramsch, M. Bernt, D. Merkle, M. Middendorf, D. Bernhard, P.F. Stadler, and M. Schlegel.
Molecular Phylogenetics and Evolution, 47(2): 855-864, 2008.
Swarm Intelligence and Signal Processing.: D. Merkle and M. Middendorf.
IEEE Signal Processing Magazine, 25(6): 152-158, 2008.
Protein Folding in the HP-Model Solved With a Hybrid Population Based ACO Algorithm.: T. Thalheim, D. Merkle, and M. Middendorf.
IAENG International Journal of Computer Science, 35(3): 291-300, 2008.
Molecular Docking with Multi-Objective Particle Swarm Optimization.: Stefan Janson, Daniel Merkle, and Martin Middendorf.
Applied Soft Computing, 8(1): 666-675, 2008.
Stability and Performance of Ant Queue Inspired Task Division Methods.: A. Scheidler, D. Merkle, and M. Middendorf.
Theory in Biosciences, 127(2): 149-161, 2008.
Self-Organized Task Allocation for Service Tasks in Computing Systems with Reconfigurable Components.: A. Scheidler, D. Merkle, and M. Middendorf.
Journal of Mathematical Modelling and Algorithms, 2(7): 237-254, 2008.
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

Optimal Base Encodings for Pseudo-Boolean Constraints.: Michael Codish, Yoav Fekete, Carsten Fuhs, and Peter Schneider-Kamp.
In Seventeenth International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science. Springer. Accepted for publication.
List Factoring and Relative Worst Order Analysis.: Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
In Eighth Workshop on Approximation and Online Algorithms, Lecture Notes in Computer Science. Springer. Accepted for publication.
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, Lecture Notes in Computer Science. Springer. 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.
Loops under Strategies ... Continued.: René Thiemann, Christian Sternagel, Jürgen Giesl, and Peter Schneider-Kamp.
In 1st International Workshop on Strategies in Rewriting, Proving, and Programming, volume 44 of Electronic Proceedings in Theoretical Computer Science, pages 51-65, 2010.
Synthesizing Shortest Straight-Line Programs over GF(2) using SAT.: Carsten Fuhs and Peter Schneider-Kamp.
In Thirteenth International Conference on Theory and Applications of Satisfiability Testing, volume 6175 of Lecture Notes in Computer Science, pages 71-84. Springer, 2010.
The Dependency Triple Framework for Termination of Logic Programs.: Peter Schneider-Kamp, Jürgen Giesl, and Manh Thang Nguyen.
In Nineteenth International Symposium on Logic-Based Program Synthesis and Transformation, volume 6037 of Lecture Notes in Computer Science, pages 37-51. Springer, 2010.
Lazy Abstraction for Size-Change Termination.: Michael Codish, Carsten Fuhs, Jürgen Giesl, and Peter Schneider-Kamp.
In Seventeenth International Conference on Logic for Programming, Artificial Intelligence and Reasoning, volume 6397 of Lecture Notes in Computer Science, pages 217-232. Springer, 2010.
A New Combinational Logic Minimization Technique with Applications to Cryptology.: Joan Boyar and René Peralta.
In 9th International Symposium on Experimental Algorithms, volume 6949 of Lecture Notes in Computer Science, pages 178-189. Springer, 2010.
Better Bounds on Online Unit Clustering.: Martin R. Ehmsen and Kim S. Larsen.
In Twelfth Scandinavian Symposium and Workshops on Algorithm Theory, volume 6139 of Lecture Notes in Computer Science, pages 371-382. Springer, 2010.
An O (log log n )-Competitive Binary Search Tree with Optimal Worst-Case Access Times.: Prosenjit Bose, Karim Douïeb, Vida Dujmovic, and Rolf Fagerberg.
In Twelfth Scandinavian Symposium and Workshops on Algorithm Theory, volume 6139 of Lecture Notes in Computer Science, pages 38-49. Springer, 2010.
Finding All Sorting Tandem Duplication Random Loss Operations.: Matthias Bernt, Ming-Chiang Chen, Daniel Merkle, Hung-Lung Wang, Kun-Mao Chao, and Martin Middendorf.
In 20th Annual Symposium on Combinatorial Pattern Matching, volume 5577 of Lecture Notes in Computer Science, pages 301-313. Springer, 2009.
The Influence of Dynamic Environments on Polyethism in Response Threshold Models for Social Insects.: K. Diwold, D. Merkle, and M. Middendorf.
In 8th German Workshop on Artificial Life, pages 37-48. IOS Press, 2009.
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 Design of RNA Sequences for Realizing Extended Shapes.: Marc Hellmuth, Daniel Merkle, and Martin Middendorf.
In International Joint Conferences on System Biology, Bioinformatics and Intelligent Computing, pages 167-173. IEEE Computer Society, 2009.
Emergent Sorting in Networks of Router Agents.: Alexander Scheidler, Christian Blum, Daniel Merkle, and Martin Middendorf.
In Seventh International Conference on Ant Colony Optimization and Swarm Intelligence, volume 5217 of Lecture Notes in Computer Science, pages 299-306. Springer, 2008.
Learning from House-Hunting Ants: Collective Decision-Making in Organic Computing Systems.: Arne Brutschy, Alexander Scheidler, Daniel Merkle, and Martin Middendorf.
In Seventh International Conference on Ant Colony Optimization and Swarm Intelligence, volume 5217 of Lecture Notes in Computer Science, pages 96-107. Springer, 2008.
An Algorithm for Inferring Mitogenome Rearrangements in a Phylogenetic Tree.: Matthias Bernt, Daniel Merkle, and Martin Middendorf.
In 6th RECOMB Comparative Genomics Satellite Workshop, volume 5267 of Lecture Notes in Computer Science, pages 143-157. Springer, 2008.
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 (entries, chapters, and editorials)

12th International Conference on the Synthesis and Simulation of Living Systems.: H. Fellermann, Mark Dörr, M. Hanczyc, L. Laursen, S. Maurer, D. Merkle, P.-A. Monnard, K. Stoy, and S. Rasmussen, editors.
MIT Press, 2010.
Editorial: Artificial Life.: K. Klemm, D. Merkle, and E. Olbrich.
Advances in Complex Systems, 12(3), 2009.
Special Issue on Ant Colony Optimization.: K.F. Doerner, D. Merkle, and T. Stützle.
Swarm Intelligence, 3(1): 1-2, 2009.
8th German Workshop on Artificial Life.: K. Klemm, D. Merkle, and E. Olbrich, editors.
IOS Press, 2009.
Congestion Control in Ant Like Moving Agent Systems.: A. Scheidler, D. Merkle, and M. Middendorf.
In Hinchey et al., editor, Biologically-Inspired Collaborative Computing, volume 268 of IFIP International Federation for Information Processing, pages 33-43. Springer, 2008.
Self-Adaptive Worker-Helper Systems with Self-Organized Task Allocation.: A. Scheidler, D. Merkle, and M. Middendorf.
In R.P. Würtz, editor, Organic Computing. Springer, 2008.
Organic Computing and Swarm Intelligence.: Daniel Merkle, Martin Middendorf, and Alexander Scheidler.
In Christian Blum and Daniel Merkle, editors, Swarm Intelligence: Introduction and Applications, Natural Computing Series, pages 253-281, 2008.
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.
Swarm Intelligence: Introduction and Application.: C. Blum and D. Merkle, editors.
Natural Computing Series. Springer, 2008.

Additional Manuscripts (submissions)

On the Absolute Approximation Ratio for First Fit and Related Results.: Joan Boyar, Gyorgy Dósa, and Leah Epstein.
In preparation.
A Comparison of Performance Measures for Online Algorithms.: Joan Boyar, Sandy Irani, and Kim S. Larsen.
In preparation.
Online Greedy Matching from a New Perspective.: Lene M. Favrholdt and Martin Vatshelle.
In preparation.
A Technique for Exact Computation of Precoloring Extension on Interval Graphs.: Martin R. Ehmsen and Kim S. Larsen.
In preparation.