New for: D1, D2
The minimum dicycle cover problem is to find nonnegative numbers $x_e$,
such that $\sum {x_e: e \in C} \geq 1$ for every dicycle $C$ in $D$,
and such that $\sum {w(e)x_e: e \in A}$ is as small as possible.
The maximum dicycle packing problem is to find a family $H$ of dicycles
of $D$ and nonnegative numbers $y_C$, $C \in H$, such that
$\sum {y_C: e \in C} \leq w(e)$ for all $e \in A$, and such that
$\sum {y_C: C \in H}$ is as large as possible.
The latter problem is mentioned in the literature as being NP-hard.
We will show that both problems are solvable in strongly polynomial time.
In a subsequent talk, I will consider integral versions of these problems.