Cooperative item collecting problems in directed bipartite structures

Abstract

In this paper, a variant of 0-1 knapsack problems in graph structures is considered. Given a directed bipartite structure with a set of items and a set of players, the problem asks to find an arc reversing strategy of the players which collects items with a budget constraint so that the total weighted profit of the collected items is maximized. More players than one are associated with an item by their directed arcs, and in order to win the weighted profit, it is indispensable for the players to make their arcs with respect to the item in the same direction. The situation of the same direction of associated arcs with an item is regarded as a cooperation of the associated players with the item, and the problem is called CIC (cooperative item collecting) for short. Problem CIC is viewed as a generalization of an integrated circuit design problem, in which a certain type of the cost of changes from an initial design is newly considered. A cooperation of associated players with an item is generally adverse to another item, and problem CIC is also seen as a compromising model in conflictive states. In this paper, some complexity results of problem CIC including the NP-hardness are discussed, and greedy heuristic algorithms are designed. Numerical experiments are conducted to demonstrate the performance of the greedy heuristic algorithms, and the results are reported.

Keywords

• engineering optimization
• 0-1 knapsack problems
• directed bipartite graphs
• cooperative arc reversing
• greedy heuristics