Research Lackner

Home Research Teaching Curriculum Vitae Having fun with permutations
Research Areas My research lies at the interplay of Algorithms and Combinatorics. I am interested in the design of efficient algorithms for combinatorial problems, in particular for combinatorial optimization problems. I have also worked on enumerative aspects of labelled combinatorial objects. Combinatorial optimization: Real-world problems from production scheduling and planning that require tailored solutions, e.g. using AI-techniques Complexity analysis: classical and parametrized complexity theory, design of algorithms Enumeration: permutation patterns, generalized parking functions, patterns in trees and mappings; exact and asymptotic results, generating functions and bijections, log-concavity of combinatorial sequences Social Choice Theory: Connection between domain restrictions and permutation patterns, likelihood of domain restrictions; combinatorial and probabilistic methods Publications updated May 2024 2024 Reducing Energy Consumption in Electronic Component Manufacturing through Large Neighborhood Search joint work with Francesca Da Ros, Luca Di Gaspero and Nysret Musliu, accepted for the GECCO 2024 Workshop Industrial Applications of Metaheuristics Local Search Algorithms for the Oven Scheduling Problem joint work with Francesca Da Ros, Luca Di Gaspero, Nysret Musliu and Felix Winter, accepted as poster for GECCO 2024. 2023 Exact methods for the Oven Scheduling Problem joint work with Christoph Mrkvicka, Nysret Musliu, Daniel Walkiewicz and Felix Winter, Constraints, 28(2), 320–361. 2022 Solving an Industrial Oven Scheduling Problem with a Simulated Annealing Approach, joint work with Nysret Musliu and Felix Winter, accepted for publication in Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2022. Exact and meta-heuristic approaches for the production leveling problem, joint work with Johannes Vass, Christoph Mrkvicka, Nysret Musliu and Felix Winter, Journal of Scheduling, 1 (2022), 1; 1-32. 2021 Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem, joint work with Christoph Mrkvicka, Nysret Musliu, Daniel Walkiewicz and Felix Winter, in Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), 37:1–37:18. 2020 A Mathematical Analysis of an Election System Proposed by Gottlob Frege, joint work with Paul Harrenstein and Martin Lackner. Erkenntnis, 1 (2020), 1-36. Available here. Runs in labelled trees and mappings, joint work with Alois Panholzer, Discrete Mathematics, 343(9): 111990, 2020. Preprint available here. Latticepathology and Symmetric Functions (Extended Abstract), joint work with Cyril Banderier, and Michael Wallner: AofA 2020: 2:1-2:16, 2020. 2017 Longest increasing subsequences and log concavity, joint work with Miklos Bona and Bruce Sagan, Annals of Combinatorics, 21, pages 535-549, 2017. Preprint available here. On the likelihood of single-peaked preferences, joint work with Martin Lackner, Social Choice and Welfare, 48(4), 717-745, 2017. A preprint of this paper is available here. 2016 The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations, joint work with Michael H. Albert, Martin Lackner and Vincent Vatter, Discrete Mathematics & Theoretical Computer Science, vol. 18 no. 2, Permutation Patterns 2015, 2016. Available here. Parking functions for mappings, joint work with Alois Panholzer, Journal of Combinatorial Theory, Series A, 142, 1-28, 2016. A preprint of this paper can be found here. A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs , joint work with Martin Lackner, Algorithmica: 1-34. A preprint of this paper can be found here. Mountainous patterns, self-published by Marie-Louise Lackner and printed by epubli, Berlin. ISBN: 9783741817038 2015 Patterns in labelled combinatorial objects, PhD thesis written under the supervision of Alois Panholzer, TU Wien, 2015. 2014 The Likelihood of Structure in Preference Profiles, joint work with Martin Lackner, in Proceedings of the 8th Multidisciplinary Workshop on Advances in Preference Handling (MPref 2014). 2013 On restricted permutations on regular multisets, in Permutation Patterns 2012 Proceedings, Special Issue of Pure Mathematics and Applications, 24 (2): 59-82, 2013. The computational landscape of permutation patterns, joint work with Martin Lackner, in Permutation Patterns 2012 Proceedings, Special Issue of Pure Mathematics and Applications, 24 (2): 83-101, 2013. 2012 A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs , joint work with Martin Lackner, 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012). An extended and refined version of this paper was published in Algorithmica, see above. From Peaks to Valleys, Running Up and Down: Fast Permutation Pattern Matching , joint work with Martin Lackner, Tiny Transactions on Computer Science ( TinyTOCS ), 2012. The aim of this paper is to explain our results in "A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs" with only 140 characters. This radical length constraint is the central idea of the Tiny Transactions on Computer Science journal. 2011 Restricted Permutations on Multisets, master thesis written under the supervision of Alois Panholzer, TU Wien, 2011. A list of all my publications on arxiv.org can be found here. Talks Practical Integration of Lower Bounds for the Oven Scheduling Problem, Research seminar of the Databases and Artificial Intelligence Group, TU Wien, April 2024. Solving an Industrial Oven Scheduling Problem with a Simulated Annealing Approach, PATAT 2022, Leuven, Belgium, August 2022. Lower bounds for the Oven Scheduling Optimization Problem, Research seminar of the Databases and Artificial Intelligence Group, TU Wien, March 2022. Minimizing cumulative batch processing time for an industrial oven scheduling problem, Research seminar of the Databases and Artificial Intelligence Group, TU Wien, November 2021. Minimizing cumulative batch processing time for an industrial oven scheduling problem, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), online, October 2021. Parking functions generalised to trees and mappings - enumerative and asymptotic results, Mathematics colloquium, The Open University, UK, May 2016. Parking in trees and mappings - enumerative results and a phase change behaviour, Combinatorics seminar, University of Oxford, UK, March 2016. Efficient Algorithms for Permutation Pattern Matching, Dagstuhl Seminar 16071 on Pattern Avoidance and Genome Sorting, Schloss Dagstuhl, Germany, February 2016. An Invitation to Analytic Combinatorics and Lattice Path Counting, introductory course held together with Michael Wallner at ALEA in Europe Young Researchers' Workshop, University of Bath, UK, December 2015. Log-concavity, longest increasing subsequences, and involutions, 13th Permutation Patterns conference, London, UK, June 2015. The likelihood of single-peaked preference profiles: a combinatorial approach, Combinatorics Seminar, University of Florida, Gainesville, USA, January 2015. A combinatorial approach to structure in preference profiles, held at seminar of the Arbeitsgemeinschaft Diskrete Mathematik, Vienna University of Technology, Austria, January 2015. The Likelihood of Structure in Preference Profiles, Workshop on Challenges in Algorithmic Social Choice, Bad Belzig, Germany. Permutation Pattern Matching: From separable permutations to fixed-parameter algorithms, Combinatorics Seminar, University of Florida, Gainesville, USA, February 2014. The computational landscape of permutation patterns, held at the 11th Permutation Patterns conference, University Paris Diderot, Paris, France, July 2013. Parking in trees, held at 4th biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM), Memorial University of Newfoundland, St. John's, Canada, June 2013. Label patterns in mappings, held at the 24th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2013, Cala Galdana, Menorca, Spain, May 2013. Parking arborescent, held at the Journées Aléa 2013, CIRM, Marseille, France, March 2013. A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs, held at seminar of the Arbeitsgemeinschaft Diskrete Mathematik, Vienna University of Technology, Austria, October 2012. A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs, held at the 10th Permutation Patterns conference, University of Strathclyde, Glasgow, Scotland, June 2012. Counting multiset-permutations avoiding the pattern 122 and another pattern of length three, held at the 30th Colloquium on Combinatorics, Magdeburg, Germany, November 2011. Enumerative formulae for multiset-permutations avoiding the pattern 122 and another pattern of length three, ÖMG-Tagung - CSASC 2011, Krems, Austria, September 2011.

Home Research Teaching Curriculum Vitae Having fun with permutations

Research Areas

My research lies at the interplay of Algorithms and Combinatorics. I am interested in the design of efficient algorithms for combinatorial problems, in particular for combinatorial optimization problems. I have also worked on enumerative aspects of labelled combinatorial objects.

Combinatorial optimization: Real-world problems from production scheduling and planning that require tailored solutions, e.g. using AI-techniques

Complexity analysis: classical and parametrized complexity theory, design of algorithms

Enumeration: permutation patterns, generalized parking functions, patterns in trees and mappings; exact and asymptotic results, generating functions and bijections, log-concavity of combinatorial sequences

Social Choice Theory: Connection between domain restrictions and permutation patterns, likelihood of domain restrictions; combinatorial and probabilistic methods

Publications

updated May 2024

2024

Reducing Energy Consumption in Electronic Component Manufacturing through Large Neighborhood Search joint work with Francesca Da Ros, Luca Di Gaspero and Nysret Musliu, accepted for the GECCO 2024 Workshop Industrial Applications of Metaheuristics
Local Search Algorithms for the Oven Scheduling Problem joint work with Francesca Da Ros, Luca Di Gaspero, Nysret Musliu and Felix Winter, accepted as poster for GECCO 2024.

2023

Exact methods for the Oven Scheduling Problem joint work with Christoph Mrkvicka, Nysret Musliu, Daniel Walkiewicz and Felix Winter, Constraints, 28(2), 320–361.

2022

Solving an Industrial Oven Scheduling Problem with a Simulated Annealing Approach, joint work with Nysret Musliu and Felix Winter, accepted for publication in Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2022.
Exact and meta-heuristic approaches for the production leveling problem, joint work with Johannes Vass, Christoph Mrkvicka, Nysret Musliu and Felix Winter, Journal of Scheduling, 1 (2022), 1; 1-32.

2021

Minimizing Cumulative Batch Processing Time for an Industrial Oven Scheduling Problem, joint work with Christoph Mrkvicka, Nysret Musliu, Daniel Walkiewicz and Felix Winter, in Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), 37:1–37:18.

2020

A Mathematical Analysis of an Election System Proposed by Gottlob Frege, joint work with Paul Harrenstein and Martin Lackner. Erkenntnis, 1 (2020), 1-36. Available here.
Runs in labelled trees and mappings, joint work with Alois Panholzer, Discrete Mathematics, 343(9): 111990, 2020. Preprint available here.
Latticepathology and Symmetric Functions (Extended Abstract), joint work with Cyril Banderier, and Michael Wallner: AofA 2020: 2:1-2:16, 2020.

2017

Longest increasing subsequences and log concavity, joint work with Miklos Bona and Bruce Sagan, Annals of Combinatorics, 21, pages 535-549, 2017. Preprint available here.
On the likelihood of single-peaked preferences, joint work with Martin Lackner, Social Choice and Welfare, 48(4), 717-745, 2017. A preprint of this paper is available here.

2016

The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations, joint work with Michael H. Albert, Martin Lackner and Vincent Vatter, Discrete Mathematics & Theoretical Computer Science, vol. 18 no. 2, Permutation Patterns 2015, 2016. Available here.
Parking functions for mappings, joint work with Alois Panholzer, Journal of Combinatorial Theory, Series A, 142, 1-28, 2016. A preprint of this paper can be found here.
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs , joint work with Martin Lackner, Algorithmica: 1-34. A preprint of this paper can be found here.
Mountainous patterns, self-published by Marie-Louise Lackner and printed by epubli, Berlin. ISBN: 9783741817038

2015

Patterns in labelled combinatorial objects, PhD thesis written under the supervision of Alois Panholzer, TU Wien, 2015.

2014

The Likelihood of Structure in Preference Profiles, joint work with Martin Lackner, in Proceedings of the 8th Multidisciplinary Workshop on Advances in Preference Handling (MPref 2014).

2013

On restricted permutations on regular multisets, in Permutation Patterns 2012 Proceedings, Special Issue of Pure Mathematics and Applications, 24 (2): 59-82, 2013.
The computational landscape of permutation patterns, joint work with Martin Lackner, in Permutation Patterns 2012 Proceedings, Special Issue of Pure Mathematics and Applications, 24 (2): 83-101, 2013.

2012

A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs , joint work with Martin Lackner, 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012).
An extended and refined version of this paper was published in Algorithmica, see above.
From Peaks to Valleys, Running Up and Down: Fast Permutation Pattern Matching , joint work with Martin Lackner, Tiny Transactions on Computer Science ( TinyTOCS ), 2012.
The aim of this paper is to explain our results in "A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs" with only 140 characters. This radical length constraint is the central idea of the Tiny Transactions on Computer Science journal.

2011

Restricted Permutations on Multisets, master thesis written under the supervision of Alois Panholzer, TU Wien, 2011.

A list of all my publications on arxiv.org can be found here.

Talks

Practical Integration of Lower Bounds for the Oven Scheduling Problem, Research seminar of the Databases and Artificial Intelligence Group, TU Wien, April 2024.
Solving an Industrial Oven Scheduling Problem with a Simulated Annealing Approach, PATAT 2022, Leuven, Belgium, August 2022.
Lower bounds for the Oven Scheduling Optimization Problem, Research seminar of the Databases and Artificial Intelligence Group, TU Wien, March 2022.
Minimizing cumulative batch processing time for an industrial oven scheduling problem, Research seminar of the Databases and Artificial Intelligence Group, TU Wien, November 2021.
Minimizing cumulative batch processing time for an industrial oven scheduling problem, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), online, October 2021.
Parking functions generalised to trees and mappings - enumerative and asymptotic results, Mathematics colloquium, The Open University, UK, May 2016.
Parking in trees and mappings - enumerative results and a phase change behaviour, Combinatorics seminar, University of Oxford, UK, March 2016.
Efficient Algorithms for Permutation Pattern Matching, Dagstuhl Seminar 16071 on Pattern Avoidance and Genome Sorting, Schloss Dagstuhl, Germany, February 2016.
An Invitation to Analytic Combinatorics and Lattice Path Counting, introductory course held together with Michael Wallner at ALEA in Europe Young Researchers' Workshop, University of Bath, UK, December 2015.
Log-concavity, longest increasing subsequences, and involutions, 13th Permutation Patterns conference, London, UK, June 2015.
The likelihood of single-peaked preference profiles: a combinatorial approach, Combinatorics Seminar, University of Florida, Gainesville, USA, January 2015.
A combinatorial approach to structure in preference profiles, held at seminar of the Arbeitsgemeinschaft Diskrete Mathematik, Vienna University of Technology, Austria, January 2015.
The Likelihood of Structure in Preference Profiles, Workshop on Challenges in Algorithmic Social Choice, Bad Belzig, Germany.
Permutation Pattern Matching: From separable permutations to fixed-parameter algorithms, Combinatorics Seminar, University of Florida, Gainesville, USA, February 2014.
The computational landscape of permutation patterns, held at the 11th Permutation Patterns conference, University Paris Diderot, Paris, France, July 2013.
Parking in trees, held at 4th biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM), Memorial University of Newfoundland, St. John's, Canada, June 2013.
Label patterns in mappings, held at the 24th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2013, Cala Galdana, Menorca, Spain, May 2013.
Parking arborescent, held at the Journées Aléa 2013, CIRM, Marseille, France, March 2013.
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs, held at seminar of the Arbeitsgemeinschaft Diskrete Mathematik, Vienna University of Technology, Austria, October 2012.
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs, held at the 10th Permutation Patterns conference, University of Strathclyde, Glasgow, Scotland, June 2012.
Counting multiset-permutations avoiding the pattern 122 and another pattern of length three, held at the 30th Colloquium on Combinatorics, Magdeburg, Germany, November 2011.
Enumerative formulae for multiset-permutations avoiding the pattern 122 and another pattern of length three,
ÖMG-Tagung - CSASC 2011, Krems, Austria, September 2011.