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

Gulek M., TOROSLU İ. H.

INFORMATION SCIENCES, vol.180, no.20, pp.3974-3979, 2010 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 180 Issue: 20
  • Publication Date: 2010
  • Doi Number: 10.1016/j.ins.2010.06.035
  • Journal Name: INFORMATION SCIENCES
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.3974-3979
  • Middle East Technical University Affiliated: Yes

Abstract

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.