Combinatorial optimization algorithms for radio network planning

被引：24

作者：

Calégari, P

Guidec, F

Kuonen, P

Nielsen, F

机构：

[1] Ecole Polytech, Lab Informat LIX, CNRS, Unite 1439, F-91128 Palaiseau, France

[2] Swiss Fed Inst Technol, CH-1015 Lausanne, Switzerland

来源：

THEORETICAL COMPUTER SCIENCE | 2001年 / 263卷 / 1-2期

关键词：

combinatorial optimization; radio transceiver siting; set system; genetic algorithm; parallel computing;

D O I：

10.1016/S0304-3975(00)00245-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper uses a realistic problem taken from the telecommunication world as the basis for comparing different combinatorial optimization algorithms. The problem recalls the minimum hitting set problem, and is solved with greedy-like, Darwinism and genetic algorithms. These three paradigms are described and analyzed with emphasis on the Darwinism approach, which is based on the computation of epsilon -nets. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：235 / 245

页数：11

共 17 条

[1]

[Anonymous], P 47 VEH TECHN C IEE

[2]

BRONNIMANN H, 1995, DISCRETE COMPUT GEOM, V14, P263

[3] Parallel island-based genetic algorithm for radio network design [J].

Calegari, P ;

Guidec, F ;

Kuonen, P ;

Kobler, D .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1997, 47 (01) :86-90

[4]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[5]

Duh R., 1997, P 29 ANN ACM S THEOR, P256

[6]

FEIGE U, 1996, P 28 ACM S THEORY CO

[7]

HOLLAND JH, 1975, ADAPTATION NATURAL A

[8]

KARP R. M., 1972, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-1-4684-2001-2_9

[9]

Kearns MichaelJ., 1990, COMPUT COMPLEX

[10] ALMOST TIGHT BOUNDS FOR EPSILON-NETS [J].

KOMLOS, J ;

PACH, J ;

WOEGINGER, G .

DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 7 (02) :163-173

← 1 2 →