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

Date

2010-10-15

Author

Gulek, Mehmet
Toroslu, İsmail Hakkı

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

247
views

0
downloads

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.

Subject Keywords

Control and Systems Engineering, Theoretical Computer Science, Software, Information Systems and Management, Artificial Intelligence, Computer Science Applications

URI

https://hdl.handle.net/11511/39189

Journal

INFORMATION SCIENCES

DOI

https://doi.org/10.1016/j.ins.2010.06.035

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

An access structure for similarity-based fuzzy databases Yazıcı, Adnan (Elsevier BV, 1999-04-01) A significant effort has been made in representing imprecise information in database models by using fuzzy set theory. However, the research directed toward access structures to handle fuzzy querying effectively is still at an immature stage. Fuzzy querying involves more complex processing than the ordinary querying does. Additionally, a larger number of tuples are possibly selected by fuzzy conditions in comparison to the crisp ones. It is obvious that the need for fast response time becomes very important...
Verification and transformation of complex and uncertain conceptual schemas Yazıcı, Adnan (World Scientific Pub Co Pte Lt, 1997-12-01) In database environment it is necessary to represent complex and uncertain information at conceptual level and then transform the conceptual schema into the logical one for ultimate implementation. It is also important to verify the conceptual schema with respect to the constraints imposed on the schema definition. In this paper we primarily focus on the verification and transformation of the conceptual schema For the purpose of verification of the conceptual schema represented by the ExIFO data model (the ...
A finite field framework for modeling, analysis and control of finite state automata Reger, Johann; Schmidt, Klaus Verner (Informa UK Limited, 2004-09-01) In this paper, we address the modeling, analysis and control of finite state automata, which represent a standard class of discrete event systems. As opposed to graph theoretical methods, we consider an algebraic framework that resides on the finite field F-2 which is defined on a set of two elements with the operations addition and multiplication, both carried out modulo 2. The key characteristic of the model is its functional completeness in the sense that it is capable of describing most of the finite st...
A monolithic approach to automated composition of semantic web services with the Event Calculus Okutan, Cagla; Çiçekli, Fehime Nihan (Elsevier BV, 2010-07-01) In this paper, a web service composition and execution framework is presented for semantically -annotated web services. A monolithic approach to automated web service composition and execution problem is chosen, which provides some benefits by separating composition and execution phases. An AI planning method using a logical formalism, namely Abductive Event Calculus, is chosen for the composition phase. This formalism allows one to generate a narrative of actions and temporal orderings using abductive plan...
A method for concurrency control in distributed DBMSs: Permission Test Method Halıcı, Uğur (Association for Computing Machinery (ACM), 1987-01-09) In this paper, a method for concurrency control in distributed DBMSs, called Permission Test Method is proposed. The PT method satisfies the basic requirements for concurrency control, that is, it executes the transactions in a serializable order, deadlocks do not appear and indefinite postponment is prevented by the method. In PT method, transactions, which are permitted to run, are not aborted unless a related site failure occurs. Furthermore, the complexity analysis indicates that the algorithm will work...

Citation Formats

M. Gulek and İ. H. Toroslu, “A dynamic programming algorithm for tree-like weighted set packing problem,” INFORMATION SCIENCES, pp. 3974–3979, 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/39189.