Computational aspects of the maximum diversity problem

被引：86
作者：
Ghosh, JB
机构：
[1] Faculty of Business Administration, Bilkent University, 06533 Bilkent, Ankara
来源：
OPERATIONS RESEARCH LETTERS | 1996年 / 19卷 / 04期
关键词：
maximum diversity; computational complexity; heuristics;
D O I：
10.1016/0167-6377(96)00025-9
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We address two variations of the maximum diversity problem which arises when m elements are to be selected from an n-element population based on inter-element distances. We study problem complexity and propose randomized greedy heuristics. Performance of the heuristics is tested on a limited basis.
引用
收藏
页码：175 / 181
页数：7
相关论文
共 10 条
  • [1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [2] LEXICOGRAPHIC BOTTLENECK PROBLEMS
    BURKARD, RE
    RENDL, F
    [J]. OPERATIONS RESEARCH LETTERS, 1991, 10 (05) : 303 - 308
  • [3] GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES
    FEO, TA
    RESENDE, MGC
    [J]. JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) : 109 - 133
  • [4] A GRASP-STAR FOR A DIFFICULT SINGLE-MACHINE SCHEDULING PROBLEM
    FEO, TA
    VENKATRAMAN, K
    BARD, JF
    [J]. COMPUTERS & OPERATIONS RESEARCH, 1991, 18 (08) : 635 - 643
  • [5] GLOVER F, 1991, ADV NETFORM MODELS M
  • [6] SEMI-GREEDY HEURISTICS - AN EMPIRICAL-STUDY
    HART, JP
    SHOGAN, AW
    [J]. OPERATIONS RESEARCH LETTERS, 1987, 6 (03) : 107 - 114
  • [7] ANALYZING AND MODELING THE MAXIMUM DIVERSITY PROBLEM BY ZERO-ONE PROGRAMMING
    KUO, CC
    GLOVER, F
    DHIR, KS
    [J]. DECISION SCIENCES, 1993, 24 (06) : 1171 - 1185
  • [8] COMPUTATIONAL ASPECTS OF A BRANCH AND BOUND ALGORITHM FOR QUADRATIC ZERO-ONE PROGRAMMING
    PARDALOS, PM
    RODGERS, GP
    [J]. COMPUTING, 1990, 45 (02) : 131 - 144
  • [9] PARDALOS PM, 1994, DIMACS SERIES, V16
  • [10] PARDALOS PM, 1993, TOPICS PARALLEL COMP
1