Greedy maximal weighted scheduling for optical packet switches

Greedy algorithms are appealing not only because of their simplicity but also because of their effectiveness. In this paper, we study the possible greedy solutions for the optical switch scheduling problem. In particular, our algorithm 2AUGMENTATION combines the idea of simple greedy algorithm [7] and augmenting paths in maximal matching algorithms [9]. Our analysis and simulation shows that it yields satisfactory performance after comparing with the simple greedy algorithm. By generalizing this approach, we exploit the possibility of a class of greedy algorithms based on the maximal weighted matching heuristic.