An Optimization Problem Related to VoD Broadcasting

Consider a tree

T

of depth 2 whose root has

s

child nodes and the

k

th

child node from left has

n

k

child leaves. Considered as a round-robin tree,

T

represents a schedule in which each page assigned to a leaf under node

k

(1≤

k

≤

s

) appears with period

sn

k

. By varying

s

, we want to maximize the total number

n

=

$\sum_{k=1}^{s}$

n

k

of pages assigned to the leaves with the following constraints: for 1≤

k

≤

s

,

$n_{k} = \lfloor(m + \sum_{j=1}^{ k-1}n_{j} )/s\rfloor$

, where

m

is a given integer parameter. This problem arises in the optimization of a video-on-demand scheme, called

Fixed-Delay Pagoda Broadcasting

.

Due to the floor functions involved, the only known algorithm for finding the optimal

s

is essentially exhaustive, testing

m

/2 different potential optimal values of size

O

(

m

) for

s

. Since computing

n

for a given value of

s

incurs time

O

(

s

), the time complexity of finding the optimal

s

is

O

(

m

2

). This paper analyzes this combinatorial optimization problem in detail and limits the search space for the optimal

s

down to

$\kappa \sqrt{m}$

different values of size

$O \sqrt{m}$

each, where

κ

≈ 0.9, thus improving the time complexity down to

O

(

m

).