Approximate solution of length-bounded maximum multicommodity flow with unit edge-lengths

2017/08/02 by Pavel Borisovsky, Anton V. Eremeev, Borisovsky, Pavel +7
Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Smart Parking Systems Research #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.1708.00774

openalex publication_date 2017/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An improved fully polynomial-time approximation scheme and a greedy heuristic for the fractional length-bounded maximum multicommodity flow problem with unit edge-lengths are proposed. Computational experiments are carried out on benchmark graphs and on graphs that model software defined satellite networks to compare the proposed algorithms and an exact linear programming solver. The results of experiments demonstrate a trade-off between the computing time and the precision of algorithms under consideration.

Related

• Faster Approximation Schemes for Fractional Multicommodity Flow Problems\n via Dynamic Graph Algorithms
• Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows
• A New Algorithm for Multicommodity Flow
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected\n Graphs, and its Multicommodity Generalizations