Tom-Lukas Breitkopf

Tom-Lukas Breitkopf, Leonard W. Hackel, Mahdyar Ravanbakhsh et al.

Subsurface tile drainage pipes provide agronomic, economic and environmental benefits. By lowering the water table of wet soils, they improve the aeration of plant roots and ultimately increase the productivity of farmland. They do however also provide an entryway of agrochemicals into subsurface water bodies and increase nutrition loss in soils. For maintenance and infrastructural development, accurate maps of tile drainage pipe locations and drained agricultural land are needed. However, these maps are often outdated or not present. Different remote sensing (RS) image processing techniques have been applied over the years with varying degrees of success to overcome these restrictions. Recent developments in deep learning (DL) techniques improve upon the conventional techniques with machine learning segmentation models. In this study, we introduce two DL-based models: i) improved U-Net architecture; and ii) Visual Transformer-based encoder-decoder in the framework of tile drainage pipe detection. Experimental results confirm the effectiveness of both models in terms of detection accuracy when compared to a basic U-Net architecture. Our code and models are publicly available at https://git.tu-berlin.de/rsim/drainage-pipes-detection.

Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann et al.

We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem which is known to be NP-hard. While approximation algorithms and polynomial-time algorithms for some graph classes are known, the parameterized complexity of the problem has not been investigated so far. We start a parameterized complexity analysis with the goal of determining the border of algorithmic tractability for the MAD tree problem. To this end, we provide a linear-time algorithm for graphs of constant modular width and a polynomial-time algorithm for graphs of bounded treewidth; the degree of the polynomial depends on the treewidth. That is, the problem is in FPT with respect to modular width and in XP with respect to treewidth. Moreover, we show it is in FPT when parameterized by vertex integrity or by an above-guarantee parameter. We complement these algorithms with NP-hardness on split graphs.

Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek et al.

Population protocols are a model of distributed computing where $n$ agents, each a simple finite-state machine, interact in pairs to solve a common task against a (adversarial) interaction scheduler. This model was intensively studied in recent years; in particular, the problem of relative majority received much attention: Each agent starts with an input opinion (or color) out of $k$ possibilities, and the goal is for each agent to eventually output the color with the largest support in the population. Before our work, the state complexity (the minimum number of states required per agent) was only known to be between $Ω(k^2)$ and $O(k^{7})$. Our main contribution is a population protocol that solves the relative majority problem with $k^3$ states. We achieve this result with a new protocol called CIRCLES. While prior approaches in the literature relied on duels of agents to find the majority color -- an approach that proved effective for the case with two colors -- CIRCLES partitions the agents into circular linked lists of decreasing sizes, with the property that no two agents with the same initial color lie in the same circle. We show that CIRCLES always correctly computes the desired structure against the most adversarial of schedulers (weakly fair). We then show that a trivial extension of CIRCLES solves the relative majority problem. We extend our protocol to handle various tie-breaking mechanisms or to support the case where the agents do not share a prior ordering of the colors. Finally, we show that a modification of CIRCLES solves the ranking problem with $2 \cdot k^4$ states, where each agent must output the rank of its initial color in the population.