CRASHING A MAXIMUM-WEIGHT COMPLEMENTARY BASIS

被引：4

作者：

ANSTREICHER, KM ^{[1
]}

LEE, J ^{[1
]}

RUTHERFORD, TF ^{[1
]}

机构：

[1] UNIV WESTERN ONTARIO,DEPT ECON,LONDON N6A 5C2,ONTARIO,CANADA

来源：

MATHEMATICAL PROGRAMMING | 1992年 / 54卷 / 03期

关键词：

LINEAR COMPLEMENTARITY PROBLEM; LEMKE ALGORITHM; MATROID INTERSECTION;

D O I：

10.1007/BF01586055

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We consider the problem of finding a maximum-weight complementary basis of an m x 2m matrix. The problem arises naturally, for example, when a complementary set of columns is proposed as an initial basis for a "warm start" of Lemke's algorithm, but the set of columns is rank-deficient. We show that the problem is a special case of the problem of finding a maximum-weight common base of two matroids. Furthermore, we show how to efficiently implement an algorithm for the general problem in the present context. Finally, we give computational results demonstrating the practicality of our algorithm in a typical application.

引用

页码：281 / 294

页数：14