超图嵌入带权重圈的一个2-近似算法

A 2-approximation algorithm for an embedded hypergraph in a weighted cycle

超图嵌入带权圈(HEWC)问题就是把超图的超边以路的形式嵌入一个带权圈,使得圈上任何带权连接边的最大阻塞最小。这个问题的一个简单形式是图嵌入带权圈(GEWC),即把普通图的边以路的形式嵌入一个带权圈。HEWC问题第一次被归结为一个整数线性规划问题,并且利用LP的放松问题和有界启发得到一个近似解。然后设计了一个非常简单有用的可以和LP近似算法得到一样好的近似解的线性时间近似算法。

The problem of hypergraph embedding in a weighted cycle （HEWC） is to embed the hyperedges of a hypergraph as the paths in a weighted cycle, such that the maximum congestion of any weighted link in the cycle is minimized. A simple version of this problem is graph embedding in a weighted cycle（GEWC） that embeds the edges of a normal graph as the paths in a weighted cycle. The HEWC problem was formulated as an integer linear program, and an approximation solution was obtained by using LP- relation and rounding heuristic. Then, a linear timne approximation algorithm was developed, which also provided a solution with the same worst case approximation bounds as LP-approximation.