Welcome to my personal and academic profile. I am currently a postdoc researcher at Graz University of Technology in the combinatorial optimization group. Before that I did my PhD studies as part of the DK Discrete Mathematics under the supervision of Bettina Klinz.
Mail: lendl [at] math.tugraz.at
2019 |
Lendl, Stefan; Ćustić, Ante; Punnen, Abraham P Combinatorial optimization with interaction costs: Complexity and solvable cases Journal Article Discrete Optimization, 33 , pp. 101-117, 2019. @article{lendl2017combinatorial, title = {Combinatorial optimization with interaction costs: Complexity and solvable cases}, author = { Stefan Lendl and Ante Ćustić and Abraham P Punnen}, url = {https://arxiv.org/abs/1707.02428}, doi = {10.1016/j.disopt.2019.03.004}, year = {2019}, date = {2019-08-01}, journal = {Discrete Optimization}, volume = {33}, pages = {101-117}, abstract = {We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures. |
Lendl, Stefan; Peis, Britta; Timmermans, Veerle Matroid Bases with Cardinality Constraints on the Intersection Online 2019. @online{Lendl2019, title = {Matroid Bases with Cardinality Constraints on the Intersection}, author = {Stefan Lendl and Britta Peis and Veerle Timmermans }, url = {https://arxiv.org/abs/1907.04741}, year = {2019}, date = {2019-07-10}, abstract = {Given two matroids $mathcal{M}_{1} = (E, mathcal{B}_{1})$ and $mathcal{M}_{2} = (E, mathcal{B}_{2})$ on a common ground set $E$ with base sets $mathcal{B}_{1}$ and $mathcal{B}_{2}$, some integer $k in mathbb{N}$, and two cost functions $c_{1}, c_{2} colon E rightarrow mathbb{R}$, we consider the optimization problem to find a basis $X in mathcal{B}_{1}$ and a basis $Y in mathcal{B}_{2}$ minimizing cost $sum_{ein X} c_1(e)+sum_{ein Y} c_2(e)$ subject to either a lower bound constraint $|X cap Y| le k$, an upper bound constraint $|X cap Y| ge k$, or an equality constraint $|X cap Y| = k$ on the size of the intersection of the two bases $X$ and $Y$. The problem with lower bound constraint turns out to be a generalization of the Recoverable Robust Matroid problem under interval uncertainty representation for which the question for a strongly polynomial-time algorithm was left as an open question by Hradovich et al. We show that the two problems with lower and upper bound constraints on the size of the intersection can be reduced to weighted matroid intersection, and thus be solved with a strongly polynomial-time primal-dual algorithm. The question whether the problem with equality constraint can also be solved efficiently turned out to be a lot harder. As our main result, we present a strongly-polynomial, primal-dual algorithm for the problem with equality constraint on the size of the intersection. Additionally, we discuss generalizations of the problems from matroids to polymatroids, and from two to three or more matroids.}, keywords = {}, pubstate = {published}, tppubtype = {online} } Given two matroids $mathcal{M}_{1} = (E, mathcal{B}_{1})$ and $mathcal{M}_{2} = (E, mathcal{B}_{2})$ on a common ground set $E$ with base sets $mathcal{B}_{1}$ and $mathcal{B}_{2}$, some integer $k in mathbb{N}$, and two cost functions $c_{1}, c_{2} colon E rightarrow mathbb{R}$, we consider the optimization problem to find a basis $X in mathcal{B}_{1}$ and a basis $Y in mathcal{B}_{2}$ minimizing cost $sum_{ein X} c_1(e)+sum_{ein Y} c_2(e)$ subject to either a lower bound constraint $|X cap Y| le k$, an upper bound constraint $|X cap Y| ge k$, or an equality constraint $|X cap Y| = k$ on the size of the intersection of the two bases $X$ and $Y$. The problem with lower bound constraint turns out to be a generalization of the Recoverable Robust Matroid problem under interval uncertainty representation for which the question for a strongly polynomial-time algorithm was left as an open question by Hradovich et al. We show that the two problems with lower and upper bound constraints on the size of the intersection can be reduced to weighted matroid intersection, and thus be solved with a strongly polynomial-time primal-dual algorithm. The question whether the problem with equality constraint can also be solved efficiently turned out to be a lot harder. As our main result, we present a strongly-polynomial, primal-dual algorithm for the problem with equality constraint on the size of the intersection. Additionally, we discuss generalizations of the problems from matroids to polymatroids, and from two to three or more matroids. |
Lachmann, Thomas; Lendl, Stefan Efficient Algorithms for the Recoverable (Robust) Selection Problem Unpublished Forthcoming Forthcoming. @unpublished{Lachmann2019, title = {Efficient Algorithms for the Recoverable (Robust) Selection Problem}, author = {Thomas Lachmann and Stefan Lendl}, year = {2019}, date = {2019-04-01}, abstract = { We study the probl{Recoverable Selection} problem, a generalization of the well-studied classic probl{Selection} problem. Given an element set $E$, two cost vectors $alpha, beta in rr^{E}$ and two parameters $p, q in nn$, we want to find sets $A, B subseteq E$ such that $|A| = |B| = p$ and $|A cap B| geq q$ minimizing the cost $sum_{i in A} alpha_{i} + sum_{j in B} beta_{j}$. We show that a simple greedy algorithm solves this problem to optimality. By a detailed mathematical analysis of the solution structure, we obtain discrete-convexity and unimodality results for parameterized objective functions related to this problem. Using this, we obtain an asymptotically optimal linear time algorithm for the problem, matching the optimal asymptotic running time of the classic Selection problem. }, keywords = {}, pubstate = {forthcoming}, tppubtype = {unpublished} } We study the probl{Recoverable Selection} problem, a generalization of the well-studied classic probl{Selection} problem. Given an element set $E$, two cost vectors $alpha, beta in rr^{E}$ and two parameters $p, q in nn$, we want to find sets $A, B subseteq E$ such that $|A| = |B| = p$ and $|A cap B| geq q$ minimizing the cost $sum_{i in A} alpha_{i} + sum_{j in B} beta_{j}$. We show that a simple greedy algorithm solves this problem to optimality. By a detailed mathematical analysis of the solution structure, we obtain discrete-convexity and unimodality results for parameterized objective functions related to this problem. Using this, we obtain an asymptotically optimal linear time algorithm for the problem, matching the optimal asymptotic running time of the classic Selection problem. |
Grigoriev, Alexander; Hartmann, Tim A; Lendl, Stefan; Woeginger, Gerhard J Dispersing obnoxious facilities on a graph Conference 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), 2019. @conference{Grigoriev2019, title = {Dispersing obnoxious facilities on a graph}, author = {Alexander Grigoriev and Tim A. Hartmann and Stefan Lendl and Gerhard J. Woeginger}, url = {https://arxiv.org/abs/1811.08918}, doi = {10.4230/LIPIcs.STACS.2019.33}, year = {2019}, date = {2019-03-16}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, abstract = {We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance delta from each other. We investigate the complexity of this problem in terms of the rational parameter delta. The problem is polynomially solvable, if the numerator of delta is 1 or 2, while all other cases turn out to be NP-hard.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance delta from each other. We investigate the complexity of this problem in terms of the rational parameter delta. The problem is polynomially solvable, if the numerator of delta is 1 or 2, while all other cases turn out to be NP-hard. |
2018 |
Alese, Leonardo; Lendl, Stefan; Tabatabai, Paul On sequences covering all rainbow k-progressions Journal Article Journal of Combinatorics, 9 (4), pp. 739 – 745, 2018. @article{Alese2018, title = {On sequences covering all rainbow k-progressions}, author = {Leonardo Alese and Stefan Lendl and Paul Tabatabai}, url = {https://arxiv.org/abs/1802.03285}, doi = {10.4310/JOC.2018.v9.n4.a9}, year = {2018}, date = {2018-12-07}, journal = {Journal of Combinatorics}, volume = {9}, number = {4}, pages = {739 – 745}, abstract = {Let ac(n,k) denote the smallest positive integer with the property that there exists an n-colouring f of {1,…,ac(n,k)} such that for every k-subset R⊆{1,…,n} there exists an (arithmetic) k-progression A in {1,…,ac(n,k)} with {f(a):a⊂A}=R. Determining the behaviour of the function ac(n,k) is a previously unstudied problem. We use the first moment method to give an asymptotic upper bound for ac(n,k) for the case k=o(n1/5).}, keywords = {}, pubstate = {published}, tppubtype = {article} } Let ac(n,k) denote the smallest positive integer with the property that there exists an n-colouring f of {1,…,ac(n,k)} such that for every k-subset R⊆{1,…,n} there exists an (arithmetic) k-progression A in {1,…,ac(n,k)} with {f(a):a⊂A}=R. Determining the behaviour of the function ac(n,k) is a previously unstudied problem. We use the first moment method to give an asymptotic upper bound for ac(n,k) for the case k=o(n1/5). |
Ćustić, Ante; Lendl, Stefan Streaming Algorithms for the Steiner Cycle and Path Cover Problem on Interval Graphs Online 2018. @online{Custic2018, title = {Streaming Algorithms for the Steiner Cycle and Path Cover Problem on Interval Graphs}, author = {Ante Ćustić and Stefan Lendl}, url = {https://arxiv.org/abs/1802.08577}, year = {2018}, date = {2018-02-23}, abstract = {We present linear time algorithms for the Steiner path cover and Steiner cycle problems on interval graphs. These problems appear as simplified models for falling platform game levels. We also study these algorithms as streaming algorithms and analyze the necessary memory with respect to the maximum number of intervals contained in another interval. This corresponds to understanding which parts of a level have to be visible at each point to allow the player to make optimal deterministic decisions.}, keywords = {}, pubstate = {published}, tppubtype = {online} } We present linear time algorithms for the Steiner path cover and Steiner cycle problems on interval graphs. These problems appear as simplified models for falling platform game levels. We also study these algorithms as streaming algorithms and analyze the necessary memory with respect to the maximum number of intervals contained in another interval. This corresponds to understanding which parts of a level have to be visible at each point to allow the player to make optimal deterministic decisions. |
