From the 1 of 8 linked papers with an AI index.
8 papers
Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset
Robert Ganian, Manolis Vasilakis, Simon Wietheger
The paper investigates the Minimum Consistent Subset problem, providing faster treewidth‑parameterized algorithms for both weighted and unweighted graphs and proving matching lower…
Speeding Up the NSGA-II via Dynamic Population Sizes
Benjamin Doerr, Martin S. Krejca, Simon Wietheger
Multi-objective evolutionary algorithms (MOEAs) are among the most widely and successfully applied optimizers for multi-objective problems. However, to store many optimal trade-off…
Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
Tian Bai, Fedor V. Fomin, Petr A. Golovach +2
Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational b…
Fair Correlation Clustering Meets Graph Parameters
Johannes Blaha, Robert Ganian, Katharina Gillig +2
We study the generalization of Correlation Clustering which incorporates fairness constraints via the notion of fairlets. The corresponding Fair Correlation Clustering problem has…
Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
Robert Ganian, Marlene Gründel, Simon Wietheger
Pearl's Causal Hierarchy (PCH) is a central framework for reasoning about probabilistic, interventional, and counterfactual statements, yet the satisfiability problem for PCH formu…
Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
Robert Ganian, Hung P. Hoang, Simon Wietheger
We study the computational problem of computing a fair means clustering of discrete vectors, which admits an equivalent formulation as editing a colored matrix into one with few di…