Combining linear and non-linear objectives in spanning tree problems

被引：5
|
作者：
Dell'Amico, M
Maffioli, F
机构：
[1] Univ Modena & Reggio Emilia, DISMI, I-42100 Reggio Emilia, Italy
[2] Politecn Milan, DEI, I-20133 Milan, Italy
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2000年 / 4卷 / 02期
关键词：
computational complexity; spanning tree; cumulative function;
D O I：
10.1023/A:1009854922371
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
A classical approach to multicriteria problems asks for the optimization of a suitable linear combination of the objectives. In this work we address such problems when one of the objectives is the linear function, the other is a non-linear one and we seek for a spanning tree of a given graph which optimizes the combination of the two functions. We consider both maximization and minimization problems and present the complexity status of 56 such problems, giving, whenever possible, polynomial solution algorithms.
引用
收藏
页码：253 / 269
页数：17
相关论文
共 50 条
  • [31] SOME NON-LINEAR EIGENVALUE PROBLEMS
    BERESTYCKI, H
    COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE L ACADEMIE DES SCIENCES SERIE A, 1976, 283 (04): : 171 - 173
  • [32] A CLASS OF NON-LINEAR DEVELOPMENT PROBLEMS
    BARDOS, C
    BREZIS, H
    COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE L ACADEMIE DES SCIENCES SERIE A, 1968, 266 (02): : 56 - &
  • [33] Optimization for non-linear inverse problems
    Boyadzhiev, Georgi
    Brandmayr, Enrico
    Pinat, Tommaso
    Panza, Giuliano F.
    RENDICONTI LINCEI-SCIENZE FISICHE E NATURALI, 2008, 19 (01) : 17 - 43
  • [34] Optimization for non-linear inverse problems
    Georgi Boyadzhiev
    Enrico Brandmayr
    Tommaso Pinat
    Giuliano F. Panza
    RENDICONTI LINCEI, 2008, 19 (2): : 209 - 211
  • [35] STRONGLY NON-LINEAR UNILATERAL PROBLEMS
    BOCCARDO, L
    GIACHETTI, D
    APPLIED MATHEMATICS AND OPTIMIZATION, 1983, 9 (03): : 291 - 301
  • [36] HOMOGENEIZATION, CORRECTORS AND NON-LINEAR PROBLEMS
    BENSOUSSAN, A
    LIONS, JL
    PAPANICOLAOU, G
    COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE L ACADEMIE DES SCIENCES SERIE A, 1976, 282 (22): : 1277 - 1282
  • [37] Optimization for non-linear inverse problems
    Georgi Boyadzhiev
    Enrico Brandmayr
    Tommaso Pinat
    Giuliano F.Panza
    RENDICONTI LINCEI, 2008, 19 : 17 - 43
  • [38] NON-LINEAR INITIAL VALUE PROBLEMS
    BROWDER, FE
    ANNALS OF MATHEMATICS, 1965, 82 (01) : 51 - &
  • [39] SOME NON-LINEAR PROBLEMS IN ASTROPHYSICS
    LERCHE, I
    LOW, BC
    PHYSICA D-NONLINEAR PHENOMENA, 1982, 4 (03) : 293 - 318
  • [40] GENERALIZATION OF THE CG METHOD APPLIED TO LINEAR AND NON-LINEAR PROBLEMS
    DVORNIK, J
    COMPUTERS & STRUCTURES, 1979, 10 (1-2) : 217 - 223
12345