On the correlation gap of matroids

DOI10.1007/S10107-024-02116-WMaRDI QIDQ7019065zbMATH OpenFDO

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

Publication date 5 March 2025

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-024-02116-W

zbMATH Keywords

lower boundweighted rank function

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial optimization (90C27)

Cites work

• A new approximation guarantee for monotone submodular function maximization via discrete convexity
• A threshold of ln n for approximating set cover
• Algorithmic Game Theory
• An analysis of approximations for maximizing submodular set functions—I
• Approximation algorithms for reliable stochastic combinatorial optimization
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial prophet inequalities
• Discrete Convex Analysis
• Gross substitutability: an algorithmic survey
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 6783427 (Why is no real title available?)
• scientific article; zbMATH DE number 7829290 (Why is no real title available?)
• Incentives in Teams
• Job Matching, Coalition Formation, and Gross Substitutes
• 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
• NIST handbook of mathematical functions
• 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 approximation for submodular and supermodular optimization with bounded curvature
• Optimal approximation for the submodular welfare problem in the value oracle model
• Optimal Auction Design
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Price of correlations in stochastic optimization
• Simpler exchange axioms for M-concave functions on generalized polymatroids
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Tight approximation bounds for maximum multi-coverage
• Valuated matroids
• Walrasian equilibrium with gross substitutes

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 Q7019065)