A nonmonotone analysis with the primal–dual approach: Online routing of virtual circuits with unknown durations

We address the question of whether the primal–dual approach for the design and analysis of online algorithms can be applied to nonmonotone problems. We provide a positive answer by presenting a primal–dual analysis to the online algorithm of Awerbuch et al. [3] for routing virtual circuits with unknown durations.