Submodular linear programs on forests

被引：15

作者：

Faigle, U

Kern, W

机构：

[1] Department of Applied Mathematics, University of Twente, 7500 AE Enschede

来源：

MATHEMATICAL PROGRAMMING | 1996年 / 72卷 / 02期

关键词：

greedy algorithm; Monge property; submodular function; ordered set; distributive lattice;

D O I：

10.1007/BF02592089

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A general linear programming model for an order-theoretic analysis of both Edmonds' greedy algorithm for matroids and the NW-corner rule for transportation problems with Monge costs is introduced. This approach includes the model of Queyranne, Spieksma and Tardella (1993) as a special case. We solve the problem by optimal greedy algorithms for rooted forests as underlying structures. Other solvable cases are also discussed.

引用

页码：195 / 206

页数：12

共 11 条

[1] A MONGE PROPERTY FOR THE D-DIMENSIONAL TRANSPORTATION PROBLEM [J].

BEIN, WW ;

BRUCKER, P ;

PARK, JK ;

PATHAK, PK .

DISCRETE APPLIED MATHEMATICS, 1995, 58 (02) :97-109

[2]

Birkhoff G., 1967, AM MATH SOC C PUBL, VXXV

[3]

BURKARD RE, IN PRESS DISCRETE AP

[4] MONGE SEQUENCES AND A SIMPLE ASSIGNMENT ALGORITHM [J].

DERIGS, U ;

GOECKE, O ;

SCHRADER, R .

DISCRETE APPLIED MATHEMATICS, 1986, 15 (2-3) :241-248

[5]

Edmonds J., 1970, COMBINATORIAL STRUCT, P69, DOI DOI 10.1007/3-540-36478

[6]

Edmonds Jack, 1977, Annals of Discrete Mathematics, V1, P185

[7]

Faigle U., 1987, ENCY MATH ITS APPL, V29, P161

[8] GENERALIZED POLYMATROIDS AND SUBMODULAR FLOWS [J].

FRANK, A ;

TARDOS, E .

MATHEMATICAL PROGRAMMING, 1988, 42 (03) :489-563

[9]

FUJISHIGE S, 1990, ANN DISCRETE MATH, V47

[10]

Hoffman A. J., 1963, CONVEXITY P 7 S PURE, V7, P317

← 1 2 →