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

arXiv: https://arxiv.org/abs/2004.07946 · HTML: https://mlsanity.com/paper/2004.07946/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [Online Dynamic Acknowledgement with Learned Predictions](https://mlsanity.com/paper/2305.18227/) (2023)

## Abstract (arXiv)

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 the problem on this tree. We show that this is not necessary. In particular, we design a deterministic framework for these problems which is not based on embedding. This enables us to provide deterministic poly-log(n)-competitive algorithms for Steiner tree, generalized Steiner tree, node weighted Steiner tree, (non-uniform) facility location and directed Steiner tree with deadlines or with delay (where n is the number of nodes). Our deterministic algorithms also give improved guarantees over some previous randomized results. In addition, we show a lower bound of poly-log(n) for some of these problems, which implies that our framework is optimal up to the power of the poly-log. Our algorithms and techniques differ significantly from those in all previous considerations of these problems.