On the correlation gap of matroids

DOI10.1007/978-3-031-32726-1_15MaRDI QIDQ6086002zbMATH OpenFDO

Authors Edin Husić, Zhuan Khye Koh, Georg Loho, László A. Végh

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.09896

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial optimization (90C27) Mechanism design theory (91B03)

Abstract: A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is $1-1/e$, and this is tight even for simple matroid rank functions. We initiate a fine-grained study of correlation gaps of matroid rank functions. In particular, we present improved lower bounds on the correlation gap as parametrized by the rank and the girth of the matroid. We also show that the worst correlation gap of a weighted matroid rank function is achieved under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes. Previous work relied on implicit correlation gap bounds for problems such as list decoding and approval voting.

Recommendations

• scientific article; zbMATH DE number 6783427
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Understanding the correlation gap for matchings
• Maximizing a monotone submodular function subject to a matroid constraint
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem

Cites work

• A threshold of ln n for approximating set cover
• Approximation algorithms for reliable stochastic combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial prophet inequalities
• Computationally feasible VCG mechanisms
• Gross substitutability: an algorithmic survey
• scientific article; zbMATH DE number 6783427 (Why is no real title available?)
• Incentives in Teams
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Multi-parameter mechanism design and sequential posted pricing
• On basic operations related to network induction of discrete convex functions
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Optimal Auction Design
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Price of correlations in stochastic optimization
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Tight approximation bounds for maximum multi-coverage

This page was built for publication: On the correlation gap of matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086002)