Non-additive shortest paths

被引：0
|
作者：
Tsaggouris, G
Zaroliagis, C
机构：
[1] Comp Technol Inst, Patras 26110, Greece
[2] Univ Patras, Dept Comp Engn & Informat, Patras 26500, Greece
来源：
ALGORITHMS ESA 2004, PROCEEDINGS | 2004年 / 3221卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The non-additive shortest path (NASP) problem asks for finding an optimal path that minimizes a certain multi-attribute nonlinear cost function. In this paper, we consider the case of a non-linear convex and non-decreasing function on two attributes. We present an efficient polynomial algorithm for solving a Lagrangian relaxation of NASP. We also present an exact algorithm that is based on new heuristics we introduce here, and conduct a comparative experimental study with synthetic and real-world data that demonstrates the quality of our approach.
引用
收藏
页码：822 / 834
页数：13
相关论文
共 50 条
  • [21] Non-Additive Degrees of Belief
    Haenni, Rolf
    DEGREES OF BELIEF, 2009, 342 : 121 - 159
  • [22] NON-ADDITIVE AND ADDITIVE GENETIC VARIANCE IN SWINE
    SEIBERT, DW
    MILLER, HH
    GOODMAN, BL
    JOURNAL OF ANIMAL SCIENCE, 1968, 27 (04) : 1129 - &
  • [23] Optimizing Additive Approximations of Non-Additive Distortion Functions
    Bernard, Solene
    Bas, Patrick
    Pevny, Tomas
    Klein, John
    PROCEEDINGS OF THE 2021 ACM WORKSHOP ON INFORMATION HIDING AND MULTIMEDIA SECURITY, IH&MMSEC 2021, 2021, : 105 - 112
  • [24] ADDITIVE AND NON-ADDITIVE VISCOSITY BEHAVIOR OF POLYETHYLENE BLENDS
    POLTERSDORF, B
    FIEDLER, P
    HINZ, G
    PLASTE UND KAUTSCHUK, 1984, 31 (10): : 382 - 384
  • [25] Generalised asymptotic classes for additive and non-additive entropies
    Cabo Bizet, Nana
    Fuentes, Jesus
    Obregon, Octavio
    EPL, 2019, 128 (06)
  • [26] Additive and Non-Additive Risk Factors in Multiple Causation
    Van Velthoven, Ben C. J.
    Van Wijck, Peter W.
    REVIEW OF LAW & ECONOMICS, 2009, 5 (01) : 517 - 539
  • [27] Additive and Non-additive Biomass Equations for Black Wattle
    Behling, Alexandre
    Netto, Sylvio Pellico
    Sanquetta, Carlos Roberto
    Dalla Corte, Ana Paula
    Simon, Augusto Arlindo
    Rodrigues, Aurelio Lourenco
    Caron, Braulio Otomar
    FLORESTA E AMBIENTE, 2019, 26 (04):
  • [28] Shortest paths between shortest paths
    Kaminski, Marcin
    Medvedev, Paul
    Milanic, Martin
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (39) : 5205 - 5210
  • [29] A Note on Extensions of Non-additive Measures
    Ptak, Pavel
    Weber, Hans
    INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 2021, 60 (02) : 512 - 514
  • [30] Non-additive noise and optimal correlation
    Refregier, P
    Goudail, F
    Gaidon, T
    Guillaume, M
    INTERNATIONAL CONFERENCE ON IMAGE PROCESSING, PROCEEDINGS - VOL III, 1996, : 639 - 642
12345