Timeline for Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2022 at 14:10 | comment | added | Manfred Weis | what kind of brute force algorithm should that be, specifically in which order are the combinations generated? I guess it will be according to lexical order; but how can we then be sure that a specific combination, that also satisfies any further constraints, is indeed the optimal combination that satisfies all constraints? Regarding the size of the priority queue: do you have any reference for a proof of the claimed size limits? | |
| Jun 18, 2022 at 7:24 | comment | added | pcpthm | @ManfredWeis I think "minimal memory" solution is unwanted without further restriction because the brute-force algorithm only needs $O(n)$ space to generate one next combination. I assume the time required per one combination should be small. Then, the priority-queue based approach uses $O(n)$ space with $O(\log n)$ time per combination for $k = 2$. | |
| Jun 18, 2022 at 6:13 | comment | added | Manfred Weis | please note that I asked for minimal memory footprint; if I would like to check for the existence of a subset with given sum and exactly $k$ or $n-k$ summands, then that problem is in $P$ if $k$ is fixed (fixed parameter complexity) For $k=2$ I have an algorithm that enumerates all pairs of values using $O(n)$ space instead of $O(n^2)$ and for higher $k$ the space-savings are also very promising. | |
| Jun 17, 2022 at 5:49 | history | answered | pcpthm | CC BY-SA 4.0 |