Circular arrangements and cyclic broadcast scheduling

Motivated by a scheduling problem in multicast environments, we consider the problem of arranging a weighted graph around a circle so as to minimize the total weighted arc length. We describe the first polynomial-time approximation algorithms for this problem, and specifically an O(logn)-approximation algorithm for undirected circular arrangements and an -approximation algorithm for directed circular arrangements. We will also conduct an experimental evaluation of our algorithms and show that a simple heuristic has the best performance in simulations based on busy Web server logs.