notesum.ai

Published at December 3

cs.DS

cs.LG

stat.ML

Released Date: December 3, 2024

Authors: Paul Dütting¹, Federico Fusco², Silvio Lattanzi¹, Ashkan Norouzi-Fard¹, Ola Svensson³, Morteza Zadimoghaddam¹

Aff.: ¹Google Research; ²Sapienza University of Rome; ³École Polytechnique Fédérale de Lausanne

	poly time	info-theoretic
det.	$(0.3818,\nicefrac{{1}}{{2}}]$ Dütting et al. (2024)	$(0.3818,\nicefrac{{1}}{{2}}]$ Dütting et al. (2024)
rand.	$(\mathbf{0.51},1-\nicefrac{{1}}{{e}}]$ Thm. 6.8 & Feige (1998)	$\nicefrac{{\mathbf{3}}}{{\mathbf{4}}}$ (coverage) and $\nicefrac{{\mathbf{2}}}{{\mathbf{3}}}$ (submodular) Thms. 5.5 and 5.7 & Thms. 5.3 and 5.6