Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Math/Algorithms geniuses need your HELP!!!?

The problem of searching for cycles in graphs arises naturally in financial trading applications. Consider a firm that trades shares in n different companies. For each pair i != j, they maintain a trade ratio Rij, meaning that one share of i trades fo Rij shares of j. Here we allow the rate R to be fractional: that is, Rij = 2/3 means that you can trade three shares of i to get two shares of j.

A trading cycle for a sequence of shares i1, i2, ..., ik consists of successively trading shares in company i1 for shares in company i2, then shares in company i2 for shares i3, and so on, finally trading shares in ik back to shares in company i1. After such a sequence of trades, one ends up with shares in the same company i1 that one starts with. Trading around a cycle is usually a bad idea, as you tend to end up with fewer shares than you started with. But occasionally, for short periods of time, there are opportunities to increase shares. We will call such a cycle an opportunity cycle, if trading along the cycle increases the number of shares. This happens exactly if the product of the ratios along the cycle is above 1. In analyzing the state of the market, a firm engaged in trading would like to know if there are any opportunity cycles.

Give a polynomial-time algorithm that finds such an opportunity cycle, if one exists.

HINT: Bellman-Ford Algorithm

I am completely lost on this problem. If someone would be kind enough to not only solve this but tell me how you solved it. Thanks

1 Answer

Relevance
  • 1 decade ago
    Favorite Answer

    Actually, Djikstra's algorithm is faster. There are no negative weights on these edges (you cannot trade negative numbers of shares).

    http://en.wikipedia.org/wiki/Dijkstra%27s_algorith...

    That's a fairly good description of the algorithm. Just use such an algorithm to find the shortest path from the starting vertex to itself (creating a cycle). It is polynomial time. The algorithm is explained as:

    1. Create a distance list, a previous vertex list, a visited list, and a current vertex.

    2. All the values in the distance list are set to infinity except the starting vertex which is set to zero.

    3. All values in visited list are set to false.

    4. All values in the previous vertex list are set to a special value signifying that they are undefined, such as null.

    5. Current vertex is set as the starting vertex.

    6. Mark the current vertex as visited.

    7. Update distance and previous lists based on those vertices which can be immediately reached from the current vertex.

    8. Update the current vertex to the unvisited vertex that can be reached by the shortest path from the starting vertex.

    9. Repeat (from step 6) until you reach the starting node, creating the least-cost cycle from that nodes.

    If the combined weight of that cycle gives you "opportunity" then it is an opportunity cycle. If it does not, then there is none. You can apply this to every vertex, one by one, to check them all.

Still have questions? Get your answers by asking now.