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 ...
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 $...
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 $...
Top 50 recent answers are included
Related Tags
ds.algorithms × 1751graph-algorithms × 322
graph-theory × 273
cc.complexity-theory × 240
reference-request × 232
approximation-algorithms × 155
optimization × 108
co.combinatorics × 107
ds.data-structures × 100
time-complexity × 89
np-hardness × 60
linear-algebra × 59
linear-programming × 59
cg.comp-geom × 57
sorting × 52
randomized-algorithms × 49
sat × 43
matrices × 42
lower-bounds × 31
heuristics × 30
nt.number-theory × 29
counting-complexity × 28
directed-acyclic-graph × 28
machine-learning × 27
complexity-classes × 26