2019

Lendl, Stefan; Ćustić, Ante; Punnen, Abraham P Combinatorial optimization with interaction costs: Complexity and solvable cases Journal Article Discrete Optimization, 33 , pp. 101117, 2019. Abstract  Links  BibTeX @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 = {20190801},
journal = {Discrete Optimization},
volume = {33},
pages = {101117},
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. Abstract  Links  BibTeX @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 = {20190710},
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 polynomialtime 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 polynomialtime primaldual 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 stronglypolynomial, primaldual 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 polynomialtime 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 polynomialtime primaldual 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 stronglypolynomial, primaldual 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. Abstract  BibTeX @unpublished{Lachmann2019,
title = {Efficient Algorithms for the Recoverable (Robust) Selection Problem},
author = {Thomas Lachmann and Stefan Lendl},
year = {2019},
date = {20190401},
abstract = { We study the probl{Recoverable Selection} problem, a generalization of the
wellstudied 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
discreteconvexity 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
wellstudied 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
discreteconvexity 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. Abstract  Links  BibTeX @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 = {20190316},
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 NPhard.},
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 NPhard. 
2018

Alese, Leonardo; Lendl, Stefan; Tabatabai, Paul On sequences covering all rainbow kprogressions Journal Article Journal of Combinatorics, 9 (4), pp. 739 – 745, 2018. Abstract  Links  BibTeX @article{Alese2018,
title = {On sequences covering all rainbow kprogressions},
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 = {20181207},
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 ncolouring f of {1,…,ac(n,k)} such that for every ksubset R⊆{1,…,n} there exists an (arithmetic) kprogression 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 ncolouring f of {1,…,ac(n,k)} such that for every ksubset R⊆{1,…,n} there exists an (arithmetic) kprogression 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. Abstract  Links  BibTeX @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 = {20180223},
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. 