A fast heuristic algorithm for the maximum concurrent k-splittable flow problem

被引：10

作者：

Caramia, Massimiliano ^{[1
]}

Sgalambro, Antonino ^{[2
]}

机构：

[1] Univ Roma Tor Vergata, Dipartimento Ingn Impresa, I-00133 Rome, Italy

[2] Univ Naples Federico II, Dipartimento Ingn Econ Gest, I-80125 Naples, Italy

来源：

OPTIMIZATION LETTERS | 2010年 / 4卷 / 01期

关键词：

k-Splittable flow; Heuristic; Maximum concurrent flow; Multicommodity; Throughput; APPROXIMATION;

D O I：

10.1007/s11590-009-0147-4

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.

引用

页码：37 / 55

页数：19

共 29 条

[1]

Ahuja R., 1993, NETWORK FLOWS THEORY

[2] Global routing by never approximation algorithms for multicommodiy flow [J].

Albrecht, C .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2001, 20 (05) :622-632

[3]

Andrews M., 2005, P 37 ANN ACM S THEOR

[4]

Azar Yossi., 2001, P 8 C INTEGER PROGRA, P15

[5]

BADICS T, 1991, GENRMF

[6] The k-splittable flow problem [J].

Baier, G ;

Köhler, E ;

Skutella, M .

ALGORITHMICA, 2005, 42 (3-4) :231-248

[7] Asymptotic analysis of the flow deviation method for the maximum concurrent flow problem [J].

Bienstock, D ;

Raskina, O .

MATHEMATICAL PROGRAMMING, 2002, 91 (03) :479-492

[8] On the approximation of the single source k-splittable flow problem [J].

Caramia, Massimiliano ;

Sgalambro, Antonino .

JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (02) :277-289

[9] An exact approach for the maximum concurrent k-splittable flow problem [J].

Caramia, Massimiliano ;

Sgalambro, Antonino .

OPTIMIZATION LETTERS, 2008, 2 (02) :251-265

[10]

Chuzhoy J., 2004, P 36 ANN ACM S THEOR, P28

← 1 2 3 →