Dearl all,
I recently stumbled across an interesting combinatorial problem and was wondering if someone here has faced something similar and would help me get a head start.
Problem Defintion
Let G be a directed graph G and let C denote the set of all simple cycles in G (i.e. cycles that include each vertex at max once). Let's say that we have some utility function F on C which we want to maximize. The task is to find cycle
c' = argmax_c_in_C {F(c)}
I was wondering if there are some known algorithms to do it faster than just listing all simple cycles and ordering them by their utility. Do you know of some relevant literature on this topic? Does this problem have a name?
Motivation
Currency Exchange Arbitrage. Imagine vertices are currencies (USD, EUR, JPY…) and edges are exchange rates between them. The utility of a function F for cycle c = V1 -> V2-> … -> Vn -> V1 is given by F(c) which is computed by taking 1units of V1 and exchanging it for V2, then the resulting V2 amount for V3 and so forth until I come back to V1 with some amount x, then F(c) = x - 1.
I had a discussion with my friend about this a while back and I was convinced that there must be a tone of literature because it seemed like such an obvious way to approach this potentially very profitable problem. However, I am having a hard time finding anything relevant.
Can someone point me in the right direction, please?