A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915970485846016 |
|---|---|
| author | Li, Shisheng |
| author_facet | Li, Shisheng |
| contents | Buchbinder and Feldman recently gave a deterministic $(1-1/e-\varepsilon)$-approximation for maximizing a non-negative monotone submodular function subject to a matroid constraint, with query complexity $\widetilde{O}_\varepsilon(nr)$. Their algorithm uses an integer parameter $\ell$, which Buchbinder and Feldman fix to $\ell = 1 + \lceil 1/\varepsilon \rceil$ via a loose bound on $(1+1/\ell)^{-\ell}$. We point out two purely elementary refinements. First, the classical Pólya--Szegő inequality $(1+1/\ell)^{-\ell} \le e^{-1}(1+1/(2\ell))$ replaces the loose step in their proof and permits $\ell = \lceil 1/(2e\varepsilon) \rceil$, shrinking the hidden constant in $\widetilde{O}_\varepsilon(nr)$ by a factor $\approx 2^{0.816/\varepsilon}$. Second, an alternating-series tail bound for $\log(1+t)$ yields the asymptotically sharp inequality $(1+1/\ell)^{-\ell} \le e^{-1}\exp(1/(2\ell) - 1/(3\ell^2) + 1/(4\ell^3))$, matching the true expansion of $(1+1/\ell)^{-\ell}$ through order $\ell^{-3}$ and translating into $\ell_\star = 1/(2e\varepsilon) - 5/12 + O(\varepsilon)$. The asymptotic class $\widetilde{O}_\varepsilon(nr)$ of the query complexity is unchanged in either case; only the implicit constant in $\varepsilon$ is improved. All inequalities in this note are formalized and machine-checked in Lean 4 against Mathlib. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27362 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm Li, Shisheng Data Structures and Algorithms 68W25, 90C27 F.2.2; G.2.1 Buchbinder and Feldman recently gave a deterministic $(1-1/e-\varepsilon)$-approximation for maximizing a non-negative monotone submodular function subject to a matroid constraint, with query complexity $\widetilde{O}_\varepsilon(nr)$. Their algorithm uses an integer parameter $\ell$, which Buchbinder and Feldman fix to $\ell = 1 + \lceil 1/\varepsilon \rceil$ via a loose bound on $(1+1/\ell)^{-\ell}$. We point out two purely elementary refinements. First, the classical Pólya--Szegő inequality $(1+1/\ell)^{-\ell} \le e^{-1}(1+1/(2\ell))$ replaces the loose step in their proof and permits $\ell = \lceil 1/(2e\varepsilon) \rceil$, shrinking the hidden constant in $\widetilde{O}_\varepsilon(nr)$ by a factor $\approx 2^{0.816/\varepsilon}$. Second, an alternating-series tail bound for $\log(1+t)$ yields the asymptotically sharp inequality $(1+1/\ell)^{-\ell} \le e^{-1}\exp(1/(2\ell) - 1/(3\ell^2) + 1/(4\ell^3))$, matching the true expansion of $(1+1/\ell)^{-\ell}$ through order $\ell^{-3}$ and translating into $\ell_\star = 1/(2e\varepsilon) - 5/12 + O(\varepsilon)$. The asymptotic class $\widetilde{O}_\varepsilon(nr)$ of the query complexity is unchanged in either case; only the implicit constant in $\varepsilon$ is improved. All inequalities in this note are formalized and machine-checked in Lean 4 against Mathlib. |
| title | A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm |
| topic | Data Structures and Algorithms 68W25, 90C27 F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2604.27362 |