Neal Young
  • Member for 9 years, 11 months
  • Last seen this week
Characterization of integral polyhedra
Accepted answer
6 votes

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, ...

View answer
Does such a bipartite graph exist?
Accepted answer
6 votes

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
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
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
kmeans++ for arbitrary metric spaces and general potential function
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
Distinguishability a set of permutations
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
Does randomness buy us anything inside P?
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
Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?
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
Maximum subarray problem with weights
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 $...

View answer
What is the complexity of this submatrix selection problem?
Accepted answer
5 votes

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 ...

View answer
What is the complexity of this weighted b-edge matching problem?
Accepted answer
5 votes

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 ...

View answer
Diving straight into "research" versus studying broadly as an undergrad (soft question)
Accepted answer
5 votes

[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 ...

View answer
A partition problem with order constraints
Accepted answer
5 votes

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 ...

View answer
A coupon collector type problem with changing probabilities
5 votes

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]...

View answer
Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?
5 votes

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. ...

View answer
Parallel Pebble Game on a Line
Accepted answer
5 votes

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}$ ...

View answer
A game of positioning overlapping circles to maximize travel time between them
5 votes

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: ...

View answer
Maximizing sum edge weights
5 votes

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 ...

View answer
expected number of sets generated by greedy set cover ?
Accepted answer
5 votes

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 ...

View answer
Does such a graph exist?
4 votes

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
Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?
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
Partition the edges of a bipartite graph into perfect $b$-matchings
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
Is that edge orientation optimization problem NP-hard?
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 ...

View answer
Can a result of (any) hash algorithm contain the hash result itself?
Accepted answer
4 votes

For the first question, about the last line, it surely depends on the hash function. For example, suppose each line is a single bit (0 or 1). If the hash function is the xor of the bits, then the ...

View answer
Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?
Accepted answer
4 votes

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
Minimum non-zero variable in the optimal solution of linear programming
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
Approximation Ratio of Local search for $k-$center problem
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
Minimizing entropy plus a modular function
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
Is there a simplex-like algorithm that can be used with a separation oracle?
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
Is there any Bi-criteria PTAS for Metric $k$-Median?
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
What is the polynomial representation of the Hamming weight function?
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) = ...

View answer