Author

Zhao-Feng Song

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Sep 2026

Three Standard Deviations Suffice While One Does Not

Spencer's 1985 ``six standard deviations suffice''theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4<2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential func...

Victor Reis, Zhao-Feng Song · 0 citations

Preprint Sep 2026

A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP

Karlin, Klein, and Oveis Gharan introduced a randomized better-than-$3/2$ approximation algorithm for metric TSP [KKO21] and subsequently established the corresponding improvement in the integrality gap of the subtour-elimination LP [KKO22], with an explicit constant $\varepsilon>1.00000\cdot10^{-36}$. Gurvits, Klein,...

Zhao-Feng Song · 0 citations