Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.

Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.

Consider the LP:

$\max \lambda$

s.t: $p_i + \lambda \le p_j + c_{i,j}$ where $(i,j)\in \mathcal A$.

I've shown:

  • The LP is feasible.

  • If $(\lambda,p)$ is a feasible solution then the directed cycle mean cost of every directed cycle is at least $\lambda$.

  • The LP has an optimal solution (doesn't contain a line and $\lambda$ can't be greater than the maximum cost).

Now, I want to show given an optimal solution to the LP, it can be used to construct a directed cycle with minimal directed cycle mean cost.

I really don't have a clue on how to proceed. I don't see how an optimal solution give me the required information ?

  • $\begingroup$ I didn't get what are the $p_i$ $p_j$ in your equation. Can you explain me? thanks $\endgroup$ – wece Dec 4 '14 at 11:18
  • $\begingroup$ They are just variables defined in terms of the arcs. $\endgroup$ – Shuzheng Dec 4 '14 at 11:19
  • $\begingroup$ Are they fixed? $\endgroup$ – wece Dec 4 '14 at 11:21
  • $\begingroup$ One should find a vector $(\lambda, p)$ that maximizes the objective function $\lambda$. They can take on any value (they are variables) $\endgroup$ – Shuzheng Dec 4 '14 at 11:22
  • $\begingroup$ Hi, I am trying to solve the same question. Can you tell me how did you prove that this LP is feasible? I verified it by using a random directed graph, but I can't figure out a formal proof for it. Thanks. $\endgroup$ – Khushboo Apr 6 '16 at 21:47

Let $(\lambda,p)$ be an optimal solution of LP.

Let $i_0,i_1,...,i_n$ be a sequence of nodes in a cycle (i.e. $(i_k,i_k+1)\in A$ and $(i_n,i_0)\in A$).

Since $(\lambda,p)$ is a solution of LP you know that for every $k$: $$p_k+\lambda\leq p_{k+1}+c_{k,k+1}$$ and $p_n+\lambda\leq p_{0}+c_{n,0}$.

Hence by doing the sum on the cycle: $$\sum_{k=0}^n (p_k+\lambda)\leq \sum_{k=0}^{n-1}( p_{k+1}+c_{k,k+1}) + p_{0}+c_{n,0} $$ hence $$\sum_{k=0}^n p_k+(n+1)\lambda\leq \sum_{k=1}^{n} (p_{k}+c_{k-1,k}) + p_{0}+c_{n,0} $$ hence $$(n+1)\lambda\leq\sum_{k=0}^{n-1}c_{k,k+1}+c_{n,0}$$ Hence $\lambda\leq$ cycle mean cost. And this for any cycle.

Now you have to think of what happen in the case of equality, and use the fact that the solution is optimal.

I hope this helps you. If you have any further questions, please ask.


Note that the nodes not included in any cycles does not play any role in bounding $\lambda$ since you can increase the $p$ arbitrarily for those nodes.


For your second question: Consider the graph $G'$ where you removed all the nodes that don't take part in a cycle. Find an optimal solution for LP in $G'$. From this solution you can easily find a solution for LP in $G$ by setting the right $p_i$ to the node you removed (set $p_j=p_i+\lambda$ for all the new node where $(i,j)\in A$ and iterate until you find a fix point). This solution is also optimal for $G$, because if you find a better solution for $G$ then the restriction to $G$ is also a solution.

For the first question: From what's above you can (without loss of generality) consider a graph in which every nodes are part of a cycle. The intuition behind "there must be an equality for a cycle" is that if for all cylces the inequality is strict then for all nodes i,j such that $p_i+\lambda=p_j+c{i,j}$ you can increase a bit the $p_j$ and "push" the difference along all cycle until it's absorbed by the cycle. And, once you don't have any equality $p_i+\lambda=p_j+c{i,j}$ you can increase a bit the $\lambda$ hence find a better solution.

I hope it's clear. Ask if it's not ...

  • $\begingroup$ How do I know equality can happen and how do I see that $ p_j$ not in cycle doesnt depend on $\lambda $ ? $\endgroup$ – Shuzheng Dec 4 '14 at 15:57
  • $\begingroup$ And how can what you've showed be used to construct a directed cycle ? $\endgroup$ – Shuzheng Dec 4 '14 at 16:00
  • $\begingroup$ But removing all nodes that don't take part of a cycle is as hard as finding every cycle ? I don't see how your construction of the minimum mean cycle work. $\endgroup$ – Shuzheng Dec 6 '14 at 13:53
  • $\begingroup$ I don't build the cycle like that. It's just the existence. What I'm saying is that when you have an optimal solution of LP, then all the arc of the optimal cycle verify $p_i+\lambda=p_j+c_{i,j}$. From that you can build the cycle $\endgroup$ – wece Dec 8 '14 at 10:37
  • $\begingroup$ Does every arc not on such a cycle satisfy strict inequality ? $\endgroup$ – Shuzheng Dec 8 '14 at 12:27

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.