Timeline for An online algorithm to find the Pareto frontier elements
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Jan 30, 2016 at 3:31 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 59 characters in body
|
| Jan 30, 2016 at 3:07 | comment | added | D.W.♦ | @RickyDemer, that aspect is probably of independent interest, so let's take that to a separate question: cs.stackexchange.com/q/52457/755. | |
| Jan 30, 2016 at 2:38 | comment | added | user12859 | I don't see how such subtrees can all be found in O(log(n)) time. | |
| Jan 29, 2016 at 1:36 | comment | added | D.W.♦ | @RickyDemer, I've updated my answer to address that point. You're right: we might potentially need to delete an entire range of consecutive points in the frontier. Fortunately, that too can be done in $O(\lg n)$ time, using properties of balanced binary trees. Do you agree? If you agree, shall we clean up our comments? | |
| Jan 29, 2016 at 1:35 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 1264 characters in body; added 264 characters in body
|
| Jan 25, 2016 at 6:59 | vote | accept | JnBrymn | ||
| Jan 25, 2016 at 5:13 | comment | added | user12859 | In two dimensions, how are now-strictly-dominated elements removed in O(log(n)) time? | |
| Jan 25, 2016 at 3:19 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 19 characters in body
|
| Jan 24, 2016 at 23:06 | comment | added | user12859 | See "remove all other elements because this dominates them in both dimensions". (There can easily be a linear number elements to be removed, so if you have to do that one element at a time, then updates can take worst-case O(n) time.) | |
| Jan 24, 2016 at 20:50 | comment | added | D.W.♦ | @JnBrymn, see my updated answer: I added a paragraph to the end to address the situation in higher dimensions. | |
| Jan 24, 2016 at 20:50 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 424 characters in body
|
| Jan 24, 2016 at 16:42 | comment | added | JnBrymn | This is a good answer. Though it brings to my attention that I implied a constraint with my example that I didn't intend to. In my example I'm using 2-tuples, but I would need an algorithm that handles N-tuples. | |
| Jan 24, 2016 at 14:36 | comment | added | user12859 | Do balanced binary trees allow O($\hspace{.02 in}$log(n))-time deletions of ranges? | |
| Jan 24, 2016 at 13:44 | history | answered | D.W.♦ | CC BY-SA 3.0 |