# Finding optimal element with two criteria

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.

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.