The hypergraph embedding problem is to embed m hyperedges as adjacent paths of an n-vertex cycle, such that the maximum number of adjacent paths over any physical length of the cycle is minimized [1].

In this paper, Lee and Ho consider a weighted version of this embedding problem to minimize the maximum congestion of any physical link. They show that even when the hyperedges contain exactly two vertices, this problem is NP-complete. An integer linear program formulation is also derived to minimize the maximum congestion. A solution with an approximation ratio of two is presented using an LP-based rounding algorithm. The authors have developed a linear-time approximation algorithm that provides an embedding with congestion of, at most, twice the optimum.