Computing near-optimal solutions for the dominating subset with minimal weight problem


Urfat N., Burak O.

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, cilt.81, ss.1309-1318, 2004 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 81 Konu: 11
  • Basım Tarihi: 2004
  • Doi Numarası: 10.1080/03057920412331272126
  • Dergi Adı: INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
  • Sayfa Sayıları: ss.1309-1318

Özet

In this work, we consider a combinatorial "dominating subset with minimal weight" problem, which is an associative problem for solving global optimization problem. This problem can be expressed as a kind of assignment problem. The mathematical model and the economical interpretations of the problem are given and its properties are described. Then, we propose a new algorithm which has a ratio bound in polynomial time, by using above properties for solving the problem and present the results of numerical experiments.