Online Multi-Commodity Flow with High Demands

DOI10.1007/978-3-642-38016-7_3MaRDI QIDQ2848910zbMATH OpenOpenAlexFDO

Authors Guy Even, Moti Medina

Publication date 13 September 2013

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.5030

zbMATH Keywords

multi-commodity flowonline algorithmsprimal-dual scheme

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Abstract: 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.

Recommendations

• Multicommodity flows
• New methods for multi-commodity flows
• Multicommodity flows over time: Efficient algorithms and complexity
• scientific article; zbMATH DE number 2038726
• Multi-commodity variable upper bound flow models
• Online multidimensional load balancing
• scientific article; zbMATH DE number 2038727
• Dynamic flows with supply and demand
• Stable multicommodity flows

Cited in

(4)

• Heterogeneous flow distribution at the peak load in the multiuser network
• Competitive and deterministic embeddings of virtual networks
• Competitive Online Multicommodity Routing
• On-line path computation and function placement in SDNs

This page was built for publication: Online Multi-Commodity Flow with High Demands

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848910)