Neal Young
  • Member for 9 years, 11 months
  • Last seen this week
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 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
2-Center problem with forbidden pairs
Accepted answer
1 votes

Maybe this will give ideas for a faster algorithm: Theorem 1. There's an $O(n^2 \log n)$-time 2-approximation algorithm. Proof. Here's the algorithm: Using binary search over the $O(n^2)$-pairwise ...

View answer
Set cover with rewards
Accepted answer
2 votes

Seems to be in P, as it seems to be equivalent to max-wt independent set (equivalently min-wt vertex cover) in a bipartite graph, which is in P. Specifically, construct the bipartite graph $G=(U, \...

View answer
3-SAT runtime if an optimal order to eliminate possible solutions is known
Accepted answer
2 votes

If I understand the question correctly, the answer is no. Theorem 1. There is an infinite family $\{\phi'_n\}_n$ of unsatisfiable 3CNF formulas such that, for each instance $\phi'_n$, any execution of ...

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
Hardness of computing the dimension of an integral polytope?
Accepted answer
1 votes

Yes, MORE-SAT, defined below, is one example of a combinatorial optimization problem for which the natural 0/1 integer linear program (ILP) is guaranteed to be feasible, and determining the dimension ...

View answer
Maximize the absolute value of connected nodes after $k$ modifications
Accepted answer
2 votes

We confirm @YonatanN's conjecture: Lemma 1. There is always an optimal solution $v'$ such that, for some $i'$, $|v_{i'}' - v_{i'}| = k$, while $v'_i = v_i$ for all $i\ne i'$. @YonatanN's suggested ...

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
partitioning points in the plane into two clusters to minimize maximum cluster diameter
1 votes

Theorem 1. There is an $O(n\log n)$-time algorithm for the problem in the post. Proof. We first state two utility lemmas, for an arbitrary edge-weighted graph $G$. We postpone their proofs, which are ...

View answer
Does Horn SAT (Horn formula in CNF) have an integral polytope?
Accepted answer
7 votes

EDIT: Strengthened Theorem 2. The answer to the problem as posed is no, unless P=NP: Theorem 1. Unless P=NP, there is no LP polytope for Horn-SAT that has only integer extreme points and is ...

View answer
Partition a graph into two clusters
Accepted answer
2 votes

Theorem 1. The problem admits a 2-approximation algorithm that runs in $O((m+n)\log n)$ time, given a graph $G=(V,E)$ with $m$ edges and $n$ vertices. [Caveat: The current post doesn't specify the ...

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 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
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
Accepted answer
2 votes

The answer to Question (1) is no. The answer to Question (2) is yes. Here are the details. I'll work with the following equivalent problem formulations. For the input, we are given $n$ pairs of ...

View answer
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
2 votes

The answer to the question is yes, assuming that (for all large $k$) $k$-SUM is not in $\text{DTIME}(n^{o(k)})$. It also follows (by a result of Patrascu and Williams) that the answer is yes assuming ...

View answer
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
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
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
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
Accepted answer
13 votes

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious. For the record, here's a sketch of a reduction that is parsimonious. It is obtained by composing ...

View answer
Is the knapsack variant with small profit and unlimited repetition of items NP-hard?
3 votes

The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm. Theorem 1. For unbounded Knapsack with integer profits $(p_1,\ldots,p_n)$, there is an algorithm running in time ...

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
Minimizing the gaps with incremental capacity
Accepted answer
3 votes

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

View answer
Number of connected components of a random nearest neighbor graph?
10 votes

EDIT 2: Made explicit the underlying non-asymptotic bounds in the calculation. EDIT: Replaced the calculation for two dimensions by the case of arbitrary constant dimension. Added a table of the ...

View answer
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
Accepted answer
10 votes

EDIT: Added Lemma 2 which covers all cases asked about. Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, ...

View answer
Deciding whether a 2nfa halts on every input on every branch
Accepted answer
3 votes

Lemma 1. $H_{\textsf{2nfa}}$ is decidable. Proof. Decide it as follows. Given as input a two-way non-deterministic finite automaton $M_{\textsf{2nfa}}$: Convert $M_{\textsf{2nfa}}$ into a two-way ...

View answer
Phase transition in counting feasible solutions to knapsack problems?
2 votes

I don't have a reference for you, just a minor remark that is too large for a comment. We assume $w$ is chosen as follows. Choose r.v. $x\in[0,1]^n$ uniformly at random (i.e., each $x_i$ is i.i.d. ...

View answer