13 citations · 33 across the 14 of their papers we have counts for
14 papers
CKR Partitions and Lower Bounds for Constrained Correlation Clustering and Variants
Florian Adriaens
By using a simple textbook reduction from vertex cover, we show that the following three problems are all UG-hard to approximate with constant-factor smaller than two; minimum weak…
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…
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…
Max-Min Diversification with Asymmetric Distances
Iiro Kumpulainen, Florian Adriaens, Nikolaj Tatti
One of the most well-known and simplest models for diversity maximization is the Max-Min Diversification (MMD) model, which has been extensively studied in the data mining and data…
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…
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…
Minimizing Hitting Time between Disparate Groups with Shortcut Edges
Florian Adriaens, Honglian Wang, Aristides Gionis
Structural bias or segregation of networks refers to situations where two or more disparate groups are present in the network, so that the groups are highly connected internally, b…
Diameter Minimization by Shortcutting with Degree Constraints
Florian Adriaens, Aristides Gionis
We consider the problem of adding a fixed number of new edges to an undirected graph in order to minimize the diameter of the augmented graph, and under the constraint that the num…
Improved analysis of randomized SVD for top-eigenvector approximation
Ruo-Chun Tzeng, Po-An Wang, Florian Adriaens +2
Computing the top eigenvectors of a matrix is a problem of fundamental interest to various fields. While the majority of the literature has focused on analyzing the reconstruction…
Testing properties of signed graphs
Florian Adriaens, Simon Apers
In graph property testing the task is to distinguish whether a graph satisfies a given property or is "far" from having that property, preferably with a sublinear query and time co…
Block-Approximated Exponential Random Graphs
Florian Adriaens, Alexandru Mara, Jefrey Lijffijt +1
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. By utilizing fast matrix block-approximation techniques,…
Discovering Interesting Cycles in Directed Graphs
Florian Adriaens, Cigdem Aslay, Tijl De Bie +2
Cycles in graphs often signify interesting processes. For example, cyclic trading patterns can indicate inefficiencies or economic dependencies in trade networks, cycles in food we…
From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths
Florian Adriaens, Tijl De Bie, Aristides Gionis +2
Social networks often provide only a binary perspective on social ties: two individuals are either connected or not. While sometimes external information can be used to infer the s…