From the 1 of 9 linked papers with an AI index.
5 papers · 1 filter
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…
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…
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…
Parameterized Complexity of Efficient Sortation
Robert Ganian, Hung P. Hoang, Simon Wietheger
A crucial challenge arising in the design of large-scale logistical networks is to optimize parcel sortation for routing. We study this problem under the recent graph-theoretic for…