02/02/2021

Minimum Robust Multi-Submodular Cover for Fairness

Lan N. Nguyen, My T. Thai

Keywords:

Abstract Paper Similar Papers

Abstract: In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MinRF), as follows: given a ground set V; m monotone submodular functions f_1,...,f_m; m thresholds T_1,...,T_m and a non-negative integer r; MinRF asks for the smallest set S such that f_i(S \ X) ≥ T_i for all i ∈ [m] and |X| ≤ r. We prove that MinRF is inapproximable within (1- ε) ln m; and no algorithm, taking fewer than exponential number of queries in term of r, is able to output a feasible set to MinRF with high certainty. Three bicriteria approximation algorithms with performance guarantees are proposed: one for r = 0, one for r = 1, and one for general r. We further investigate our algorithms' performance in two applications of MinRF, Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. Our algorithms have shown to outperform baseline heuristics in both solution quality and the number of queries in most cases.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949310
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 12:58 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 10:44 
 0
 0
 0
 0
 14:21 
 0
 0
 0
 0
 7:26 
 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 14:36 
 0
 0
 0
 0
 4:56 
 0
 0
 0
 0
 4:37 
 0
 0
 0
 0
 4:42 
 0
 0
 0
 0
 15:04 
 0
 0
 0
 0
 18:17 
 0
 0
 0
 0
 5:10 
 0
 0
 0
 0
 11:35 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 3:13 
 0
 0
 0
 0
 2:56 
 0
 0
 0
 0
 13:46 
 0
 0
 0
 0
 14:45 
 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 5:51 
 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 14:02 
 0
 0
 0
 0
 3:03 
 0
 0
 0
 0
 25:10 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 29:37 
 0
 0
 0
 0
 16:37 
 0
 0
 0
 0
 14:21 
 0
 0
 0
 0
 5:26 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 11:15 
 0
 0
 0
 0
 3:17 
 0
 0
 0
 0
 21:03 
 0
 0
 0
 0
 16:29 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 19:52 
 0
 0
 0
 0
 15:19 
 0
 0
 0
 0
 14:11