An efficient algorithm for approximate solution of the vector cost assignment problem

被引：0

作者：

Sakakibara, S ^{[1
]}

Nakamori, M ^{[1
]}

机构：

[1] Tokyo Univ Agr & Technol, Dept Comp Informat & Commun Sci, Koganei, Tokyo 1848588, Japan

来源：

PDPTA '05: Proceedings of the 2005 International Conference on Parallel and Distributed Processing Techniques and Applications, Vols 1-3 | 2005年

关键词：

assignment problem; vector cost assignment problem; parametric assignment problem; approximate solution; integer programming;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An extended model of the assignment problem is considered whose cost is a two dimensional vector. This problem belongs to the class NP-hard, and it is difficult to obtain the optimal solution. In the present paper an algorithm based on parametric analysis is presented for quasi optimal solution. Results of numerical experiments are shown, and it is concluded that the algorithm. gives a satisfactory solution, even when the correlation coefficient is near to 1.

引用

页码：433 / 439

页数：7

共 7 条

[1] FINDING MINIMUM-COST FLOWS BY DOUBLE SCALING [J].

AHUJA, RK ;

GOLDBERG, AV ;

ORLIN, JB ;

TARJAN, RE .

MATHEMATICAL PROGRAMMING, 1992, 53 (03) :243-266

[2]

Dantzig G., 1963, LINEAR PROGRAMMING

[3]

Ford L. R., 1962, FLOWS NETWORKS

[4]

KAMURA Y, 2002, P PDPTA 2002, V1, P228

[5] Regulation of endothelial cell death and its role in angiogenesis and vascular regression [J].

Sakamaki, K .

CURRENT NEUROVASCULAR RESEARCH, 2004, 1 (04) :305-315

[6]

TOKUYAMA T, 1991, P 7 ANN S COMP GEOM, P262

[7]

Tomizawa N., 1971, Networks, V1, P173, DOI 10.1002/net.3230010206

← 1 →