New answers tagged ds.algorithms
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
