Online Multi-Commodity Flow with High Demands

Details Online Multi-Commodity Flow with High Demands Online Multi-Commodity Flow with High Demands

2012-01-24

arxiv.org/abs/1201.5030v4

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Online Multi-Commodity Flow with High Demands does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Online Multi-Commodity Flow with High Demands, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Multi-Commodity Flow with High Demands will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107347