Computational aspects of the maximum diversity problem

被引：88
作者：
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 [J].
BURKARD, RE ;
RENDL, F .
OPERATIONS RESEARCH LETTERS, 1991, 10 (05) :303-308
[3]   GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES [J].
FEO, TA ;
RESENDE, MGC .
JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) :109-133
[4]   A GRASP-STAR FOR A DIFFICULT SINGLE-MACHINE SCHEDULING PROBLEM [J].
FEO, TA ;
VENKATRAMAN, K ;
BARD, JF .
COMPUTERS & OPERATIONS RESEARCH, 1991, 18 (08) :635-643
[5]  
GLOVER F, 1991, ADV NETFORM MODELS M
[6]   SEMI-GREEDY HEURISTICS - AN EMPIRICAL-STUDY [J].
HART, JP ;
SHOGAN, AW .
OPERATIONS RESEARCH LETTERS, 1987, 6 (03) :107-114
[7]   ANALYZING AND MODELING THE MAXIMUM DIVERSITY PROBLEM BY ZERO-ONE PROGRAMMING [J].
KUO, CC ;
GLOVER, F ;
DHIR, KS .
DECISION SCIENCES, 1993, 24 (06) :1171-1185
[8]   COMPUTATIONAL ASPECTS OF A BRANCH AND BOUND ALGORITHM FOR QUADRATIC ZERO-ONE PROGRAMMING [J].
PARDALOS, PM ;
RODGERS, GP .
COMPUTING, 1990, 45 (02) :131-144
[9]  
PARDALOS PM, 1994, DIMACS SERIES, V16
[10]  
PARDALOS PM, 1993, TOPICS PARALLEL COMP
1