New answers tagged

5

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 following reduction from Subset Sum. Given a Subset-Sum input $(y, T)$, where $y=(y_1, y_2, \ldots, y_n)$ is a sequence of integers, and $T$ is the target, the ...


1

This is NP-hard, by reduction from ILP feasibility. Deciding feasibility of an ILP instance is NP-hard, so your problem is, too. You can convert each inequality $a_1 x_1 + \dots + a_n x_n \ge b$ into an equality using a slack variable $s \ge 0$: $$a_1 x_1 + \dots + a_n x_n - s = b.$$ You can arrange for all variables to be non-negative by defining $x_i = ...


1

With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}^{th}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}^{th}$ block of $3n ...


0

Two more publications 1. Goldengorin, B., Ghosh, D.: A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. J. Glob. Optim. 32, 65–82 (2005) B. Goldengorin. Maximization of submodular functions: Theory and enumeration algorithms. European Journal of Operational Research, 198(1):102–112, ...


5

The best algorithm for 3-SAT now has numerical upper bound O(1.306995^n). It is described in this paper: Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, Uri Zwick, Faster k-SAT algorithms using biased-PPSZ , 2019 Simply speaking, it adds bias to the PPSZ algorithm to let some literals have a higher, lower or equal probability to turn to some value. In the ...


2

One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed. I suspect it should be possible to build an interpreter that incurs at most a $O(1)$-factor slowdown, but I haven't checked the details (the instruction set is so primitive that the ...


Top 50 recent answers are included