DMMP Seminar

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 d1 and d2 for each edge as well as budgets b1 and b2. The question is whether there exists a cycle C that fulfills di(C)/|C| ≤ bi 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?