Algorithms, Complexity, and Optimization (ALGOPT)
Designing efficient algorithms helps to explore the limits of what computers can achieve with real-world computational power.
This is an old research theme of the Department of Data Science and Knowledge Engineering (DKE). DKE has become the Department of Advanced Computing Sciences.
Inefficient algorithms quickly become an issue especially when large volumes of data need to be processed and analysed, as is often the case today. Furthermore, if we are to rely on algorithms, we should be able to guarantee that they function well.
Research focus and application
Research within the scope of ALGOPT focuses on developing and analyzing algorithms with rigorous and verifiable performance guarantees. Performance guarantees typically relate to the quality of the output (optimal solutions or solutions that are at most a certain distance from optimality) and/or to the resources used by the algorithm (time/space complexity). Although much of the work has a theoretical flavour, this theory is used to drive the development of highly efficient algorithms in practise.
Techniques and algorithms developed within the scope of ALGOPT are applied to areas such as biology and bioinformatics, logistics, networking, parallel processing and (increasingly) machine learning.
Algorithms, Complexity and Optimization in practice:Dr. Matúš Mihalák discusses optimizing the order of wagons of freight trains |
Scope
- Discrete/Combinatorial Optimization
- Algorithmic Graph Theory
- Computational Game Theory
- Mathematical Programming
- Operations Research
- Computational Complexity
- Theoretical Computer Science
The ALGOPT website is under construction: ALGOPT was previously embedded in the Networks and Strategic Optimization (NSO) group.
Go to NSO website
Researchers
Selected publications
- Angelini, P., Chaplick, S., Cornelsen, S., Lozzo, G. D., & Roselli, V. (2019). Morphing Contact Representations of Graphs. In G. Barequet, & Y. Wang (Eds.), 35th International Symposium on Computational Geometry (SoCG 2019) (Vol. 129, pp. 10:1-10:16). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics (LIPIcs) Vol. 129 https://doi.org/10.4230/LIPICS.SOCG.2019.10
- Bärtschi, A., Chalopin, J., Das, S., Disser, Y., Geissmann, B., Graf, D., Labourel, A., & Mihalák, M. (2020). Collaborative delivery with energy-constrained mobile robots. Theoretical Computer Science, 810, 2-14. https://doi.org/10.1016/j.tcs.2017.04.018
- Bonnet, E., Escoffier, B., Paschos, V., & Stamoulis, G. (2018). Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs. Discrete Optimization, 27, 26-56. https://doi.org/10.1016/j.disopt.2017.09.001
- Bot, R., Grad, S. M., Meier, D., & Staudigl, M. (2021). Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure. Advances in Nonlinear Analysis, 10(1), 450-476. https://doi.org/10.1515/anona-2020-0143
- Chaplick, S., Fomin, F., Golovach, P. A., Knop, D., & Zeman, P. (2021). Kernelization of Graph Hamiltonicity: Proper H-Graphs. Siam Journal on Discrete Mathematics, 35(2), 840-892. https://doi.org/10.1137/19M1299001
- Chaplick, S., Fulek, R., & Klavík, P. (2019). Extending partial representations of circle graphs. Journal of Graph Theory, 91(4), 365-394. https://doi.org/10.1002/JGT.22436
- Chen, C., Giessler, P., Mamageishvili, A., Mihalák, M., & Penna, P. (2020). Sequential Solutions in Machine Scheduling Games. In X. Chen, N. Gravin, M. Hoefer, & R. Mehta (Eds.), Web and Internet Economics: Proceedings of the 16th International Conference on Web and Internet Economics (WINE) (Vol. 12495, pp. 309-322). Springer Nature. Lecture Notes in Computer Science https://doi.org/10.1007/978-3-030-64946-322
- de Campos, C. P., Stamoulis, G., & Weyland, D. (2020). A structured view on weighted counting with relations to counting, quantum computation and applications. Information and Computation, 275, [104627]. https://doi.org/10.1016/j.ic.2020.104627
- Dvurechensky, P., Shtern, S., & Staudigl, M. (2021). First-Order Methods for Convex Optimization. EURO Journal on Computational Optimization, 9, [100015]. https://doi.org/10.1016/j.ejco.2021.100015
- Jones, M., Kelk, S., & Stougie, L. (2021). Maximum parsimony distance on phylogenetic trees: A linear kernel and constant factor approximation algorithm. Journal of Computer and System Sciences, 117, 165-181. https://doi.org/10.1016/j.jcss.2020.10.003
- Kelk, S., & Linz, S. (2019). A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees. Siam Journal on Discrete Mathematics, 33(3), 1556-1574. https://doi.org/10.1137/18M122724X
- Kelk, S., & Stamoulis, G. (2019). Integrality gaps for colorful matchings. Discrete Optimization, 32, 73-92. https://doi.org/10.1016/j.disopt.2018.12.003
- Mihalák, M., & Pont, M. (2019). On Sorting with a Network of Two Stacks. In V. Cacchiani, & A. Marchetti-Spaccamela (Eds.), 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) (Vol. 75, pp. 3:1-3:12). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. OASICS https://doi.org/10.4230/OASIcs.ATMOS.2019.3
- Musegaas, M., Schlicher, L. & Blok, H. (2022). Stackelberg production-protection games: Defending crop production against intentional attacks. European Journal of Operational Research, 297(1), 102-119. https://doi.org/10.1016/j.ejor.2021.04.012.
- Van Iersel, L., Jones, M., & Kelk, S. (2019). A Third Strike Against Perfect Phylogeny. Systematic Biology, 68(5), 814-827. https://doi.org/10.1093/sysbio/syz009
- Westerink-Duijzer, L. E., Schlicher, L. P. J., & Musegaas, M. (2020). Core Allocations for Cooperation Problems in Vaccination. Production and Operations Management, 29(7), 1720-1737. https://doi.org/10.1111/poms.13184