## Bodo Manthey — *Minimum Mean-Weight Cycles with Budgets*

Time: | Wednesday, November 3, 2010 |

Location: | Room 101, Citadel |

Given a graph *G* = (*V*,*E*) with edge lengths *d*, a minimum-mean weight cycle is a simple cycle
*C* that minimizes *d*(*C*)/|*C*|,
where |*C*| is the number of edges (or nodes) of *C*.
Minimum mean-weight cycles can be computed in time O(|*V*| × |*E*|).
In the budgeted version of this problem, we are given two lengths *d*_{1}
and *d*_{2} for each edge as well as budgets *b*_{1} and *b*_{2}.
The question is whether there exists a cycle
*C* that fulfills *d _{i}*(

*C*)/|

*C*| ≤

*b*

_{i}for

*i*= 1,2. In turns out that this problem is strongly NP-hard.

We are interested in the complexity of finding approximate solutions. Adding the two objective functions and solving the resulting problem with a single objective yields a factor 2 approximation. The question is now: Does there exists an α approximation for some α < 2?