AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Matching in bipartite graphs is a well-studied problem with numerous theoretical as well as practical applications. We consider this problem in the presence of “group fairness constraints”. We refer to the two bipartitions as “items” and “platforms”, and the goal is to assign items to platforms. The items are classified into different groups depending on the properties they possess. Each platform sets its own limit on the number of items that can be assigned to it from each group. The output matching is required to meet these limits.

This problem is NP-hard when the groups can have arbitrary intersections with each other.
We give polynomial-time approximation algorithm for this problem by showing connections to the hypergraph matching problem. We also show that our algorithm leads to an approximation algorithm for a generalization of the hypergraph independent set problem.

This is a joint work with Anand Louis, Meghana Nasre, Govind S. Sankar.

Roohani Sharma

+49 681 9325 1116

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de