The edge asymmetry of a directed, edge-weighted graph is defined as the maximum ratio of the weight of antiparallel edges in the graph, and can be used as a measure of the heterogeneity of links in a data communication network. In this paper we provide a near-tight upper bound on the competitive ratio of the Online Steiner Tree problem in graphs of bounded edge asymmetry α. This problem has applications in efficient multicasting over networks with non-symmetric links. We show an improved upper bound of O (min { max { a log k/log α, a log k/log log k}, k }) on the competitive ratio of a simple greedy algorithm, for any request sequence of k terminals. The result almost matches the lower bound of Ω(min { max {α log k/log α, a log k/log log k}, k~(1-∈)}) (where e is an arbitrarily small constant) due to Faloutsos et al. [8] and Angelopoulos [2].
展开▼
机译：有向边加权图的边不对称性定义为图中反平行边权重的最大比率，并且可以用作数据通信网络中链路异构性的度量。在本文中，我们在有界边不对称α的图中提供了在线Steiner树问题的竞争比的近紧上限。此问题在具有非对称链接的网络上的有效多播中具有应用。我们针对k个终端的任何请求序列，在简单贪心算法的竞争比上显示了O的改进上限（min {max {log {k / logα，log k / log log k}，k}）。由于以下原因，结果几乎与Ω（min {max {max {αlog k / logα，log k / log log k}，k〜（1-∈）}）的下限匹配（其中e是任意小的常数）。 Faloutsos等。 [8]和Angelopoulos [2]。
展开▼
