2019/05/21 by Simon Bruggmann, Rico Zenklusen, Bruggmann, Simon +1 · 1 citation
Computer Science · #68W20 #68W25 (Secondary) #90C27 (Primary) #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1905.08658
openalex publication_date 2019/05/21 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
Relaxation and rounding approaches became a standard and extremely versatile\ntool for constrained submodular function maximization. One of the most common\nrounding techniques in this context are contention resolution schemes. Such\nschemes round a fractional point by first rounding each coordinate\nindependently, and then dropping some elements to reach a feasible set. Also\nthe second step, where elements are dropped, is typically randomized. This\nleads to an additional source of randomization within the procedure, which can\ncomplicate the analysis. We suggest a different, polyhedral viewpoint to design\ncontention resolution schemes, which avoids to deal explicitly with the\nrandomization in the second step. This is achieved by focusing on the marginals\nof a dropping procedure. Apart from avoiding one source of randomization, our\nviewpoint allows for employing polyhedral techniques. Both can significantly\nsimplify the construction and analysis of contention resolution schemes. We\nshow how, through our framework, one can obtain an optimal monotone contention\nresolution scheme for bipartite matchings. So far, only very few results are\nknown about optimality of monotone contention resolution schemes. Our\ncontention resolution scheme for the bipartite case also improves the lower\nbound on the correlation gap for bipartite matchings. Furthermore, we derive a\nmonotone contention resolution scheme for matchings that significantly improves\nover the previously best one. At the same time, our scheme implies that the\ncurrently best lower bound on the correlation gap for matchings is not tight.\nOur results lead to improved approximation factors for various constrained\nsubmodular function maximization problems over a combination of matching\nconstraints with further constraints.\n