Search Results

Documents authored by Klein, Nathan

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.79
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

Authors: Leonid Gurvits, Nathan Klein, and Jonathan Leake

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of their approximation factor for metric TSP. Our results also allow for a more streamlined analysis of the algorithm. To achieve these new bounds, we build upon the work of Gurvits-Leake on the use of the productization technique for bounding the capacity of a real stable polynomial. This technique allows one to reduce certain inequalities for real stable polynomials to products of affine linear forms, which have an underlying matrix structure. In this paper, we push this technique further by characterizing the worst-case polynomials via bipartitioned forests. This rigid combinatorial structure yields a clean induction argument, which implies our stronger bounds. In general, we believe the results of this paper will lead to further improvement and simplification of the analysis of various combinatorial and probabilistic bounds and algorithms.
Cite as

Leonid Gurvits, Nathan Klein, and Jonathan Leake. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gurvits_et_al:LIPIcs.ICALP.2024.79,
  author =	{Gurvits, Leonid and Klein, Nathan and Leake, Jonathan},
  title =	{{From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.79},
  URN =		{urn:nbn:de:0030-drops-202229},
  doi =		{10.4230/LIPIcs.ICALP.2024.79},
  annote =	{Keywords: traveling salesman problem, strongly Rayleigh distributions, polynomial capacity, probability lower bounds, combinatorial lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.2
Matroid Partition Property and the Secretary Problem

Authors: Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
A matroid M on a set E of elements has the α-partition property, for some α > 0, if it is possible to (randomly) construct a partition matroid 𝒫 on (a subset of) elements of M such that every independent set of 𝒫 is independent in M and for any weight function w:E → ℝ_{≥0}, the expected value of the optimum of the matroid secretary problem on 𝒫 is at least an α-fraction of the optimum on M. We show that the complete binary matroid, B_d on 𝔽₂^d does not satisfy the α-partition property for any constant α > 0 (independent of d). Furthermore, we refute a recent conjecture of [Kristóf Bérczi et al., 2021] by showing the same matroid is 2^d/d-colorable but cannot be reduced to an α 2^d/d-colorable partition matroid for any α that is sublinear in d.
Cite as

Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2,
  author =	{Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan},
  title =	{{Matroid Partition Property and the Secretary Problem}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.2},
  URN =		{urn:nbn:de:0030-drops-175051},
  doi =		{10.4230/LIPIcs.ITCS.2023.2},
  annote =	{Keywords: Online algorithms, Matroids, Matroid secretary problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact