Fdtxjr

Should I use a zero-interest credit card for a large one-time purchase?

Is the Standard Deduction better than Itemized when both are the same amount?

Why is my conclusion inconsistent with the van't Hoff equation?

51k Euros annually for a family of 4 in Berlin: Is it enough?

Generate an RGB colour grid

How to tell that you are a giant?

Single word antonym of "flightless"

What does an IRS interview request entail when called in to verify expenses for a sole proprietor small business?

Short Story with Cinderella as a Voo-doo Witch

Why are there no cargo aircraft with "flying wing" design?

How can I make names more distinctive without making them longer?

How widely used is the term Treppenwitz? Is it something that most Germans know?

What exactly is a "Meth" in Altered Carbon?

Apollo command module space walk?

Seeking colloquialism for “just because”

2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?

Is it true that "carbohydrates are of no use for the basal metabolic need"?

What is the meaning of the new sigil in Game of Thrones Season 8 intro?

Abandoning the Ordinary World

How to react to hostile behavior from a senior developer?

Identify plant with long narrow paired leaves and reddish stems

English words in a non-english sci-fi novel

List *all* the tuples!

What does this icon in iOS Stardew Valley mean?

Graph search algorithm for finding cycle with largest end result

0

$begingroup$

I have a directed graph where the vertices represent Forex currencies, and the edges represent the ratio of the projecting currency to the projected currency. For example:

$$E(USD, EUR) = 0.91$$
$$E(EUR, USD) = 1.13$$
$$E(EUR,YEN) = 126.69$$
$$E(YEN,USD) = 0.0091$$

If I wanted the value of $1.50 USD in EUR, I would calculate $1.50*0.91$, and if I wanted the value of €1.50 EUR in USD, I would calculate $1.50*1.13$.

Since most pairs of vertices will have two edges between them, with one going each way, the graph has cycles. What I want to be able to do is find all cycles in the graph that result in a value larger than the initial state. This process is known as arbitrage.

So, say I have $1 USD. I want to evaluate all possible paths in the graph that would start at $V(USD)$, end at $V(USD)$, and have the end value greater than or equal to the start value. For example:

$$$1 rightarrow €0.91 rightarrow ¥115.2879 rightarrow $1.049$$

This example starts and ends at the same vertex and has an end value of $1.049, which is greater than the starting value of $1. Thus, it is a valid path.

Is there an algorithm that achieves this type of search behavior? I am familiar with basic path search algorithms, but none of the ones I currently have knowledge of allow searching specifically for cycles, and they all prioritize reducing cost rather than increasing it (although I'm sure this can be solved with a few operator swaps).

discrete-mathematics graph-theory directed-graphs

share|cite|improve this question

asked Mar 26 at 17:06

HausHaus

1114

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  According to this answer the problem is NP-hard. You can easily reduce your problem to the sum-of-weights problem by taking logarithms.
  $endgroup$
  – saulspatz
  Mar 26 at 17:13
  

  
  
  
  

add a comment | 

0

$begingroup$

I have a directed graph where the vertices represent Forex currencies, and the edges represent the ratio of the projecting currency to the projected currency. For example:

$$E(USD, EUR) = 0.91$$
$$E(EUR, USD) = 1.13$$
$$E(EUR,YEN) = 126.69$$
$$E(YEN,USD) = 0.0091$$

If I wanted the value of $1.50 USD in EUR, I would calculate $1.50*0.91$, and if I wanted the value of €1.50 EUR in USD, I would calculate $1.50*1.13$.

Since most pairs of vertices will have two edges between them, with one going each way, the graph has cycles. What I want to be able to do is find all cycles in the graph that result in a value larger than the initial state. This process is known as arbitrage.

So, say I have $1 USD. I want to evaluate all possible paths in the graph that would start at $V(USD)$, end at $V(USD)$, and have the end value greater than or equal to the start value. For example:

$$$1 rightarrow €0.91 rightarrow ¥115.2879 rightarrow $1.049$$

This example starts and ends at the same vertex and has an end value of $1.049, which is greater than the starting value of $1. Thus, it is a valid path.

Is there an algorithm that achieves this type of search behavior? I am familiar with basic path search algorithms, but none of the ones I currently have knowledge of allow searching specifically for cycles, and they all prioritize reducing cost rather than increasing it (although I'm sure this can be solved with a few operator swaps).

discrete-mathematics graph-theory directed-graphs

share|cite|improve this question

asked Mar 26 at 17:06

HausHaus

1114

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  According to this answer the problem is NP-hard. You can easily reduce your problem to the sum-of-weights problem by taking logarithms.
  $endgroup$
  – saulspatz
  Mar 26 at 17:13
  

  
  
  
  

add a comment | 

$begingroup$

I have a directed graph where the vertices represent Forex currencies, and the edges represent the ratio of the projecting currency to the projected currency. For example:

$$E(USD, EUR) = 0.91$$
$$E(EUR, USD) = 1.13$$
$$E(EUR,YEN) = 126.69$$
$$E(YEN,USD) = 0.0091$$

If I wanted the value of $1.50 USD in EUR, I would calculate $1.50*0.91$, and if I wanted the value of €1.50 EUR in USD, I would calculate $1.50*1.13$.

Since most pairs of vertices will have two edges between them, with one going each way, the graph has cycles. What I want to be able to do is find all cycles in the graph that result in a value larger than the initial state. This process is known as arbitrage.

So, say I have $1 USD. I want to evaluate all possible paths in the graph that would start at $V(USD)$, end at $V(USD)$, and have the end value greater than or equal to the start value. For example:

$$$1 rightarrow €0.91 rightarrow ¥115.2879 rightarrow $1.049$$

This example starts and ends at the same vertex and has an end value of $1.049, which is greater than the starting value of $1. Thus, it is a valid path.

Is there an algorithm that achieves this type of search behavior? I am familiar with basic path search algorithms, but none of the ones I currently have knowledge of allow searching specifically for cycles, and they all prioritize reducing cost rather than increasing it (although I'm sure this can be solved with a few operator swaps).

discrete-mathematics graph-theory directed-graphs

share|cite|improve this question

asked Mar 26 at 17:06

HausHaus

1114

$endgroup$

share|cite|improve this question

asked Mar 26 at 17:06

HausHaus

1114

share|cite|improve this question

asked Mar 26 at 17:06

HausHaus

1114

asked Mar 26 at 17:06

HausHaus

1114

asked Mar 26 at 17:06

HausHaus

1114