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 条
  • [1] Combining Linear and Non-Linear Objectives in Spanning Tree Problems
    Mauro Dell'Amico
    Francesco Maffioli
    Journal of Combinatorial Optimization, 2000, 4 : 253 - 269
  • [2] LINEAR AND NON-LINEAR PROBLEMS OF PLATE DYNAMICS
    Baradokas, P.
    Michnevic, E.
    Syrus, L.
    AVIATION, 2007, 11 (04) : 9 - 13
  • [3] Linear and non-linear problems of plate dynamics
    Department of Theoretical Mechanics, Vilnius Gediminas Technical University, Sauletekio al. 11, LT-10223 Vilnius, Lithuania
    Aviation, 2007, 4 (9-13+40)
  • [4] SOME PROBLEMS IN LINEAR AND NON-LINEAR PROGRAMMING
    HARTLEY, HO
    BIOMETRICS, 1959, 15 (02) : 336 - 337
  • [5] ON SOME NON-LINEAR PROBLEMS
    SRINIVAS.K
    CANADIAN JOURNAL OF MATHEMATICS, 1968, 20 (02): : 394 - &
  • [6] NON-LINEAR DISTRIBUTION PROBLEMS
    BUZBY, BR
    OPERATIONS RESEARCH, 1965, S 13 : B144 - &
  • [7] Problems of Non-linear Symmetry
    Kuzmin, V. I.
    Dzerzhinsky, R. I.
    DATA SCIENCE AND ALGORITHMS IN SYSTEMS, 2022, VOL 2, 2023, 597 : 293 - 311
  • [8] DECOMPOSITION OF NON-LINEAR PROBLEMS
    POSNER, ME
    MATHEMATICAL PROGRAMMING, 1978, 15 (03) : 360 - 362
  • [9] Tree automata for non-linear arithmetic
    Kobayashi, Naoki
    Ohsaki, Hitoshi
    REWRITING TECHNIQUES AND APPLICATIONS, PROCEEDINGS, 2008, 5117 : 291 - +
  • [10] COMPARISON OF SOLUTIONS OF NON-LINEAR EVOLUTION PROBLEMS WITH DIFFERENT NON-LINEAR TERMS
    BENILAN, P
    DIAZ, JI
    ISRAEL JOURNAL OF MATHEMATICS, 1982, 42 (03) : 241 - 257
12345