The project Algorithmic Challenges is funded by a DKK 1,036,800.00 grant from the Danish Council for Independent Research | Natural Sciences, running from July 1, 2014 through September 30, 2017.
The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark.

Participants

Environment

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The participants are all associated with the Research Training Program in Computer Science as Ph.D. advisors.

Activities

Almost all activities on this grant are research related traveling to conferences, meetings by invitation, research collaboration, and hosting guests. Other more major arrangements include the following:

April 4, 2016, Boyar, Fagerberg, and Larsen arranged ARCO at SDU.

November 12-13, 2015, Boyar, Favrholdt, and Larsen, together with two Ph.D. students, attended the workshop New Techniques in Online Algorithms in Paris and gave three presentations.

June 15-27, 2015, Boyar was a senior keynote speaker and member of the scientific committee of EURO Summer Institute on Online Optimization held at the University of Szeged.

November 2-7, 2014, Merkle co-organized the Dagstuhl seminar, Algorithmic Cheminformatics.

July 7, 2014, Boyar, Favrholdt, and Larsen arranged the workshop, TOLA, on Trends in Online Algorithms, as a satelite workshop of ICALP.

Publications

Here we list project publications since July 1, 2014. Complete lists for each participant can be found via our individual home pages or via the standard search engine for Computer Science publications, dblp.

Acknowledgement: We are grateful to dblp for providing data for the publication list.

Peer-Reviewed International Journal Articles

Online-Bounded Analysis.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
Journal of Scheduling.
Accepted for Publication

Formally Proving Size Optimality of Sorting Networks.
Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp.
Journal of Automated Reasoning.
Accepted for publication

Online Algorithms with Advice: A Survey.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, Jesper W. Mikkelsen.
ACM Comput. Surv. 50(2): 19:1-19:34, 2017.

On the list update problem with advice.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
Inf. Comput. 253: 411-423, 2017.

Optimal-depth sorting networks.
Daniel Bundala, Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp, Jakub Závodný.
J. Comput. Syst. Sci. 84: 185-204, 2017.

Optimizing sorting algorithms by using sorting networks.
Michael Codish, Luís Cruz-Filipe, Markus Nebel, Peter Schneider-Kamp.
Formal Asp. Comput. 29(3): 559-579, 2017.

Analyzing Program Termination and Complexity Automatically with AProVE.
Jürgen Giesl, Cornelius Aschermann, Marc Brockschmidt, Fabian Emmes, Florian Frohn, Carsten Fuhs, Jera Hensel, Carsten Otto, Martin Plücker, Peter Schneider-Kamp, Thomas Ströder, Stephanie Swiderski, René Thiemann.
J. Autom. Reasoning 58(1): 3-31, 2017.

Automatically Proving Termination and Memory Safety for Programs with Pointer Arithmetic.
Thomas Ströder, Jürgen Giesl, Marc Brockschmidt, Florian Frohn, Carsten Fuhs, Jera Hensel, Peter Schneider-Kamp, Cornelius Aschermann.
J. Autom. Reasoning 58(1): 33-65, 2017.

Biased Predecessor Search.
Prosenjit Bose, Rolf Fagerberg, John Howat, Pat Morin.
Algorithmica 76(4): 1097-1105, 2016.

On various nonlinearity measures for boolean functions.
Joan Boyar, Magnus Gausdal Find, René Peralta.
Cryptography and Communications 8(3): 313-330, 2016.

Online Bin Packing with Advice.
Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz.
Algorithmica 74(1): 507-527, 2016.

Sorting nine inputs requires twenty-five comparisons.
Michael Codish, Luís Cruz-Filipe, Michael Frank, Peter Schneider-Kamp.
J. Comput. Syst. Sci. 82(3): 551-563, 2016.

Towards Optimal DNA-Templated Computing.
Jakob L. Andersen, Christoph Flamm, Martin M. Hanczyc, Daniel Merkle.
IJUC 11(3-4): 185-203, 2015.

In silico Support for Eschenmoser's Glyoxylate Scenario
Jakob L. Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
Israel Journal of Chemistry 55(8): 919-933, 2015.

New and improved spanning ratios for Yao graphs.
Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot, Ge Xia.
JoCG 6(2): 19-53, 2015.

Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles.
Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot.
SIAM J. Comput. 44(6): 1626-1649, 2015.

Cancellation-free circuits in unbounded and bounded depth.
Joan Boyar, Magnus Gausdal Find.
Theor. Comput. Sci. 590: 17-26, 2015.

Relative interval analysis of paging algorithms on access graphs.
Joan Boyar, Sushmita Gupta, Kim S. Larsen.
Theor. Comput. Sci. 568: 28-48, 2015.

A Comparison of Performance Measures for Online Algorithms.
Joan Boyar, Sandy Irani, Kim S. Larsen.
Algorithmica 72(4): 969-994, 2015.

The Frequent Items Problem in Online Streaming Under Various Performance Measures.
Joan Boyar, Kim S. Larsen, Abyayananda Maiti.
Int. J. Found. Comput. Sci. 26(4): 413-440, 2015.

Online multi-coloring with advice.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
Theor. Comput. Sci. 596: 79-91, 2015.

Soccer is Harder Than Football.
Jan Christensen, Anders Nicolai Knudsen, Kim S. Larsen.
Int. J. Found. Comput. Sci. 26(4): 477-486, 2015.

Task allocation in organic computing systems: networks with reconfigurable helper units.
Daniel Merkle, Martin Middendorf, Alexander Scheidler.
IJAACS 8(1): 60-80, 2015.

Generic Strategies for Chemical Space Exploration.
Jakob L. Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
International Journal of Computational Biology and Drug Design 8(1): 225-258, 2014.

Online bin covering: Expectations vs. guarantees.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
Theor. Comput. Sci. 556: 71-84, 2014.

Peer-Reviewed International Conference Articles

Chemical Graph Transformation with Stereo-Information.
Jakob Lykke Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
ICGT, Lecture Notes in Computer Science 10373: 54-69, Springer, 2017.
[Graph Transformation - 10th International Conference, ICGT 2017, Held as Part of STAF 2017, Marburg, Germany, July 18-19, 2017, Proceedings.]

Relaxing the Irrevocability Requirement for Online Graph Algorithms.
Joan Boyar, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 10389: 217-228, Springer, 2017.
[Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL, Canada, July 31 - August 2, 2017, Proceedings.]

Efficient Certified RAT Verification.
Luís Cruz-Filipe, Marijn J. H. Heule, Warren A. Hunt Jr., Matt Kaufmann, Peter Schneider-Kamp.
CADE, Lecture Notes in Computer Science 10395: 220-236, Springer, 2017.
[Automated Deduction - CADE 26 - 26th International Conference on Automated Deduction, Gothenburg, Sweden, August 6-11, 2017, Proceedings.]

The Paths to Choreography Extraction.
Luís Cruz-Filipe, Kim S. Larsen, Fabrizio Montesi.
FoSSaCS, Lecture Notes in Computer Science 10203: 424-440, 2017.
[Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings.]

How to Get More Out of Your Oracles.
Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp.
ITP, Lecture Notes in Computer Science 10499: 164-170, Springer, 2017.
[Interactive Theorem Proving - 8th International Conference, ITP 2017, Brasília, Brazil, September 26-29, 2017, Proceedings.]

Efficient Certified Resolution Proof Checking.
Luís Cruz-Filipe, Joao Marques-Silva, Peter Schneider-Kamp.
TACAS (1), Lecture Notes in Computer Science 10205: 118-135, 2017.
[Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, Part I.]

Formally Proving the Boolean Pythagorean Triples Conjecture.
Luís Cruz-Filipe, Peter Schneider-Kamp.
LPAR, EPiC Series in Computing 46: 509-522, EasyChair, 2017.
[LPAR-21, 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Maun, Botswana, 7-12th May 2017.]

DNA-Templated Synthesis Optimization.
Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, Alexei Mihalchuk.
DNA, Lecture Notes in Computer Science 10467: 17-32, Springer, 2017.
[DNA Computing and Molecular Programming - 23rd International Conference, DNA 23, Austin, TX, USA, September 24-28, 2017, Proceedings.]

Flight Planning in Free Route Airspaces.
Casper Kehlet Jensen, Marco Chiarandini, Kim S. Larsen.
ATMOS, OASICS 59: 14:1-14:14, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
[17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2017, September 7-8, 2017, Vienna, Austria.]

Constraint Handling in Flight Planning.
Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen.
CP, Lecture Notes in Computer Science 10416: 354-369, Springer, 2017.
[Principles and Practice of Constraint Programming - 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings.]

Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps.
Nikolai Nøjgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, Marc Hellmuth.
WABI, LIPIcs 88: 17:1-17:12, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
[17th International Workshop on Algorithms in Bioinformatics, WABI 2017, August 21-23, 2017, Boston, MA, USA.]

A Software Package for Chemically Inspired Graph Transformation.
Jakob L. Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
ICGT, Lecture Notes in Computer Science 9761: 73-88, Springer, 2016.
[Graph Transformation - 9th International Conference, ICGT 2016, in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Vienna, Austria, July 5-6, 2016, Proceedings.]

Online Dominating Set.
Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen.
SWAT, LIPIcs 53: 21:1-21:15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
[15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, June 22-24, 2016, Reykjavik, Iceland.]

Online Bounded Analysis.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
CSR, Lecture Notes in Computer Science 9691: 131-145, Springer, 2016.
[Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings.]

Batch Coloring of Graphs.
Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
WAOA, Lecture Notes in Computer Science: 52-64, Springer, 2016.
[Fourteenth Workshop on Approximation and Online Algorithms.]

Weighted Online Problems with Advice.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
IWOCA, Lecture Notes in Computer Science 9843: 179-190, Springer, 2016.
[Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings.]

Active Integrity Constraints for Multi-context Systems.
Luís Cruz-Filipe, Graça Gaspar, Isabel Nunes, Peter Schneider-Kamp.
EKAW, Lecture Notes in Computer Science 10024: 98-112, 2016.
[Knowledge Engineering and Knowledge Management - 20th International Conference, EKAW 2016, Bologna, Italy, November 19-23, 2016, Proceedings.]

Integrity Constraints for General-Purpose Knowledge Bases.
Luís Cruz-Filipe, Isabel Nunes, Peter Schneider-Kamp.
FoIKS, Lecture Notes in Computer Science 9616: 235-254, Springer, 2016.
[Foundations of Information and Knowledge Systems - 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings.]

Automatic Inference of Graph Transformation Rules Using the Cyclic Nature of Chemical Reactions.
Christoph Flamm, Daniel Merkle, Peter F. Stadler, Uffe Thorsen.
ICGT, Lecture Notes in Computer Science 9761: 206-222, Springer, 2016.
[Graph Transformation - 9th International Conference, ICGT 2016, in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Vienna, Austria, July 5-6, 2016, Proceedings.]

Vertical Optimization of Resource Dependent Flight Paths.
Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen.
ECAI, Frontiers in Artificial Intelligence and Applications 285: 639-645, IOS Press, 2016.
[ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016).]

Competitive Local Routing with Constraints.
Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot.
ISAAC, Lecture Notes in Computer Science 9472: 23-34, Springer, 2015.
[Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings.]

Advice Complexity for a Class of Online Problems.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
STACS, LIPIcs 30: 116-129, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
[32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany.]

Constructive Relationships Between Algebraic Thickness and Normality.
Joan Boyar, Magnus Gausdal Find.
FCT, Lecture Notes in Computer Science 9210: 106-117, Springer, 2015.
[Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings.]

Adding Isolated Vertices Makes Some Online Algorithms Optimal.
Joan Boyar, Christian Kudahl.
IWOCA, Lecture Notes in Computer Science 9538: 65-76, Springer, 2015.
[Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers.]

Applying Sorting Networks to Synthesize Optimized Sorting Libraries.
Michael Codish, Luís Cruz-Filipe, Markus Nebel, Peter Schneider-Kamp.
LOPSTR, Lecture Notes in Computer Science 9527: 127-142, Springer, 2015.
[Logic-Based Program Synthesis and Transformation - 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers.]

Sorting Networks: The End Game.
Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp.
LATA, Lecture Notes in Computer Science 8977: 664-675, Springer, 2015.
[Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings.]

Active Integrity Constraints: From Theory to Implementation.
Luís Cruz-Filipe, Michael Franz, Artavazd Hakhverdyan, Marta Ludovico, Isabel Nunes, Peter Schneider-Kamp.
IC3K, Communications in Computer and Information Science 631: 399-420, Springer, 2015.
[Knowledge Discovery, Knowledge Engineering and Knowledge Management - 7th International Joint Conference, IC3K 2015, Lisbon, Portugal, November 12-14, 2015, Revised Selected Papers.]

repAIrC: A Tool for Ensuring Data Consistency.
Luís Cruz-Filipe, Michael Franz, Artavazd Hakhverdyan, Marta Ludovico, Isabel Nunes, Peter Schneider-Kamp.
KMIS: 17-26, SciTePress, 2015.
[KMIS 2015 - Proceedings of the International Conference on Knowledge Management and Information Sharing, part of the 7th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management (IC3K 2015), Volume 3, Lisbon, Portugal, November 12-14, 2015.]

Optimizing a Certified Proof Checker for a Large-Scale Computer-Generated Proof.
Luís Cruz-Filipe, Peter Schneider-Kamp.
CICM, Lecture Notes in Computer Science 9150: 55-70, Springer, 2015.
[Intelligent Computer Mathematics - International Conference, CICM 2015, Washington, DC, USA, July 13-17, 2015, Proceedings.]

Formalizing Size-Optimal Sorting Networks: Extracting a Certified Proof Checker.
Luís Cruz-Filipe, Peter Schneider-Kamp.
ITP, Lecture Notes in Computer Science 9236: 154-169, Springer, 2015.
[Interactive Theorem Proving - 6th International Conference, ITP 2015, Nanjing, China, August 24-27, 2015, Proceedings.]

50 Shades of Rule Composition - From Chemical Reactions to Higher Levels of Abstraction.
Jakob Lykke Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
FMMB, Lecture Notes in Computer Science 8738: 117-135, Springer, 2014.
[Formal Methods in Macro-Biology - First International Conference, FMMB 2014, Nouméa, New Caledonia, September 22-24, 2014. Proceedings.]

Continuous Yao Graphs.
Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, André van Renssen, Perouz Taslakian, Sander Verdonschot.
CCCG, Carleton University, Ottawa, Canada, 2014.
[Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014.]

The Relationship between Multiplicative Complexity and Nonlinearity.
Joan Boyar, Magnus Gausdal Find.
MFCS (2), Lecture Notes in Computer Science 8635: 130-140, Springer, 2014.
[Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II.]

Online Multi-Coloring with Advice.
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen.
WAOA, Lecture Notes in Computer Science 8952: 83-94, Springer, 2014.
[Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers.]

Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten).
Michael Codish, Luís Cruz-Filipe, Michael Frank, Peter Schneider-Kamp.
ICTAI: 186-193, IEEE Computer Society, 2014.
[26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limassol, Cyprus, November 10-12, 2014.]

The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes.
Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp.
SYNASC: 359-366, IEEE Computer Society, 2014.
[16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2014, Timisoara, Romania, September 22-25, 2014.]

Online Dual Edge Coloring of Paths and Trees.
Lene M. Favrholdt, Jesper W. Mikkelsen.
WAOA, Lecture Notes in Computer Science 8952: 181-192, Springer, 2014.
[Approximation and Online Algorithms - 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers.]

Group communication patterns for high performance computing in scala.
Felix Palludan Hargreaves, Daniel Merkle, Peter Schneider-Kamp.
FHPC@ICFP: 75-85, ACM, 2014.
[Proceedings of the 3rd ACM SIGPLAN workshop on Functional high-performance computing, FHPC@ICFP 2014, Gothenburg, Sweden, September 4, 2014.]

Contributions by Invitation

Online Algorithms with Advice: A Survey.
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, Jesper W. Mikkelsen.
SIGACT News 47(3): 93-129, 2016.

String Sorting.
Rolf Fagerberg.
Encyclopedia of Algorithms: 2117-2121, 2016.

Cache-Oblivious B-Tree.
Rolf Fagerberg.
Encyclopedia of Algorithms: 261-264, 2016.

Cache-Oblivious Model.
Rolf Fagerberg.
Encyclopedia of Algorithms: 264-269, 2016.

 

Data protection at SDU ▪ Databeskyttelse på SDU