My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \wedge\ \forall C \in \mathrm{cycles}(G)\ \forall e \in C:\ x_e \leq \!\!\!\!\sum_{e' \in C \setminus \{e\}} \!\! x_{e'}  \right\}$$  

This problem, studied by [Chopra and Rao (1993)][1], is sometimes called Minimum Cost Multicut, although the term is used also for different problems in the literature (e.g. [this][2] problem with terminals and positive edge weights).

Is the problem stated above known to be APX-hard? 


  [1]: http://link.springer.com/article/10.1007%2FBF01581239
  [2]: http://www.nada.kth.se/~viggo/wwwcompendium/node93.html