3 papers
cs.DS2026
Balanced Spanning Tree Distributions Have Separation Fairness
Harry Chen, Kamesh Munagala, Govind S. Sankar
Sampling-based methods such as ReCom are widely used to audit redistricting plans for fairness, with the balanced spanning tree distribution playing a central role since it favors…
cs.DS2025
Group Fairness and Multi-criteria Optimization in School Assignment
Santhini K. A., Kamesh Munagala, Meghana Nasre +1
We consider the problem of assigning students to schools, when students have different utilities for schools and schools have capacity. There are additional group fairness consider…
cs.CC2025
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets of non-negative integers, a -s…