5 citations · 10 across the 7 of their papers we have counts for
10 papers
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…
Individual Fairness in Graph Decomposition
Kamesh Munagala, Govind S. Sankar
In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters which are cohesive in that close-by pairs of no…
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…
Data Exchange Markets via Utility Balancing
Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im +3
This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets of non-negative…
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 -set o…
Online Algorithms for Matchings with Proportional Fairness Constraints and Diversity Constraints
Anand Louis, Meghana Nasre, Prajakta Nimbhorkar +1
Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. More…
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
Dániel Marx, Govind S. Sankar, Philipp Schepper
In the general AntiFactor problem, a graph is given with a set of forbidden degrees for every vertex and the task is to find a set of edges su…
Matchings with Group Fairness Constraints: Online and Offline Algorithms
Govind S. Sankar, Anand Louis, Meghana Nasre +1
We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this…
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Dániel Marx, Govind S. Sankar, Philipp Schepper
For the General Factor problem we are given an undirected graph and for each vertex a finite set of non-negative integers. The task is to decide if there is a…