报告时间：2015年3月25日，14:00-
报告人：杨朝霞 博士
报告人单位：bat365在线官网入口 bat365在线官网入口
报告地点：教2-501室
报告题目：超图嵌入带权圈问题的多项式时间近似算法（A Polynomial Time Approximation Scheme for Embedding Hypergraph in a Weighted Cycle）
报告内容：The problem of Minimum Congestion Hypergraph Embedding in a Weighted Cycle (MCHEWC) is to embed the hyperedges of a hypergraph as paths in a weighted cycle such that the maximum congestion is minimized. This problem is NP-hard. It is a challenging problem with many applications in electronic design automation, computer networks, parallel computing and computer communication. We present a polynomial time approximation scheme (PTAS) for this problem. The general problem in which both the hypergraph and the cycle are weighted remains open.