Minimum-Cost Broadcast through Varying-Size Neighborcast

In traditional multihop network broadcast problems, in which a message beginning at one node is efficiently relayed to all others, cost models typically used involve a charge for each

unicast

or each

broadcast

. These settings lead to a minimum spanning tree (MST) problem or the Connected Dominating Set (CDS) problem, respectively. Neglected, however, is the study of intermediate models in which a node can choose to transmit to an arbitrary subset of its neighbors, at a cost based on the number of recipients (due e.g. to acknowledgements or repeat transmissions). We focus in this paper on a transmission cost model of the form 1 + 

A

k

b

, where

k

is the number of recipients,

b

 ≥ 0, and

A

 ≥ 0, which subsumes MST, CDS, and other problems.

We give a systematic analysis of this problem as parameterized by

b

(relative to

A

), including positive and negative results. In particular, we show the problem is approximable with a factor varying from 2 + 2

H

Δ

down to 2 as

b

varies from 0 to 1 (via a modified CDS algorithm), and thence with a factor varying from 2 to 1 (i.e., optimal) as

b

varies from 1 to

$\log_2 (\frac{1}{A}+2)$

, and optimal thereafter (both via spanning tree).

For arbitrary cost functions of the form 1 + 

Af

(

k

), these algorithms provide a 2 + 2

H

Δ

-approximation whenever

f

(

k

) is sublinear and a (1 + 

A

)/

A

-approximation whenever

f

(

k

) is superlinear, respectively. We also show that the problem is optimally solvable for any

b

when the network is a clique or a tree.