On packing and coloring hyperedges in a cycle

Given a hypergraph and k   different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link ejej on the cycle is used at most cjcj times, each hyperedge hihi has its profit pipi and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC).In this paper, we prove that the MPPCHC problem is NP  -hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link ejej has same capacity k  , we propose an algorithm with approximation ratio 32.