Let there be a (unsymmetric, directed, weighted) graph ( $\mathbb{G}$, capacity $m$ ) and an array ( $\mathbb{A}$, fixed capacity $n$) of objects ($m>>n$). The array contains references to a number of vertices. The problem is to pick a single vertex ($\mathbb{V}$) from the graph, that is not in the array, fulfilling the following condition: $\mathbb{V}$ has the minimal $\psi$ of all the vertices in $\mathbb{G}$ and $\psi$ is defined as $\psi(\mathbb{V})=S(\mathbb{V})\cdot\tau(\mathbb{V})$. (for tie-breaker conditions see below)

  1. $S(\mathbb{V})$ is the sum of the weights of the edges of $\mathbb{V}$ to all the vertices that are in $\mathbb{A}$.

    Example: if $\{ g_1,g_2,g_3,g_4\}\in\mathbb{G}$ and $\{ g_2,g_3\}\in\mathbb{A}$, given that $W(g_1, g_2)=5$, $W(g_1, g_3)=3$, $W(g_1, g_4)=1$, $W(g_2, g_1)=2$, $W(g_2, g_3)=1$, $W(g_2, g_4)=8$, $W(g_4, g_1)=9$, $W(g_4, g_2)=2$, $W(g_4, g_3)=1$, then $S(g_1) = W(g_1, g_2) + W(g_1, g_3) = 8$ and $S(g_4) = W(g_4, g_2) + W(g_4, g_3) = 3$.

  2. Each vertex in $\mathbb{G}$ has a time-decay property (100-1), $\tau(\mathbb{V})$, that is updated at discrete moments. The value is reset to the maximum once it is removed from $\mathbb{A}$ and is periodically lowered until it reaches the minimal value (at which point it stops decreasing) or is again picked and placed in $\mathbb{A}$.

  3. tie-break: if $\psi(\mathbb{V}_1)=\psi(\mathbb{V}_2)$, advantage is given in the following order: lower $S(\mathbb{V})$, lower $\tau(\mathbb{V})$, any of the two (e.g. the first that was picked).

My approach was the following algorithm:

  1. get the current number of elements in $\mathbb{A}$, $a$
  2. create a new array $\mathbb{A}_2$ of size $a(m-a)$
  3. populate $\mathbb{A}_2$ with the weight of each edge ($W(g_x, g_y)$ where $g_x \in \mathbb{G}$ and $g_y \in \mathbb{A}$)
  4. apply the time-decay to each element of $\mathbb{A}_2$ (i.e. multiply the weight with the time-decay)
  5. return the vertex with the minimal value in $\mathbb{A}_2$

This is a very expensive approach, both in terms of time and space complexity.

Are there any provably better algorithms for this problem?

Is there a specification for my kind of problem, based on which I could do further research? My current searches regarding sorting/searching, graphs and optimization problems have not yielded any tangible results.

Additional information

The size of $\mathbb{A}$ is fixed. Vertices can be added/removed from $\mathbb{G}$.The program logic takes elements from $\mathbb{G}$ and places them in $\mathbb{A}$, where they are part of some processing that is not related with this algorithm. It is important to note that vertices are repeatedly subjected to this processing and that, as a side effect of this processing, the weights of the vertices in $\mathbb{A}$ are updated.

Once that processing is completed, a vertex is removed from $\mathbb{A}$ (note that that doesn't necessarily imply that the vertex is removed from $\mathbb{G}$ as well, in fact, adding/removal of vertices is very rare). The now vacant slot needs to be filled, which is were the algorithm applies. $S(\mathbb{V})$ ensures that the choice is optimal in regards of internal metrics (i.e. the weights of the edges), while $\tau(\mathbb{V})$ is supposed to prevent starving. All vertices in $\mathbb{G}$ need to participate in the processing, otherwise only the "best" elements would iterate through $\mathbb{A}$, while those with bad metrics would never get processed.

Therefore, there is a mechanism in place which at discreet moments goes through every vertex in $\mathbb{G}$ and updates their respective idle time property (i.e. applies time-decay). This value is reset once the appropriate vertex is removed from $\mathbb{A}$.

Finally, the algorithm takes as input $\mathbb{G}$ and $\mathbb{A}$. Its task is to fill the vacant slot in $\mathbb{A}$. This is done by finding the minimal $\psi$ (take tie-breaks into account). The output of the algorithm is this particular vertex.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.