PARALLEL SYNCHRONOUS AND ASYNCHRONOUS IMPLEMENTATIONS OF THE AUCTION ALGORITHM

被引：86

作者：

BERTSEKAS, DP ^{[1
]}

CASTANON, DA ^{[1
]}

机构：

[1] BOSTON UNIV,DEPT ELECT COMP & SYST ENGN,BOSTON,MA 02215

来源：

PARALLEL COMPUTING | 1991年 / 17卷 / 6-7期

关键词：

ASSIGNMENT PROBLEM; AUCTION ALGORITHM; SYNCHRONOUS AND ASYNCHRONOUS IMPLEMENTATION; COMPUTATIONAL RESULTS; SHARED MEMORY MACHINES;

D O I：

10.1016/S0167-8191(05)80062-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we discuss the parallel implementation of the auction algorithm for the classical assignment problem. We show that the algorithm admits a totally asynchronous implementation and we consider several implementations on a shared memory machine, with varying degrees of synchronization. We also discuss and explore computationally the tradeoffs involved in using asynchronism to reduce the synchronization penalty.

引用

页码：707 / 732

页数：26

共 45 条

[1]

[Anonymous], 2003, LINEAR PROGRAMMING

[2]

BALAS E, 1989, MSRR552 CARN MELL U

[3] SIGNATURE METHODS FOR THE ASSIGNMENT PROBLEM [J].

BALINSKI, ML .

OPERATIONS RESEARCH, 1985, 33 (03) :527-536

[4] A COMPETITIVE (DUAL) SIMPLEX-METHOD FOR THE ASSIGNMENT PROBLEM [J].

BALINSKI, ML .

MATHEMATICAL PROGRAMMING, 1986, 34 (02) :125-141

[5] ALTERNATING BASIS ALGORITHM FOR ASSIGNMENT PROBLEMS [J].

BARR, RS ;

GLOVER, F ;

KLINGMAN, D .

MATHEMATICAL PROGRAMMING, 1977, 13 (01) :1-13

[6]

BERTSEKAS D, 1989, LIDSP1925 MIT LAB IN

[7]

BERTSEKAS D, 1985, 24 IEEE C DEC CONTR, P1703

[8]

Bertsekas D. P., 1988, Annals of Operations Research, V14, P105, DOI 10.1007/BF02186476

[9]

Bertsekas D. P., 1989, Annals of Operations Research, V20, P67, DOI 10.1007/BF02216923

[10]

Bertsekas D.P., 1991, LINEAR NETWORK OPTIM

← 1 2 3 4 5 →