New answers tagged

0 votes

Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm

I share my "toy code" as an answer to make visually clear that at least a heuristic is available ...
user avatar
  • 11.1k
1 vote
Accepted

Longest path on directed acyclic graph when the weight is defined on the pair of edges

The quadratic shortest path problem (QSSP) can be reduced to the problem. Because QSSP is NP-hard [1], the problem in the question has no polynomial-time solution unless P = NP. To remove the ...
user avatar
  • 191
0 votes

Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm

This problem is at least as hard as the subset sum problem, therefore NP-hard. For an instance of the subset sum problem with positive integer items $a_1, \dots, a_n$ and the target $T$, let $X_i = \{ ...
user avatar
  • 191
2 votes

Fastest way to solve non-negative linear diophantine equations

Such problems are naturally expressed as finding integral points within a bounded polyhedron. There is a bunch of software available for this, e.g., Normaliz. Although my initial attempt to employ ...
user avatar
2 votes

Fastest way to solve non-negative linear diophantine equations

Consider constraint programming for this. On my laptop, the constraint programming solver in SAS finds all the solutions in one second. Code: ...
user avatar
  • 3,770

Top 50 recent answers are included