  This paper deals with the problem of computing, in an online fashion, a
maximum benefit multi-commodity flow (\ONMCF), where the flow demands may be
bigger than the edge capacities of the network.
  We present an online, deterministic, centralized, all-or-nothing, bi-criteria
algorithm. The competitive ratio of the algorithm is constant, and the
algorithm augments the capacities by at most a logarithmic factor.
  The algorithm can handle two types of flow requests: (i) low demand requests
that must be routed along a path, and (ii) high demand requests that may be
routed using a multi-path flow.
  Two extensions are discussed: requests with known durations and machine
scheduling.
