NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow.

Thomas Erlebach Alexander Hall

Published in: J. Sched. (2004)

Keyphrases

min cost
np hardness
single source
approximation algorithms
broadcast scheduling
np hard
shortest path problem
combinatorial optimization problems
special case
multi source
minimum cost
network flow
worst case
max flow
shortest path
linear program
data fusion
upper bound
lower bound