research
∙
09/03/2023
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Upward planarity testing and Rectilinear planarity testing are central p...
share
research
∙
08/22/2023
Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
Recently, Brand, Ganian and Simonov introduced a parameterized refinemen...
research
∙
07/14/2023
Turán's Theorem Through Algorithmic Lens
The fundamental theorem of Turán from Extremal Graph Theory determines t...
research
∙
05/03/2023
Approximating Long Cycle Above Dirac's Guarantee
Parameterization above (or below) a guarantee is a successful concept in...
research
∙
04/27/2023
A Parameterized Theory of PAC Learning
Probably Approximately Correct (i.e., PAC) learning is a core concept of...
research
∙
01/10/2023
Proportionally Fair Matching with Multiple Groups
The study of fair algorithms has become mainstream in machine learning a...
research
∙
10/13/2022
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
The generic homomorphism problem, which asks whether an input graph G ad...
research
∙
08/26/2022
Testing Upward Planarity of Partial 2-Trees
We present an O(n^2)-time algorithm to test whether an n-vertex directed...
research
∙
07/15/2022
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
We introduce a general method for obtaining fixed-parameter algorithms f...
research
∙
06/03/2022
Weighted Model Counting with Twin-Width
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and ...
research
∙
03/10/2022
Parameterized Algorithms for Upward Planarity
We obtain new parameterized algorithms for the classical problem of dete...
research
∙
02/07/2022
Longest Cycle above Erdős-Gallai Bound
In 1959, Erdős and Gallai proved that every graph G with average vertex ...
research
∙
01/10/2022
Detours in Directed Graphs
We study two "above guarantee" versions of the classical Longest Path pr...
research
∙
12/13/2021
How to Find a Good Explanation for Clustering?
k-means and k-median clustering are powerful unsupervised machine learni...
research
∙
07/20/2021
FPT Approximation for Fair Minimum-Load Clustering
In this paper, we consider the Minimum-Load k-Clustering/Facility Locati...
research
∙
07/15/2021
Lossy Kernelization of Same-Size Clustering
In this work, we study the k-median clustering problem with an additiona...
research
∙
05/08/2021
Parameterized Complexity of Feature Selection for Categorical Data Clustering
We develop new algorithmic methods with provable guarantees for feature ...
research
∙
11/06/2020
Algorithmic Extensions of Dirac's Theorem
In 1952, Dirac proved the following theorem about long cycles in graphs ...
research
∙
10/19/2020
EPTAS for k-means Clustering of Affine Subspaces
We consider a generalization of the fundamental k-means clustering for d...
research
∙
07/20/2020
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
Fair clustering is a constrained variant of clustering where the goal is...
research
∙
02/18/2020
Building large k-cores from sparse graphs
A popular model to measure network stability is the k-core, that is the ...
research
∙
02/18/2020
Manipulating Districts to Win Elections: Fine-Grained Complexity
Gerrymandering is a practice of manipulating district boundaries and loc...
research
∙
05/10/2019
Refined Complexity of PCA with Outliers
Principal component analysis (PCA) is one of the most fundamental proced...
research
∙
04/12/2019
Low-rank binary matrix approximation in column-sum norm
We consider ℓ_1-Rank-r Approximation over GF(2), where for a binary m× n...
research
∙
02/22/2019