1
$\begingroup$

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.

$\endgroup$

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.