✦ LIBER ✦

On minimizing the maximum congestion for Weighted Hypergraph Embedding in a Cycle

✍ Scribed by SingLing Lee; Hann-Jang Ho

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 77 KB
Volume: 87
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00297-7

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of Weighted Hypergraph Embedding in a Cycle (WHEC) is to embed the weighted hyperedges of a hypergraph as adjacent paths around a cycle, such that the maximum congestion over any physical link in the cycle is minimized. In this paper, we first show that even when hyperedges contain exactly two vertices, the WHEC problem is NP-complete. Afterwards we formulate the problem as an Integer Linear Program (ILP). Then, a solution with approximation ratio of two is presented by using LP-based rounding algorithm. Finally, to improve the efficiency, we develop a linear-time approximation algorithm to provide an embedding with congestion at most two times the optimum.

📜 SIMILAR VOLUMES

On the maximum number of edges in a hype

On the maximum number of edges in a hypergraph whose linegraph contains no cycle

✍ J.-C. Bermond; P. Frankl; F. Sterboul 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 122 KB

Soit H = (X. ~1 un hypergraphe h-uniforme avec IX] = net soit L h ~(H! le graphe Jont les sommets reprdsentent les arates de H, deux sommets 6lant reli6s si et seulement si t~s z~r6tes qu'ils reprdsen!ent intersectent en h -1 sommet,=. Nous montrons que sif,, t(H) ne contienl pas de cycle, alors I~[

Effects of couplings, container type and

Effects of couplings, container type and box size on maximum acceptable weight of lift : Garg, A., and Saxena, U. In. Compass for Technology, Proceedings of the 23rd Annual Meeting of the Human Factors Society, Boston, Massachusetts, Oct 29–Nov 1 1979, Edited by C.K. Bensel, pp 179–182

📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 141 KB

to the solution of a single shunter and a radio-controlled locomotive, thus eliminating the hazards associated with communications. Experience confirms the positive predictions concerning safety and workload. In the metalworks where the author is employed, remotecontrolled shunting is even performed