一个超图嵌入问题的多项式时间近似算法

Approximation algorithm about hypergraph embedding in a cycle

把定义在一个圈上的超图的每个超边映射为这个圈的一条路,每条超边的顶点均在对应的映射中,要求使圈中的任一边经过的路的最大次数最小,称此问题为超图在圈中的最小嵌入问题.将此问题归结为最近串选取问题,从而证明该问题存在多项式时间近似算法.

The problems of Minimum Congestion Hypergraph Embedding in a Cycle （MCHEC） is to embed the hyperedges of a hypergraph as paths in a cycle such that the maximum congestion （the maximum number of paths that use any single link in a cycle） is minimized. The MCHEC problem is NP-hard. In this paper, we consider the equivalent of this problem with another important problem in computational biology, and get conclusion that MCHEC has a PTAS.