New answers tagged np-hardness
3
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, ...
4
I emailed the author.
He replied "yes that paper is wrong!".
He has lost the passwords to remove it from the web.
0
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
