New answers tagged ds.algorithms
0
votes
How to show that the median cannot be maintained in $O(1)$ time?
The question's title presupposes the wrong answer. Median can in fact be maintained in $O(1)$ time. Here is the counter example disproving the title's fallacious claim of “How to show that the ...
- 101
11
votes
Accepted
How to show that the median cannot be maintained in $O(1)$ time?
If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$:
first you compute a value $a$ smaller than all elements in the sequence and a value $...
- 685
2
votes
Accepted
Maximize a special monotone submodular function - is it easier?
I believe that the problem is NP-Hard and it admits a FPTAS. Let me sketch my thoughts.
NP-Hardness: Consider a slight variant of the well-known 2-Partition problem. Given $2n$ non-negative integers $...
- 6,650
Top 50 recent answers are included