The Maximum Multiflow Problems with Bounded Fractionality.

We consider the weighted maximum multiflow problem with respect to a terminal weight. We show that if the dimension of the tight span associated with the weight is at most 2, then this problem has a 1/12-integral optimal multiflow for every Eulerian supply graph. This result solves a weighted generalization of Karzanovˌs conjecture for classifying commodity graphs with finite fractionality. In addition, our proof technique proves the existence of an integral or half-integrality optimal multiflow for a large class of multiflow maximization problems, and it gives a polynomial time algorithm. [ABSTRACT FROM AUTHOR]