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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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