On the Correlation Gap of Matroids

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

doi:10.1007/978-3-031-32726-1_15

On the Correlation Gap of Matroids

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

^*Corresponding author for this work

Mathematics of Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

23 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 language	English
Title of host publication	Integer Programming and Combinatorial Optimization
Subtitle of host publication	24th International Conference, IPCO 2023 Madison, WI, USA, June 21-23, 2023. Proceedings
Editors	Alberto Del Pia, Volker Kaibel
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	203-216
Number of pages	14
ISBN (Electronic)	978-3-031-32726-1
ISBN (Print)	978-3-031-32725-4
DOIs	https://doi.org/10.1007/978-3-031-32726-1_15
Publication status	Published - 22 May 2023
Event	24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023 - Madison, United States Duration: 21 Jun 2023 → 23 Jun 2023 Conference number: 24

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13904
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023
Abbreviated title	IPCO
Country/Territory	United States
City	Madison
Period	21/06/23 → 23/06/23

Keywords

2023 OA procedure

Access to Document

10.1007/978-3-031-32726-1_15

ArticleFinal published version, 373 KBLicence: Taverne

Cite this

Husić, E., Koh, Z. K., Loho, G., & Végh, L. A. (2023). On the Correlation Gap of Matroids. In A. Del Pia, & V. Kaibel (Eds.), Integer Programming and Combinatorial Optimization: 24th International Conference, IPCO 2023 Madison, WI, USA, June 21-23, 2023. Proceedings (pp. 203-216). (Lecture Notes in Computer Science; Vol. 13904). Springer. https://doi.org/10.1007/978-3-031-32726-1_15

@inproceedings{4fa9f56c3ccc4e80a16da2683a1a8c36,

title = "On the Correlation Gap of Matroids",

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.",

keywords = "2023 OA procedure",

author = "Edin Husi{\'c} and Koh, {Zhuan Khye} and Georg Loho and V{\'e}gh, {L{\'a}szl{\'o} A.}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023, IPCO ; Conference date: 21-06-2023 Through 23-06-2023",

year = "2023",

month = may,

day = "22",

doi = "10.1007/978-3-031-32726-1_15",

language = "English",

isbn = "978-3-031-32725-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "203--216",

editor = "{Del Pia}, Alberto and Volker Kaibel",

booktitle = "Integer Programming and Combinatorial Optimization",

address = "Germany",

}

Husić, E, Koh, ZK, Loho, G & Végh, LA 2023, On the Correlation Gap of Matroids. in A Del Pia & V Kaibel (eds), Integer Programming and Combinatorial Optimization: 24th International Conference, IPCO 2023 Madison, WI, USA, June 21-23, 2023. Proceedings. Lecture Notes in Computer Science, vol. 13904, Springer, Cham, Switzerland, pp. 203-216, 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023, Madison, Wisconsin, United States, 21/06/23. https://doi.org/10.1007/978-3-031-32726-1_15

On the Correlation Gap of Matroids. / Husić, Edin; Koh, Zhuan Khye; Loho, Georg et al.
Integer Programming and Combinatorial Optimization: 24th International Conference, IPCO 2023 Madison, WI, USA, June 21-23, 2023. Proceedings. ed. / Alberto Del Pia; Volker Kaibel. Cham, Switzerland: Springer, 2023. p. 203-216 (Lecture Notes in Computer Science; Vol. 13904).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the Correlation Gap of Matroids

AU - Husić, Edin

AU - Koh, Zhuan Khye

AU - Loho, Georg

AU - Végh, László A.

N1 - Conference code: 24

PY - 2023/5/22

Y1 - 2023/5/22

N2 - 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.

AB - 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.

KW - 2023 OA procedure

UR - http://www.scopus.com/inward/record.url?scp=85163374975&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-32726-1_15

DO - 10.1007/978-3-031-32726-1_15

M3 - Conference contribution

AN - SCOPUS:85163374975

SN - 978-3-031-32725-4

T3 - Lecture Notes in Computer Science

SP - 203

EP - 216

BT - Integer Programming and Combinatorial Optimization

A2 - Del Pia, Alberto

A2 - Kaibel, Volker

PB - Springer

CY - Cham, Switzerland

T2 - 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023

Y2 - 21 June 2023 through 23 June 2023

ER -