We show that set cover on a universe of size $n$ and with sets of size at most $k$ can be solved in time $2^{(1-1/k+O(1/k^{3/2}))n}$. This improves on a $2^{(1-0.929/k)n}$-time algorithm of Bj\"orklund (STACS 2010) for all sufficiently large $k$.
A randomized algorithm returns a $(1\pm\varepsilon)-approximation with failure probability at most $\delta$ in $O^*(2^k\varepsilon^{-2}\log(1/\delta)$ time.
We determine, up to a factor of $2^{o(k)}$, the number of $k$-sets $A \subset \{1, \ldots, n\}$ such that $|A + A| \leq m$, where $k = \Theta(\log n)$ and $m \leq k^{1 + \alpha}$, for small $\alpha>0$, answering a question of Green and Morris.
Let $\lambda$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $\alpha>1$, we prove that there are $O(n^{\lceil2\alpha\rceil-1})$ cuts of size strictly below $\alpha\lambda$. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families...
After the initial idea for the main proof was found by the authors, various AI models were used to streamline the argument and perform the calculations necessary for completion of the proof.
Let $A$ be the smallest set of positive integers containing $2$ and $3$ such that $ab-1\in A$ whenever $a,b\in A$ are distinct. We prove that $A$ has positive lower density, answering a problem of Erd\H{o}s attributed to Hofstadter.
The first $\widetilde O_k(n^{ck})$-time algorithm for Minimum $k$-Cut on simple graphs for an absolute constant $c<1$ is given.
We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.
