A dynamic programming algorithm for tree-like weighted set packing problem

Gulek M., TOROSLU İ. H.

INFORMATION SCIENCES, cilt.180, sa.20, ss.3974-3979, 2010 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 180 Sayı: 20
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1016/j.ins.2010.06.035
  • Dergi Adı: INFORMATION SCIENCES
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.3974-3979
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming tree-like hierarchical structure. We propose a dynamic programming algorithm with cubic time complexity. (C) 2010 Elsevier Inc. All rights reserved.