On the correlation gap of matroids

DOI10.1007/978-3-031-32726-1_15zbMath1528.05012arXiv2209.09896MaRDI QIDQ6086002

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

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 optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Mechanism design theory (91B03)

Cites Work

• Unnamed Item
• Unnamed Item
• Gross substitutability: an algorithmic survey
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Tight approximation bounds for maximum multi-coverage
• Multi-parameter mechanism design and sequential posted pricing
• Price of Correlations in Stochastic Optimization
• A threshold of ln n for approximating set cover
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Approximation Algorithms for Reliable Stochastic Combinatorial Optimization
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Optimal Auction Design
• Incentives in Teams
• Combinatorial Prophet Inequalities
• On basic operations related to network induction of discrete convex functions
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)