3
$\begingroup$

I'm trying to solve this from The Algorithm Design Manual:

6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with 0.75×2×0.7=1.05 U.S. dollars---a profit of 5%. Suppose that there are n currencies c1,...,cn and an n×n table R of exchange rates, such that one unit of currency ci buys R[i,j] units of currency cj. Devise and analyze an algorithm to determine the maximum value of R[c1,ci1]⋅R[ci1,ci2]⋯R[cik−1,cik]⋅R[cik,c1] Hint: think all-pairs shortest path.

My understanding is this is asking to find the longest simple cycle (LSC) on a directed weighted (complete?) graph. There is a reduction from longest simple path to LSC, so this would be NP-hard. It seems strange that the problem gives a hint, so maybe it's asking something else?.

$\endgroup$
2
$\begingroup$

The question is at least poorly worded, since it does not specify $k \leq n$ or require a simple cycle. So any positive-value arbitrage cycle can be "pumped" to generate a cycle with unbounded positive value.

If we add the requirement that the cycle is simple, then finding the simple cycle with the maximum product of the weights is equivalent to finding the simple cycle with the maximum sum of the logarithms of the weights, which is indeed the NP-hard Longest Simple Cycle problem.

Usually, these arbitrage questions ask to find a cycle with positive return, if one exists. This can be done by negating the logarithms of the weights and checking for negative cycles. This question asks for the best cycle, though.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.