Colored Packets with Deadlines and Metric Space Transition Cost

Yossi Azar, Adi Vardi

We consider scheduling of colored packets with transition costs which form a general metric space. We design a $1-O(\sqrt{MST(G)/L})$ competitive algorithm. Our main result is…