Question

The tramp steamer problem. You are the owner of a steamship that can apply between a group of port cities V . You make money at each port: a visit to city i earns you a profit of ${\mathit{p}}_{\mathbf{i}}$ dollars. Meanwhile, the transportation cost from port i to port j is ${\mathit{c}}_{\mathbf{i}\mathbf{j}}\mathbf{>}\mathbf{0}$ .You want to find a cyclic route in which the ratio of profit to cost is maximized.

To this end, consider a directed graph $\mathit{G}\mathbf{=}\left(V,E\right)$ whose nodes are ports, and which has edges between each pair of ports. For any cycle C in this graph, the profit-to-cost ratio is

role="math" localid="1658920675878" $\mathit{r}\mathbf{\left(}\mathbf{c}\mathbf{\right)}=\underset{}{\frac{\sum \left(i,j\right)ic\mathit{P}\left({}_{ij}\right)}{\sum \left(i,j\right)ic{\mathit{C}}_{ij}}}$

Let r' be the maximum ratio achievable by a simple cycle. One way to determine r' is by binary search: by first guessing some ratio r , and then testing whether it is too large or too small. Consider any positive $\mathit{r}\mathbf{>}\mathbf{0}$ . Give each edge $\left(i,j\right)$ a weight of ${\mathit{w}}_{\mathbf{i}\mathbf{j}}\mathbf{=}\mathit{r}{\mathit{c}}_{\mathbf{i}\mathbf{j}}\mathbf{-}{\mathit{p}}_{\mathbf{j}}$ .

1. Show that if there is a cycle of negative weight, then .
2. Show that if all cycles in the graph have strictly positive weight, then $\mathit{r}\mathbf{<}{\mathit{r}}^{\mathbf{*}}$.
3. Give an efficient algorithm that takes as input a desired accuracy $\mathbf{\in }\mathbf{>}\mathbf{0}$ and returns a simple cycle c for which $\mathit{r}{\left(C\right)}^{\mathbf{3}}{\mathit{r}}^{\mathbf{*}}\mathbf{-}\mathbf{\in }$ Justify the correctness of your algorithm and analyze its running time in terms of $\left|V\right|\mathbf{,}\mathbf{\in }$ and $\mathbf{R}\mathbf{=}{\mathbf{max}}_{\left(i,j\right)\mathbf{iE}}\left(\frac{P_J}{C_{\mathrm{IJ}}}\right)$ .

Short answer

a) The cycle of negative weight is shown below.

b) If all cycles in the graph have strictly positive weight, then $r>r^{*}$is proved.

c) An efficient algorithm that takes as input a desired accuracy$\in >0$ is proved.

Step-by-step solution

Step-by-Step Solution .  Cmax,Cnegative,r, 

Step-1: (a) proof of negative weight in cycle

Let $G_r$ be the graph with edge weights $w_{ij}=r{c}_{ij}-p_j$ for a given r . Let's pretend there's a negative weight cycle in $G_r$. Consider a simple negative-weight cycle localid="1658921532977" $C_{negative}$ . The following $C_{negative}$ is the weight is given as: localid="1658921854625" $r\left(C\right)<\frac{\sum _{}\left(i,j\right)\in C{P}_{ij}}{\sum _{}\left(i,j\right)\in c{C}_{IJ}}$

$$\begin{gathered} weight\left(c_{negative}\right)=\sum _{\left(i,j\right)\dot{\mathrm{I}}{C}_{negative}}{W}_{ij} \\ weight\left({\mathrm{c}}_{\mathrm{negative}}\right)=\sum _{(\mathrm{i},\mathrm{j})\dot{\mathrm{I}}{\mathrm{C}}_{\mathrm{negative}}}\left(r{c}_{ij}-p_j\right)<0 \\ r<\frac{{\sum }_{\left(i,j\right)\in }{C}_{negative}{P}_{i,j}}{{\sum }_{\left(i,j\right)\in }{C}_{negtive}{C}_{ij}}=C_{negative} \end{gathered}$$

Thus,

$r<\underset{}{\frac{\sum \left(i,j\right)\in C_{negative}{P}_{ij}}{{\sum _{}}_{\left(i,j\right)\in }{C}_{negative}{C}_{ij}}=r\left(C_{Negative}\right)}$

Since the highest possible ratio for any simple cycle

$r<r\left(C_{negative}\right)\underline{<}{r}^{*}$.

Therefore,

$r<r^{*}$

 Step-2: proof of positive weight in cycle.

b).

Let's consider the basic cycle $c_{max}$ with the highest profit-to-cost ratio, which is $r\text{'}=r\left(c_{max}\right)$ .

Assume that no negative weight cycles exist in $G_r$. In the graph $G_r$, the weight of $c_{max}$ is:

$$\begin{gathered} r\left(C\right)<\frac{{\sum _{}}_{\left(i,j\right)\in C}{P}_{ij}}{{\sum _{}}_{\left(i,j\right)\in C}{C}_{ij}} \\ weight\left(c_{max}\right)=\sum _{\left(i,j\right)I{C}_{max}}{w}_{ij} \\ weight\left(c_{max}\right)\sum _{\left(i,j\right)iI{C}_{max}}\left(r{c}_{ij}=p_j\right) \end{gathered}$$

Because the weight of all cycles in the graph is strictly larger than zero,

$weight\left(c_{max}\right)=\sum _{\left(i,j\right)I{C}_{max}}\left(r{c}_{ij}-p_j\right)$

Thus,

$r<\frac{\sum _{}\left(i,j\right)\in c_{max}{P}_{ij}}{\sum _{}\left(i,j\right)\in c_{max}{C}_{IJ}}=r\left(c_{max}\right)$

Therefore,

The basic purpose of this challenge is to find a cycle with a ratio r that falls withinthe interval. It can be accomplished through the use of binary search and the conclusions in (a) and (b).

To begin with, it's simple to show upperbound and is a lowerbound for . Then choose a value that is in the middle of these two and test for the presence of negative weight cycles in $G_r$. Let be the new lowerbound if there is a negative cycle in $G_r$ (which implies that $r<r^{*}$). Otherwise, the new upperbound should be r . When the length of the interval (the distance between lowerbound and upperbound) is less than $\in$, the binary search operation ends.

Step-3: (c) Algorithm

The basic purpose of this challenge is to find a cycle with a ratio r that falls within the choose a value r that is in the middle of these two and test for the presence of negative weight cycles in$G_r$. Let r be the new lowerbound if there is a negative cycle in$G_r$. When the length of the interval (the distance between lowerbound and upperbound) is less than$\in ,$, the binary search operation ends.

.Initialize $lowest\neg 0,highest\neg max\left(i,j\right)\hat{\mathrm{I}}E\left(\frac{p_j}{c_{ij}}\right)$

.while $\left(highest-lowest\right)>\in$ , do

$r\leftarrow \frac{highest+lowest}{2}$

If G has negative cycle then

$lowest\leftarrow r$

else

$highest\leftarrow r$

end if

end while