Skip to main content
Theoretical Computer Science

Return to Answer

added 564 characters in body
Source Link
David Eppstein
David Eppstein
  • 51.2k
  • 3
  • 173
  • 280

It is equivalent to ask, among a set of $d$ non-negatively weighted items, for the $d+1$ subsets of minimum total weight. One can form all the subsets of the items into a tree, in which the parent of a subset is formed by removing its heaviest item (with ties broken arbitrarily but consistently); the $d+1$ solutions will form a subtree of this tree connected at its root (the empty set).

So, one can search this tree for the smallest $d+1$ items by a form of Dijkstra's algorithm in which we maintain a priority queue of subsets and remove them in priority order. We start with the first selected item being the empty set. Then, at each step, we maintain as an invariant of the algorithm a priority queue containing the next unselected child for each already-selected subset. When we select a set $S$, we remove it from the priority queue, and we add to the priority queue two new subsets: its first child (the set formed by adding the next heavier element than the heaviest element in $S$) and its next sibling (the set formed by removing the heaviest element in $S$ and adding the same next heavier element).

After sorting the items by their weights, it is straightforward to represent each set implicitly (as its heaviest element plus a pointer to its parent set), maintain the total weight of each set, and find the first child and next sibling needed by the algorithm in constant time per set. Therefore the total time is dominated by the initial sorting and by the priority queue operations, which take total time $O(d\log d)$.

Even this can be improved, if the items are already sorted by their weights. View the "first child" and "next sibling" relation from the previous algorithm as the left and right children in a binary tree of subsets. This tree is heap-ordered (total weight increases from parent to child) so we can apply an algorithm for finding the $d+1$ minimum-weight nodes in a heap-ordered binary tree [G. N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Computation, 104:197–214, 1993]. The total time, after the sorting step, is $O(d)$.

It is equivalent to ask, among a set of $d$ non-negatively weighted items, for the $d+1$ subsets of minimum total weight. One can form all the subsets of the items into a tree, in which the parent of a subset is formed by removing its heaviest item (with ties broken arbitrarily but consistently); the $d+1$ solutions will form a subtree of this tree connected at its root (the empty set).

So, one can search this tree for the smallest $d+1$ items by a form of Dijkstra's algorithm in which we maintain a priority queue of subsets and remove them in priority order. We start with the first selected item being the empty set. Then, at each step, we maintain as an invariant of the algorithm a priority queue containing the next unselected child for each already-selected subset. When we select a set $S$, we remove it from the priority queue, and we add to the priority queue two new subsets: its first child (the set formed by adding the next heavier element than the heaviest element in $S$) and its next sibling (the set formed by removing the heaviest element in $S$ and adding the same next heavier element).

After sorting the items by their weights, it is straightforward to represent each set implicitly (as its heaviest element plus a pointer to its parent set), maintain the total weight of each set, and find the first child and next sibling needed by the algorithm in constant time per set. Therefore the total time is dominated by the initial sorting and by the priority queue operations, which take total time $O(d\log d)$.

It is equivalent to ask, among a set of $d$ non-negatively weighted items, for the $d+1$ subsets of minimum total weight. One can form all the subsets of the items into a tree, in which the parent of a subset is formed by removing its heaviest item (with ties broken arbitrarily but consistently); the $d+1$ solutions will form a subtree of this tree connected at its root (the empty set).

So, one can search this tree for the smallest $d+1$ items by a form of Dijkstra's algorithm in which we maintain a priority queue of subsets and remove them in priority order. We start with the first selected item being the empty set. Then, at each step, we maintain as an invariant of the algorithm a priority queue containing the next unselected child for each already-selected subset. When we select a set $S$, we remove it from the priority queue, and we add to the priority queue two new subsets: its first child (the set formed by adding the next heavier element than the heaviest element in $S$) and its next sibling (the set formed by removing the heaviest element in $S$ and adding the same next heavier element).

After sorting the items by their weights, it is straightforward to represent each set implicitly (as its heaviest element plus a pointer to its parent set), maintain the total weight of each set, and find the first child and next sibling needed by the algorithm in constant time per set. Therefore the total time is dominated by the initial sorting and by the priority queue operations, which take total time $O(d\log d)$.

Even this can be improved, if the items are already sorted by their weights. View the "first child" and "next sibling" relation from the previous algorithm as the left and right children in a binary tree of subsets. This tree is heap-ordered (total weight increases from parent to child) so we can apply an algorithm for finding the $d+1$ minimum-weight nodes in a heap-ordered binary tree [G. N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Computation, 104:197–214, 1993]. The total time, after the sorting step, is $O(d)$.

Source Link
David Eppstein
David Eppstein
  • 51.2k
  • 3
  • 173
  • 280

It is equivalent to ask, among a set of $d$ non-negatively weighted items, for the $d+1$ subsets of minimum total weight. One can form all the subsets of the items into a tree, in which the parent of a subset is formed by removing its heaviest item (with ties broken arbitrarily but consistently); the $d+1$ solutions will form a subtree of this tree connected at its root (the empty set).

So, one can search this tree for the smallest $d+1$ items by a form of Dijkstra's algorithm in which we maintain a priority queue of subsets and remove them in priority order. We start with the first selected item being the empty set. Then, at each step, we maintain as an invariant of the algorithm a priority queue containing the next unselected child for each already-selected subset. When we select a set $S$, we remove it from the priority queue, and we add to the priority queue two new subsets: its first child (the set formed by adding the next heavier element than the heaviest element in $S$) and its next sibling (the set formed by removing the heaviest element in $S$ and adding the same next heavier element).

After sorting the items by their weights, it is straightforward to represent each set implicitly (as its heaviest element plus a pointer to its parent set), maintain the total weight of each set, and find the first child and next sibling needed by the algorithm in constant time per set. Therefore the total time is dominated by the initial sorting and by the priority queue operations, which take total time $O(d\log d)$.