2012/01/24 by Guy Even, Even, Guy, Moti Medina +1
Computer Science · Decision Sciences · Engineering · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1201.5030
openalex publication_date 2012/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.