Improving heuristics for the frequency assignment problem

被引：54
|
作者：
Smith, DH [1 ]
Hurley, S
Thiel, SU
机构：
[1] Univ Glamorgan, Sch Accounting & Math, Div Math & Comp, Pontypridd CF37 1DL, M Glam, Wales
[2] Univ Wales Coll Cardiff, Dept Comp Sci, Cardiff CF2 3XF, S Glam, Wales
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1998年 / 107卷 / 01期
关键词：
frequency assignment; heuristics; graph theory;
D O I：
10.1016/S0377-2217(98)80006-4
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
Lower bounds for the frequency assignment problem can be found from maximal cliques and subgraphs related to cliques. In this paper we show that for many types of problem optimal assignments can be found by a process of assigning these subgraphs first, fixing the assignment and then extending the assignment to the full problem. We demonstrate the advantages of the method for some typical examples. In particular we give the first optimal assignments of several variants of the "Philadelphia" problems. These problems have been used by several authors to assess assignment methods and lower bounds. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：76 / 86
页数：11
相关论文
共 50 条
  • [11] New Heuristics for the Multidimensional Vote Assignment Problem
    P. Kleinschmidt
    C. Rank
    Computing, 1999, 63 : 405 - 417
  • [12] Greedy Heuristics for Client Assignment Problem by Zones
    Farlow, Shawn
    Trahan, Jerry L.
    PROCEEDINGS OF THE 12TH INTERNATIONAL CONFERENCE ON THE FOUNDATIONS OF DIGITAL GAMES (FDG'17), 2017,
  • [13] Local search heuristics for the multidimensional assignment problem
    Karapetyan, Daniel
    Gutin, Gregory
    JOURNAL OF HEURISTICS, 2011, 17 (03) : 201 - 249
  • [14] Evaluation of hotlink assignment heuristics for improving web access
    Czyzowicz, J
    Kranakis, E
    Krizanc, D
    Pelc, A
    Martin, MV
    IC'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INTERNET COMPUTING, VOLS I AND II, 2001, : 793 - 799
  • [15] Heuristics for the multi-resource generalized assignment problem
    Mazzola, JB
    Wilcox, SP
    NAVAL RESEARCH LOGISTICS, 2001, 48 (06) : 468 - 483
  • [16] Heuristics for a project management problem with incompatibility and assignment costs
    Nicolas Zufferey
    Olivier Labarthe
    David Schindl
    Computational Optimization and Applications, 2012, 51 : 1231 - 1252
  • [17] Improved Lagrangian bounds and heuristics for the generalized assignment problem
    Litvinchev, I.
    Mata, M.
    Saucedo, J.
    Rangel, S.
    JOURNAL OF COMPUTER AND SYSTEMS SCIENCES INTERNATIONAL, 2017, 56 (05) : 803 - 809
  • [18] Improved Lagrangian bounds and heuristics for the generalized assignment problem
    I. Litvinchev
    M. Mata
    J. Saucedo
    S. Rangel
    Journal of Computer and Systems Sciences International, 2017, 56 : 803 - 809
  • [19] A communication assignment problem on trees: Heuristics and asymptotic behavior
    Burkard, RE
    Cela, E
    Dudas, T
    NETWORK OPTIMIZATION, 1997, 450 : 127 - 155
  • [20] Heuristics for a project management problem with incompatibility and assignment costs
    Zufferey, Nicolas
    Labarthe, Olivier
    Schindl, David
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2012, 51 (03) : 1231 - 1252
12345