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

Abstract

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.

E-mail: [email protected]

Keywords:

• Dominating subset with minimal weight
• Global optimization
• Assignment problem
• Weighted set-covering problem
• Combinatorial optimization
• Cutting angle method

Notes

E-mail: [email protected]