Suitable Data Structure?

Perhaps this is slightly off-topic: if it is, could someone suggest a better
group?

I have the following problem, and would certainly appreciate some help. I
need to find a suitable data structure for a vector v of dimension n to
implement the following algorithm effectively:

v=0
for i=1..n
for j=1..m
Update j components of v: v_(j(i)) = v_(j(i))+d_(j(i)) (1)
end for j
determine I such that v_I = max(v_i: i=1,..n). (2)
v_I =0
end for i

The difficulty is the following: The precise components j(i) of v that will
be updated in (1) and the values of d_(j(i)) are unknown in advance. (They
are calculated in the i-loop elsewhere.) In any case, n is quite large
(often n>10^5), whereas m is usually quite small (m<100).

Simply selecting the largest element in (2) requires O(n) operations, for a
total of O(n^2) operations in the entire algorithm, which is too high for
my application. Keeping v sorted and updating the order of v after every
update seems to be too expensive if a linear data structure is used. The
actual amount of work needed would also be too unpredictable. Ideally, a
binary tree could be used to keep the elements in order, but to my
knowledge, once an element is inserted in the tree, it cannot be updated,
so this is not suitable either. Essentially, I need an algorithm that
requires significantly less than O(n^2) operations. Ideal would be, of
course, O(n*log n), which could be obtained if a binary tree could be used.
Any ideas?

For the sake of completeness, I should add that all d_(j(i)) are positive,
so that all components of v are also positive. Furthermore, once v_I has
been selected and set to zero, it will definitely not be updated and can be
discarded.

Thanks in advance

Jan



.

Relevant Pages

  • Re: Suitable Data Structure?
    ... >implement the following algorithm effectively: ... The precise components jof v that will ... >Simply selecting the largest element in requires Ooperations, ... >course, O, which could be obtained if a binary tree could be used. ...
    (sci.math.num-analysis)
  • Re: $1000 to the first person who can solve this problem
    ... appear before it can make a "decision" about the trend. ... you're after is an algorithm that can make a decision on EVERY number? ... is VERY close to what we need was the Secretary Problem. ...
    (sci.stat.math)
  • Monotone Decomposition
    ... It's the first step in the classic Otriangulation algorithm. ... During the plane-sweep some of the active edges are stored in a binary tree or similar Osearch-structure. ... I have no idea how the search for the rightmost edge should work. ... The only reliable way to get the rightmost intersection-point seems to calculate the intersections and compare them. ...
    (comp.graphics.algorithms)
  • Re: Binqry Tree sort
    ... Actually I'm looking for a parallel proessing, ... The connection between processors are like the binary tree. ... The parent processor compares the ... Now I'm looking for a parallel algorithm wich uses parallel binary tree ...
    (comp.programming)
  • Re: Binqry Tree sort
    ... second about the algorithm which I asked. ... Actually I'm looking for a parallel proessing, not a sequential proessing with just one processor. ... In other words I want to use the binary tree as my parallel architecture. ... "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. ...
    (comp.programming)
Loading