New answers tagged


Here's a poly-time dynamic-programming algorithm. Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm. Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, n\}$. For each $t, p\in \{0, 1,\ldots, n\}$, define subproblem $M(t, p)$ as follows. Consider the problem restricted to the first $t$ time slots. (That is, ...


I emailed the author. He replied "yes that paper is wrong!". He has lost the passwords to remove it from the web.


You question is very vague. Let's give it a try. Let $X_1,\ldots,X_n$ be drawn ii from the uniform distribution on $[-1,1]$. For every $\epsilon \ge e^{-n/(2C)}$. With probability at least $1-\exp(-(n/2-C\log(1/\epsilon))^2/(2n))$ the following holds: For ever $x \in [-1/2,1/2]$, there exists $S \subseteq \{1,\ldots,n\}$ such that $|\sum_{i \in S}X_i - x|...

Top 50 recent answers are included