5 papers · 1 filter
Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset
Robert Ganian, Manolis Vasilakis, Simon Wietheger
Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretica…
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…
A Strategic Routing Framework and Algorithms for Computing Alternative Paths
Thomas Bläsius, Maximilian Böther, Philipp Fischbeck +9
Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have un…