Neal Young
• Member for 9 years, 11 months
• Last seen this week

Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below. EDIT: But, ...

Theorem 1. For every $d$ and $k$, there is a graph with the desired properties. I'll describe the construction in two stages. First, construct a bipartite multi-graph $G_1=(L_1, R_1, E_1)$ where $L_1=... View answer Accepted answer 6 votes Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT. Proof. Call the given problem Positive Discrepancy Cut (PDC). Define weighted PDC to be the generalization where the input is a ... View answer Accepted answer 6 votes Here's an example that suggests that the stronger claim in the earlier version (Lemma 5.3) is false. I've only given a cursory look at the papers, so please check this carefully to make sure I am ... View answer Accepted answer 6 votes Here are loose lower and upper bounds. Fix$d \le n$as in the post. Let$k^*$denote the largest possible value of$k$meeting the conditions in the post. We show that$k^* = \exp(\Theta(d\log d)$... View answer 6 votes Given an$n\times n$payoff matrix for a zero-sum matrix with payoffs in [0,1], estimate the value of the game within an additive$\epsilon$. This problem has a randomized algorithm that runs in time ... View answer 5 votes Theorem 1. For all$n\ge 6$and$T$with$n+14\le T \le 7{n\choose 3}$, there is a satisfiable 3-SAT formula on$n$variables with$T$clauses in which all clauses are redundant. Before we give the ... View answer Accepted answer 5 votes Please check the following proof, and see the final remark with a link to code for an$O(n)$-time algorithm. Theorem 1. There is an$O(n\log n)$-time algorithm for the problem. Proof. Fix an instance$...

EDIT: Added an answer meeting the unique-sum requirement. Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique. Proof. Here's the reduction. First ...

Assuming $x(e)=1$ in Condition 2, the problem is NP-complete. Clearly it is in NP. We show NP-hardness by reduction from Subset Sum: Lemma 1. The problem is NP-hard. Proof. The proof is by the ...

[This is really a comment, but too long to fit in a comment field.] You seem to be exceptionally well prepared compared to most students at the end of your freshman year. And I'm not sure what you ...

Intuitively, the intermediate cases should be neither in P, nor NP-hard. Perhaps it depends exactly on what we mean by "intermediate case". Here is one interpretation for which we can prove ...

Lemma. In the unbounded case, the expected number of flips is at most $\sqrt t + 3/2$. Proof. Let r.v. $F$ be the number of flips until a head. Then the expected number of flips is \begin{align} E[F]...

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum. Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op. Here is the intuition. ...

EDITS: Added Lemmas 2 and 3. Here's a partial answer: You can reach position $N$ in $N$ moves using space $N^{O(\epsilon(N))}$, where $\epsilon(N) = 1/\sqrt{\log N}$. (Lemma 1) in $N^{1+\delta}$ ...

David E. conjectured "Maybe the answer would be different if the bug walked directly to the closest point in the current intersection, rather than towards the center of the new circle?" (EDIT: ...

FWIW, your problem is hard to approximate within a multiplicative factor of $n^{1-\epsilon}$ for any $\epsilon>0$. We show that below by giving an approximation-preserving reduction from ...

Given that a cover exists, greedy will return a cover of expected size $O(p^{-1}\log n)$. As long as $k$ is not too large, with high probability every cover has size $\Omega(p^{-1}\log n)$ This ...

EDIT: The answers below are for previous versions of the question. Answer for third version: [This version asked for an edge-colored graph $G$ with a vertex $r$ such that has exactly three edges $a,b,... View answer Accepted answer 4 votes Theorem 1. The problem in the post is NP-complete. Proof. MIN DNF is the following special case of the problem in the post: Given a truth table$T$and integer$k$, is there a DNF of size at most$k$... View answer Accepted answer 4 votes Here's a counter-example for$k= 4$. Take$G = K_{2,2}$, specifically$G=(V, E)$where$V=\{1,2,3,4\}$and$E=\{(1,3), (1, 4), (2,3), (2,4)\}$. Define$b^1$by$b^1_1 = b^1_3 = 1$and$b^1_2=b^1_4=0$. ... View answer 4 votes We answer OP's last question: can an approximate solution to IQP be obtained by randomized rounding? We show that the natural randomized-rounding scheme gives a 2-approximation, and a$(1+1/\overline ...

EDIT: Merged the two answers. Here's the problem statement: The input is $(V, \mathbf b, \ell)$, where $V=\{x_1,x_2,\ldots,x_n\}$ with each $x_i\in\{0,1\}^d$ (where $d$ is constant), vector $\textbf{... View answer Accepted answer 4 votes No, it is not always possible. The illustration below shows an example in which the smallest non-zero value must be$1/2^{\Omega(n)}$. The example is shown in the top of the illustration. Round ... View answer Accepted answer 4 votes Local search (with a single swap) doesn't give you a good approximation factor in the worst case for$k$-center, as illustrated by the following example. Take a simplex in$\mathbb{R}^{k-1}$, and put ... View answer Accepted answer 4 votes Unless I'm mistaken, you can solve your problem in$O(n\log n)$time using a greedy algorithm. Minimizing$f(S)$is equivalent to maximizing$$\textstyle g(S') = \sum_{i \in S'} b_i + \big(\sum_{i\in ... View answer 3 votes I'm not sure if you would consider the algorithms I'll discuss here "Simplex-like" (but see the comment about column generation at the end). If you have a weak separation oracle for a ... View answer Accepted answer 3 votes We improve Chandra's bound, as he conjectured was possible, giving an approximation algorithm that opens$f(k,\epsilon)=O(k\log (1/\epsilon))$facilities to obtain assignment cost at most$1+\epsilon$... View answer Accepted answer 3 votes Here is the polynomial representation of any such function$f$: For any$y\in \{-1,1\}^n$, define polynomial$I_y(x) = 2^{-n}\prod_{i=1}^n 1+y_i x_i.$Then for all$x\in\{-1,1\}^n$we have$I_y(x) = ...