11 papers
Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
Florian Adriaens, Nikolaj tatti
The Bad Triangle Transversal (BTT) problem asks for the smallest set of edges that need to be removed from a given signed graph, so that the resulting graph does not have a bad tri…
Multilayer Correlation Clustering
Atsushi Miyauchi, Florian Adriaens, Francesco Bonchi +1
We establish Multilayer Correlation Clustering, a novel generalization of Correlation Clustering to the multilayer setting. In this model, we are given a series of inputs of Correl…
Approximating splits for decision trees quickly in sparse data streams
Nikolaj Tatti
Decision trees are one of the most popular classifiers in the machine learning literature. While the most common decision tree learning algorithms treat data as a batch, numerous a…
The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards
Vedangi Bengali, Nikolaj Tatti, Iiro Kumpulainen +2
We consider a generalization of the densest subhypergraph problem where nonnegative rewards are given for including partial hyperedges in a dense subhypergraph. Prior work addresse…
Fair Diversity Maximization with Few Representatives
Florian Adriaens, Nikolaj Tatti
Diversity maximization problem is a well-studied problem where the goal is to find diverse items. Fair diversity maximization aims to select a diverse subset of items from…
Improved Hardness and Approximations for Cardinality-Based Minimum - Cuts Problems in Hypergraphs
Florian Adriaens, Vedangi Bengali, Iiro Kumpulainen +2
In hypergraphs, an edge that crosses a cut (i.e., a bipartition of nodes) can be split in several ways, depending on how many nodes are placed on each side of the cut. A cardinalit…