Timeline for Ordered lattice point enumeration
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2021 at 21:25 | history | edited | Paul | CC BY-SA 4.0 |
fixed broken link
|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Jun 16, 2015 at 17:30 | vote | accept | Paul | ||
| Apr 24, 2015 at 22:57 | answer | added | Michael Albert | timeline score: 1 | |
| Apr 24, 2015 at 16:38 | history | edited | Paul | CC BY-SA 3.0 |
corrected a link per Gerry's comment
|
| Apr 24, 2015 at 3:12 | answer | added | Aaron Meyerowitz | timeline score: 0 | |
| Apr 23, 2015 at 23:23 | comment | added | Paul | @Michael I want to produce the points in order, not jump ahead. So "list the first M points" is what I'm after. Perhaps I'm just being dense, I still don't see what you mean by "usual queue based approaches." Do you have a reference that I could read? | |
| Apr 23, 2015 at 23:02 | comment | added | Michael Albert | @Paul What I was trying to say is that we can do this in effectively constant time per item (I think that's correct - may take a bit of work to avoid adding items to the queue on multiple occasions - but it's certainly right if we're treating N as a constant). So if the objective is "list the first 1000 points" that's easily done. If it is "tell me the 1000^th point" then it's less clear. | |
| Apr 23, 2015 at 21:04 | comment | added | Paul | @Michael You're correct, the NP portion of the subset sum problem is asking if there is a subset which sums to zero. I guess the point I was trying to make was that I don't think the problem "Is there a point in $\Lambda$ of given $L^{1}$-norm" is NP-complete. At any rate, it is getting a little off topic. I'm happy to clairify, but I thik I'm a little confused regarding what you're asking. Certainly the problem can be solved by returning paths in the obvious graph of increasing length. I'm likely misunderstanding your point, but I don't see how that is solvable in O(1). | |
| Apr 23, 2015 at 20:43 | comment | added | Michael Albert | We have to be a bit careful using phrases like "NP-complete" here, since, as posed, the problem isn't really in the right form. Would it also be possible to clarify - do you really want an algorithm that uses say O(N) memory beyond the initial data? [Otherwise we're just solving shortest path problems from a single source in the obvious graph, and the usual queue based approaches will be O(1) time per item output.] | |
| Apr 23, 2015 at 20:07 | comment | added | Paul | @Per I agree. I was dismayed when I saw NP-complete in the subset sum problem, but I suspect that the problem I'm considering here is not NP-complete. | |
| Apr 23, 2015 at 19:58 | comment | added | Per Alexandersson | @Paul: But you don't need negative numbers, only two subsets with same sum. This seems to be very similar to determining if two elements in $\Lambda$ has the same $L_1$-norm... | |
| Apr 23, 2015 at 19:52 | comment | added | Paul | @Per Alexandersson It does seem related, but I suspect that the problem I am considering is simpler as negative numbers are explicitly forbidden. Nonetheless, I'll be sure to look closely at subset sum to see if any of the techniques can be adapted. | |
| Apr 23, 2015 at 19:31 | comment | added | Dima Pasechnik | @SteveHuntsman - LattE will only count the points | |
| Apr 23, 2015 at 18:36 | comment | added | Per Alexandersson | It feels like this is very close to the subset-sum problem: en.wikipedia.org/wiki/Subset_sum_problem | |
| Apr 23, 2015 at 18:27 | comment | added | Steve Huntsman | math.ucdavis.edu/~latte | |
| Apr 23, 2015 at 17:39 | history | asked | Paul | CC BY-SA 3.0 |