Task assignment in tree-like hierarchical structures

Creative Commons License

EVRENDİLEK C., TOROSLU İ. H., Hashemikhabir S.

JOURNAL OF COMBINATORIAL OPTIMIZATION, vol.34, no.2, pp.631-655, 2017 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 34 Issue: 2
  • Publication Date: 2017
  • Doi Number: 10.1007/s10878-016-0097-6
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.631-655
  • Middle East Technical University Affiliated: Yes


Many large organizations, such as corporations, are hierarchical by nature. In hierarchical organizations, each entity, except the root, is a sub-part of another entity. In this paper, we study the task assignment problem to the entities of a tree-like hierarchical organization. The inherent tree structure introduces an interesting and challenging constraint to the standard assignment problem. Given a tree rooted at a designated node, a set of tasks, and a real-valued function denoting the weight of assigning a node to a task, the Maximum Weight Tree Matching (MWTM) problem aims at finding a maximum weight matching in such a way that no tasks are left unassigned, and none of the ancestors of an already assigned node is allowed to engage in an assignment. When a task is assigned to an entity in a hierarchical organization, the whole entity including its children becomes responsible from the execution of that particular task. In other words, if an entity has been assigned to a task, neither its descendants nor its ancestors can be assigned to any task. In the paper, we formally introduce MWTM, and prove its NP-hardness. We also propose and experimentally validate an effective heuristic solution based on iterative rounding of a linear programming relaxation for MWTM.