Bounds on the performances of message routing heuristics

Let S be a set of messages to be routed on an N×N omega network. In addition, suppose that S contains communication conflicts. One strategy to deal with such conflicts is to partition S into some number of subsets, called rounds, such that each subset is conflict-free. The messages are then routed through the network by successively routing the messages in each subset. The minimum round partitioning problem, is the problem of partitioning a given message set into a minimum number of rounds. The authors consider heuristics for the minimum round partitioning problem. In particular, they establish upper and lower bounds on the performance ratio for two heuristics. For the first heuristic they give upper and lower bounds of O(√N) and Ω(logN), respectively. For the second heuristic they give a lower bound of Ω(logN), which matches a known upper bound of O(logN)