  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.[AAPW01] for routing virtual circuits with unknown
durations.
