یک الگوریتم برنامهریزی پویا برای مسئله تنظیم بسته بندی وزنی درخت مانند

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.

The set packing problem is an NP-Complete problem, it is one of 21 problems of Karp [8]. The set packing problem asks whether there are some k pairwise disjoint subsets in a family S of subsets of a universal set U. Bounding the cardinalities of the subsets by a number m results in a similar problem called m-set packing problem. That is, all the subsets should have cardinality at most m. This problem is also NP-Complete for m ⩾ 3 [2]. Algorithms for the parameterized version of m-Set Packing can be found in Fellows et al. [1], Jia et al. [7] and Liu et al. [11]. Below we define the weighted set packing problem as a decision problem. Definition. Let U be a set. Let S be a family of subsets of U . Let w : S → N be a weight function assigning (possibly negative) weights to the subsets. Let k ∈ N and h ∈ N . The weighted set packing problem asks whether there are some k pairwise disjoint subsets K in S such that h⩽∑D∈Kw(D)h⩽∑D∈Kw(D). Clearly, the weighted set packing problem is NP-Complete due to the NP-Completeness of the unweighted case. Problems similar to the weighted set packing problem can be found in the literature. For example, in Halldórsson and Chandra [5] the Weighted m-set packing problem was defined. This problem does not contain the constraint k, so, only the total weight is maximized. The optimization version of Weighted m-Set Packing is NP-Hard [5]. In Halldórsson and Chandra [5], an approximation algorithm for the problem was given with an approximation ratio 2(m + 1)/3. Also, a parameterized algorithm for Weighted m-Set Packing was introduced in Liu et al. [10]. In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets X and Y, either X is a subset of Y, or Y is a subset of X, or X and Y 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. For example, in military applications, the engagement rules for artillery correspond to this kind of target assignment problem [3]. This target assignment problem is equivalent to the weighted set packing problem in which the sets are nested. Other variations of hierarchical task assignment problems can be found in Toroslu and Arslanoglu [13]. Various forms of assignment problems have been studied in the literature [9], [6] and [12], but, none of them are similar to our work. In the following section we define the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming a tree-like hierarchical structure. Then, we describe an efficient solution using dynamic programming. To the best of our knowledge this is the first introduction of this problem.

In this paper we have defined the tree-like weighted set packing problem, which is a real life problem. The most common application occurs in the task assignment of hierarchical organizations. We have developed a dynamic programming algorithm with O(k2n) complexity. Correctness and complexity proofs were also given.