Incremental assignment problem

被引：26
|
作者：
Toroslu, Ismail H. [1 ]
Ucoluk, Gokturk [1 ]
机构：
[1] Middle E Tech Univ, Dept Comp Engn, TR-06531 Ankara, Turkey
来源：
INFORMATION SCIENCES | 2007年 / 177卷 / 06期
关键词：
assignment problem; weighted bipartite graph; Hungarian algorithm;
D O I：
10.1016/j.ins.2006.05.004
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper we introduce the incremental assignment problem. In this problem, a new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. We propose an O(vertical bar V vertical bar(2)) algorithm for the problem. (c) 2006 Elsevier Inc. All rights reserved.
引用
收藏
页码：1523 / 1529
页数：7
相关论文
共 50 条
  • [31] Genetic algorithms for the sailor assignment problem
    Garrett, Deon
    Vannucci, Joseph
    Silva, Rodrigo
    Dasgupta, Dipankar
    Simien, James
    GECCO 2005: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOLS 1 AND 2, 2005, : 1921 - 1928
  • [32] Optimal discounts for the online assignment problem
    Spivey, Michael Z.
    OPERATIONS RESEARCH LETTERS, 2013, 41 (01) : 112 - 115
  • [33] Comparative analysis of the sailor assignment problem
    Vannucci, Joseph
    Garrett, Deon
    Dasgupta, Dipankar
    GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2, 2006, : 1881 - +
  • [34] An assignment problem with interdependent valuations and externalities
    Daddario, Tatiana
    McLean, Richard P.
    Postlewaite, Andrew
    ECONOMIC THEORY, 2024, 78 (02) : 567 - 592
  • [35] Orthogonal projections applied to the assignment problem
    Wolfe, WJ
    Ulmer, RM
    IEEE TRANSACTIONS ON NEURAL NETWORKS, 1997, 8 (03): : 774 - 778
  • [36] Improvement in Hungarian Algorithm for Assignment Problem
    Shah, Kartik
    Reddy, Praveenkumar
    Vairamuthu, S.
    ARTIFICIAL INTELLIGENCE AND EVOLUTIONARY ALGORITHMS IN ENGINEERING SYSTEMS, VOL 1, 2015, 324 : 1 - 8
  • [37] On the complexity of the assignment problem with ordinal data
    Oudghiri, Soufiane Drissi
    Hachimi, Mohamed
    INTERNATIONAL JOURNAL OF MATHEMATICS AND COMPUTER SCIENCE, 2020, 15 (01) : 155 - 181
  • [38] An alternative formulation for the fuzzy assignment problem
    Emrouznejad, A.
    Angiz, M. Zerafat L.
    Ho, W.
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2012, 63 (01) : 59 - 63
  • [39] THE RECURRENT METHOD TO SOLVE THE ASSIGNMENT PROBLEM
    Matsiy, O. B.
    Morozov, A. V.
    Panishev, A. V.
    CYBERNETICS AND SYSTEMS ANALYSIS, 2015, 51 (06) : 939 - 946
  • [40] The ζ(2) limit in the random assignment problem
    Aldous, DJ
    RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (04) : 381 - 418
12345