30 citations · 158 across the 36 of their papers we have counts for
46 papers
Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
Luca Pascal Staus, Christian Komusiewicz, Frank Sommer +1
Decision trees are a classic model for summarizing and classifying data. To enhance interpretability and generalization properties, it has been proposed to favor small decision tre…
On Computing Optimal Tree Ensembles
Christian Komusiewicz, Pascal Kunz, Frank Sommer +1
Random forests and, more generally, (decision\nobreakdash-)tree ensembles are widely used methods for classification and regression. Recent algorithmic advances allow to compute de…
Game Implementation: What Are the Obstructions?
Jiehua Chen, Sebastian Vincent Haydn, Negar Layegh Khavidaki +2
In many applications, we want to influence the decisions of independent agents by designing incentives for their actions. We revisit a fundamental problem in this area, called GAME…
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Meike Hatzel, Lars Jaffke, Paloma T. Lima +4
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph , pairs of ve…
The Influence of Dimensions on the Complexity of Computing Decision Trees
Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani +5
A decision tree recursively splits a feature space and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machi…
Turbocharging Heuristics for Weak Coloring Numbers
Alexander Dobler, Manuel Sorge, Anaïs Villedieu
Bounded expansion and nowhere-dense classes of graphs capture the theoretical tractability for several important algorithmic problems. These classes of graphs can be characterized…