Premium
The Push Tree problem
Author(s) -
Havet Frédéric,
Wennink Marc
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20038
Subject(s) - steiner tree problem , computer science , heuristics , tree (set theory) , mathematical optimization , shortest path problem , path (computing) , tree structure , theoretical computer science , algorithm , mathematics , graph , computer network , combinatorics , binary tree
Abstract In this article, we introduce the Push Tree problem, which exposes the tradeoffs between the use of push and pull mechanisms in information distribution systems. One of the interesting features of the Push Tree problem is that it provides a smooth transition between the minimum Steiner Tree and the Shortest Path problems. We present initial complexity results and analyze heuristics. Moreover, we discuss what lessons can be learned from the static and deterministic Push Tree problem for more realistic scenarios characterized by high uncertainty and changing information request and update patterns. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 281–291 2004