Beyond Tree Embeddings -- a Deterministic Framework for Network Design with Deadlines or Delay

Yossi Azar, Noam Touitou

We consider network design problems with deadline or delay. All previous results for these models are based on randomized embedding of the graph into a tree (HST) and then solving…