On the Correlation Gap of Matroids

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Downloads (Pure)

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 at least 1 - 1 / e, and this is tight for simple matroid rank functions. We initiate a fine-grained study of the correlation gap of matroid rank functions. In particular, we present an improved lower bound on the correlation gap as parametrized by the rank and girth of the matroid. We also show that for any matroid, the correlation gap of its weighted rank function is minimized under uniform weights. Such improved lower bounds have direct applications for submodular maximization under matroid constraints, mechanism design, and contention resolution schemes.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization
Subtitle of host publication24th International Conference, IPCO 2023 Madison, WI, USA, June 21-23, 2023. Proceedings
EditorsAlberto Del Pia, Volker Kaibel
Place of PublicationCham, Switzerland
PublisherSpringer
Pages203-216
Number of pages14
ISBN (Electronic)978-3-031-32726-1
ISBN (Print)978-3-031-32725-4
DOIs
Publication statusPublished - 22 May 2023
Event24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023 - Madison, United States
Duration: 21 Jun 202323 Jun 2023
Conference number: 24

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13904
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023
Abbreviated titleIPCO
Country/TerritoryUnited States
CityMadison
Period21/06/2323/06/23

Keywords

  • 2023 OA procedure

Fingerprint

Dive into the research topics of 'On the Correlation Gap of Matroids'. Together they form a unique fingerprint.

Cite this