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 ej e j on the cycle is used at most cj c j times, each hyperedge hi h i has its profit pi p i 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 ej e j has same capacity k , we propose an algorithm with approximation ratio 3 2 .
90b10 94c15