DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2025.52

Beating Competitive Ratio 4 for Graphic Matroid Secretary

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.

Cite as

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski. Beating Competitive Ratio 4 for Graphic Matroid Secretary. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ESA.2025.52,
  author =	{Banihashem, Kiarash and Hajiaghayi, MohammadTaghi and Kowalski, Dariusz R. and Krysta, Piotr and Mittal, Danny and Olkowski, Jan},
  title =	{{Beating Competitive Ratio 4 for Graphic Matroid Secretary}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.52},
  URN =		{urn:nbn:de:0030-drops-245205},
  doi =		{10.4230/LIPIcs.ESA.2025.52},
  annote =	{Keywords: online algorithms, graphic matroids, secretary problem}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.19

Dynamic Algorithms for Submodular Matching

Authors: Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

The Maximum Submodular Matching (MSM) problem is a generalization of the classical Maximum Weight Matching (MWM) problem. In this problem, given a monotone submodular function f: 2^E → ℝ^{≥ 0} defined over subsets of edges of a graph G(V, E), we are asked to return a matching whose submodular value is maximum among all matchings in graph G(V, E). In this paper, we consider this problem in a fully dynamic setting against an oblivious adversary. In this setting, we are given a sequence 𝒮 of insertions and deletions of edges of the underlying graph G(V, E), along with an oracle access to the monotone submodular function f. The goal is to maintain a matching M such that, at any time t of sequence 𝒮, its submodular value is a good approximation of the value of the optimal submodular matching while keeping the number of operations minimal. We develop the first dynamic algorithm for the submodular matching problem, in which we maintain a matching whose submodular value is within expected (8 + ε)-approximation of the optimal submodular matching at any time t of sequence 𝒮 using expected amortized poly(log n, 1/(ε)) update time. Our approach incorporates a range of novel techniques, notably the concept of Uniform Hierarchical Caches (UHC) data structure along with its invariants, which lead to the first algorithm for fully dynamic submodular matching and may be of independent interest for designing dynamic algorithms for other problems.

Cite as

Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic Algorithms for Submodular Matching. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ICALP.2025.19,
  author =	{Banihashem, Kiarash and Biabani, Leyla and Goudarzi, Samira and Hajiaghayi, MohammadTaghi and Jabbarzade, Peyman and Monemizadeh, Morteza},
  title =	{{Dynamic Algorithms for Submodular Matching}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.19},
  URN =		{urn:nbn:de:0030-drops-233969},
  doi =		{10.4230/LIPIcs.ICALP.2025.19},
  annote =	{Keywords: Matching, Submodular, Dynamic, Polylogarithmic}
}

Search Results

Documents authored by Banihashem, Kiarash

Beating Competitive Ratio 4 for Graphic Matroid Secretary

Abstract

Cite as

Dynamic Algorithms for Submodular Matching

Abstract

Cite as

Thanks for your feedback!

Could not send message