Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized.

The minimum congestion hypergraph embedding in a cycle problem is known to be NP-hard and its graph version, the minimum congestion graph embedding in a cycle, is solvable in polynomial-time. Furthermore, for the graph problem, a polynomial-time approximation scheme for the weighted version is known. For the hypergraph model, several approximation algorithms with a ratio of two have been previously published. A recent paper reduced the approximation ratio to 1.5. We present a polynomial-time approximation scheme in this article, settling the debate regarding whether the problem is polynomial-time approximable.

REFERENCES

• 1: Frank, A. 1985. Edge-disjoint paths in planar graphs. J. Combin. Theory Ser. B 38, 164--178.
• 2: Joseph L. Ganley , James P. Cohoon, Minimum-Congestion Hypergraph Embedding in a Cycle, IEEE Transactions on Computers, v.46 n.5, p.600-602, May 1997 [doi>10.1109/12.589233]
• 3: Teofilo F. Gonzalez, Improved approximation algorithms for embedding hyperedges in a cycle, Information Processing Letters, v.67 n.5, p.267-271, Sept. 15, 1998 [doi>10.1016/S0020-0190(98)00117-3]
• 4: Gu, Q. P., and Wang, Y. 2003. Efficient algorithm for embedding hypergraph in a cycle. In Proceedings of the 10th International Conference on High Performance Computing, 85--94.
• 5: Khanna, S. 1997. A polynomial time approximation scheme for the SONET ring loading problem. Bell Labs Tech. J. 2, 36--41.
• 6: S. L. Lee , H-J. Ho, Algorithms and Complexity for Weighted Hypergraph Embedding in a Cycle, Proceedings of the First International Symposium on Cyber Worlds (CW'02), p.0070, November 06-08, 2002
• 7: SingLing Lee , Hann-Jang Ho, A 1.5 Approximation Algorithm for Embedding Hyperedges in a Cycle, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.481-488, June 2005 [doi>10.1109/TPDS.2005.62]
• 8: Ming Li , Bin Ma , Lusheng Wang, On the closest string and substring problems, Journal of the ACM (JACM), v.49 n.2, p.157-171, March 2002 [doi>10.1145/506147.506150]
• 9: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 10: András Frank , Takao Nishizeki , Nobuji Saito , Hitoshi Suzuki , Éva Tardos, Algorithms for routing around a rectangle, Discrete Applied Mathematics, v.40 n.3, p.363-378, Dec. 14, 1992 [doi>10.1016/0166-218X(92)90007-W]
• 11: Okamura, H., and Seymour, P. 1981. Multicommodity flows in planar graph. J. Combin. Theory Ser. B 31, 75--81.
• 12: Anand Srivastav , Peter Stangier, Algorithmic Chernoff-Hoeffding inequalities in integer programming, Random Structures & Algorithms, v.8 n.1, p.27-58, Jan. 1996 [doi>10.1002/(SICI)1098-2418(199601)8:1<27::AID-RSA2>3.0.CO;2-T]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Hypergraph embedding, NP-hard, minimum congestion, polynomial-time approximation scheme