On-Line Algorithms, Bioinformatics, and SAT Solving

On-Line Algorithms, Bioinformatics, and SAT Solving (OLABS) is funded by a DKK 1,267,200.00 grant from the Danish Natural Science Research Council from January 1, 2011 through December 31, 2013.

Participants

PhD students

Jakob L. Andersen
Marie G. Christ (graduated February 2014)
Magnus G. Find
Sushmita Gupta (graduated November 2013)
Felix P. Hargreaves
Christian Kudahl
Abyayananda Maiti (graduated November 2013)
Jesper With Mikkelsen
Philipp Peters (graduated November, 2013)

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 Research Training Program in Computer Science.

Publications since January 1, 2011

Peer-Reviewed International Journal Articles

A Comparison of Performance Measures for Online Algorithms: Joan Boyar, Sandy Irani, and Kim S. Larsen
Algorithmica. Accepted for publication.
A Comparison of Performance Measures via Online Search.: Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
Theoretical Computer Science, 532: 2-13, 2014.
Online Multi-Coloring on the Path Revisited.: Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Acta Informatica, 50(5-6): 343-357, 2013.
Navigating the Chemical Space of HCN Polymerization and Hydrolysis: Guiding Graph Grammars by Mass SpectrometryData.: Jakob Lykke Andersen, Tommy Andersen, Christoph Flamm, Martin Hanczyc, Daniel Merkle and Peter F Stadler.
Entropy. Accepted for publication (subject to minor revisions).
Generic Strategies for Chemical Space Exploration.: Jakob Lykke Andersen, Christoph Flamm, Daniel Merkle and Peter F Stadler.
International Journal of Computational Biology and Drug Design. Accepted for publication.
A Practical O(n log² n) Time Algorithm for Computing the Triplet Distance on Binary Trees.: Andreas Sand, Gerth S. Brodal, Rolf Fagerberg, Christian N.S. Pedersen, Thomas Mailund.
BMC Bioinformatics. Accepted for publication.
Inferring Chemical Reaction Patterns Using Rule Composition in Graph Grammars.: Jakob Lykke Andersen, Christoph Flamm, Daniel Merkle and Peter F Stadler.
Journal of Systems Chemistry. 4(4), 2013
A Technique for Exact Computation of Precoloring Extension on Interval Graphs.: Martin R. Ehmsen and Kim S. Larsen.
International Journal of Foundations of Computer Science, 24(1): 109-122, 2013.
Logic Minimization Techniques with Applications to Cryptology.: Joan Boyar and René Peralta.
Journal of Cryptology. 26: 280-312, 2013.
DOI: 10.1007/s00145-012-9124-7.
On the Absolute Approximation Ratio for First Fit and Related Results.: Joan Boyar, György Dósa, Leah Epstein.
Discrete Applied Mathematics, 160(13-14): 1914-1923, 2012.
CATCHprofiles: Clustering and Alignment Tool for ChIP Profiles.: Fiona G. G. Nielsen, Kasper G. Markus, Rune M. Friborg, Lene M. Favrholdt, Hendrik G. Stunnenberg, and Martijn Huynen
PLoS ONE, 7(1), 2012.
DOI:10.1371/journal.pone.0028272.
Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete.: J.L. Andersen, C. Flamm, D. Merkle and P.F. Stadler
Journal of System Chemistry, 3(1), 2012.
Swarm Controlled Emergence for Ant Clustering.: A. Scheidler, D. Merkle and M. Middendorf
Cybernetics, Accepted for publication.
Task Allocation in Organic Computing Systems: Networks with Reconfigurable Helper Units.: D. Merkle, M. Middendorf and A. Scheidler
Journal of Autonomous and Adaptive Communications Systems, Accepted for publication.
List Factoring and Relative Worst Order Analysis.: Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
Algorithmica, 66(2): 287-309, 2013.
Comparing Online Algorithms for Bin Packing Problems.: Leah Epstein, Lene M. Favrholdt, and Jens S. Kohrt.
Journal of Scheduling, 15(1): 13-21, 2012.
DOI:10.1007/s10951-009-0129-5.
A New Variable-Sized Bin Packing Problem.: Joan Boyar and Lene M. Favrholdt.
Journal of Scheduling, 15(3):273-287, 2012.
Online Variable-Sized Bin Packing with Conflicts.: Leah Epstein, Lene M. Favrholdt, and Asaf Levin.
Discrete Optimization, 8(2): 333-343, 2011.
SAT Solving for Termination Proofs with Recursive Path Orders and Dependency Pairs.: Michael Codish, Jürgen Giesl, Peter Schneider-Kamp, René Thiemann.
Journal of Automated Reasoning, 49(1):53-93, 2011.
Proving Termination by Dependency Pairs and Inductive Theorem Proving.: Carsten Fuhs, Jürgen Giesl, Michael Parting, Peter Schneider-Kamp, and Stephan Swiderski.
Journal of Automated Reasoning, 47(2):133-160, 2011.
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, 61(2):463-505, 2011.
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, 9(1):32-48, 2011.
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, 11(1): 33-63, 2011.
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), 2011.

Peer-Reviewed International Conference Articles

The Relationship between Multiplicative Complexity and Nonlinearity: Joan Boyar and Magnus Find.
In Mathematical Foundations of Computer Science 2014 (MFCS 2014), volume 8635 of Lecture Notes in Computer Science, pages 130-140, Springer, 2014.
On the List Update Problem with Advice: Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
In 8th International Conference on Language and Automata Theory and Applications (LATA 2014), volume 8370 of Lecture Notes in Computer Science, pages 210-221, Springer, 2014.
Online Bin Packing with Advice: Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
In 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics, pages 174-186, 2014.
Online Bin Covering: Expectations vs. Guarantees.: Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
In Seventh Annual International Conference on Combinatorial Optimization and Applications (COCOA), volume 8287 of Lecture Notes in Computer Science, pages 226-237. Springer, 2013.
FooPar: A Functional Object Oriented Parallel Framework in Scala.: Felix P. Hargreaves and Daniel Merkle.
In Proc. of the 10th International Conference on Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, 2013. Accepted for publication.
Barrier Treesfor Metabolic Adjustment Landscapes.: Christiph Flamm, Chris Hemmingsen and Daniel Merkle.
In Proc. of the 12th European Conference on Artificial Life. Accepted for publication.
Bounds for Scheduling on Grid Processors.: Joan Boyar and Faith Ellen.
In Space-Efficient Data Structures, Streams, and Algorithms, volume 8066 of Lecture Notes in Computer Science, pages 12-26, Springer, 2013.
Cancellation-Free Circuits in Unbounded and Bounded Depth.: Joan Boyar and Magnus Find.
In 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), volume 8070 of Lecture Notes in Computer Science, pages 159-170, Springer, 2013.
Performance Measures for Frequent Items in Online Streaming.: Joan Boyar, Kim Skak Larsen, and Abyayananda Maiti.
In 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), volume 8070 of Lecture Notes in Computer Science, pages 60-71, Springer, 2013.
Relative Interval Analysis of Paging Algorithms on Access Graphs.: Joan Boyar, Sushmita Gupta, and Kim Skak Larsen.
In Algorithms and Data Structures Symposium (WADS 2013), volume 8037 of Lecture Notes in Computer Science, pages 195-206, Springer, 2013.
Four Measures of Nonlinearity.: Joan Boyar, Magnus Find, and René Peralta.
In 8th International Conference on Algorithms and Complexity (CIAC 2013), volume 7878 of Lecture Notes in Computer Science, pages 61-78, Springer, 2013.
A Linear Operational Semantics for Termination and Complexity Analysis of ISO Prolog.: Thomas Ströder, Fabian Emmes, Peter Schneider-Kamp, Jürgen Giesl, and Carsten Fuhs.
In 21st International Symposium on Logic-Based Program Synthesis and Transformation, Lecture Notes in Computer Science. Accepted for publication.
Symbolic Evaluation Graphs and Term Rewriting - A General Methodology for Analyzing Logic Programs.: Jürgen Giesl, Thomas Ströder, Peter Schneider-Kamp, Fabian Emmes, and Carsten Fuhs.
In 14th International Symposium on Principles and Practice of Declarative Programming, Leuven, Belgium, pages 1-12, ACM Pres, 2012.
Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree.: Gerth S. Brodal, Rolf Fagerberg, Thomas Mailund, Christian N.S. Pedersen, Andreas Sand.
In Proceedings of 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. Accepted for publication.
Towards Fair and Efficient Assignments of Students to Projects.: Marco Chiarandini, Rolf Fagerberg, Stefano Gualandi
In Proceedings of 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT), pages 388-390, 2012.
Exploring Chemistry Using SMT.: Rolf Fagerberg, Daniel Merkle, Philipp Peters
In Proceedings of 18th International Conference on Principles and Practice of Constraint Programming (CP), volume 7514 of Lecture Notes in Computer Science, pages 900-915, Springer, 2012.
Competitive Routing on a Bounded-Degree Plane Spanner.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot.
In Proceedings of 24th Canadian Conference on Computational Geometry (CCCG), pages 285-290, 2012.
De-amortizing Binary Search Trees.: Prosenjit Bose, Rolf Fagerberg, Sébastien, Stefan Langerman
In Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP), volume 7391 of Lecture Notes in Computer Science, pages 121-132, Springer, 2012.
On Plane Constrained Bounded-Degree Spanners.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot
In Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN), volume 7256 of LNCS, pages 85-96. Springer Verlag, 2012.
Competitive Routing in the Half-Theta-6-Graph.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot
In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, 1319-1328, 2012.
Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis.: Joan Boyar, Sushmita Gupta and Kim S. Larsen.
In 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 7357 of Lecture Notes in Computer Science pages 328-339, Springer, 2012.
A Small Depth-16 Circuit for the AES S-Box.: Joan Boyar and René Peralta.
In Proceedings of IFIP SECURITY 2012. In Infomration Security and Privacy Research, 27th IFIP TC 11 Information Security and Privacy Conference, volume 376 of IFIP Advances in Information and Communication Technology, pages 287-298, Springer, 2012.
A Comparison of Performance Measures via Online Search.: Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
In SIAM Joint FAW-AAIM Conference, volume 7285 of Lecture Notes in Computer Science, pages 303-314, Springer, 2012.
Dependency Triples for Improving Termination Analysis of Logic Programs with Cut.: Thomas Ströder, Peter Schneider-Kamp, and Jürgen Giesl.
In Twentieth International Symposium on Logic-Based Program Synthesis and Transformation, volume 6564 of Lecture Notes in Computer Science, 184-199, Springer, 2011.
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, volume 6534 of Lecture Notes in Computer Science, pages 118-129. Springer, 2011.
Optimal Base Encodings for Pseudo-Boolean Constraints.: Michael Codish, Yoav Fekete, Carsten Fuhs, and Peter Schneider-Kamp.
In 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 6605 of Lecture Notes in Computer Science, pages 189-204, Springer, 2011.

Books

Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture.: Michael Stiebitz, Diego Scheide, Bjarne Toft, and Lene M. Favrholdt.
Wiley 2012.
(Swarm Intelligence - Introduction and Application, Chinese Translation).: C. Blum and D. Merkle (editors).
Chinese publisher: National Defense Industry Press with permission from Springer, 2011.

Book Contributions (entries, chapters, and editorials)

Ant Inspired Methods for Organic Computing.

Alexander Scheidler, Arne Brutschy, Konrad Diwold, Daniel Merkle, and Martin Middendorf.
In Organic Computing 2011, pages 95-109, 2011.

Patents

Method of Optimizing Combinational Circuits.: Joan Boyar and René Peralta. Patent No. US 8,316,338 B2, granted November 20, 2012.