NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

DOI10.1023/B:JOSH.0000019682.75022.96zbMath1154.90445MaRDI QIDQ2464420

Alexander Hall, Erlebach, Thomas

Publication date: 20 December 2007

Published in: Journal of Scheduling (Search for Journal in Brave)

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (8)

Scheduling broadcasts with deadlines ⋮ Improved on-line broadcast scheduling with deadlines ⋮ Equivalence of two linear programming relaxations for broadcast scheduling. ⋮ Scheduling to minimize energy and flow time in broadcast scheduling ⋮ A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time ⋮ Single-source \(k\)-splittable min-cost flows ⋮ Minimum-cost single-source 2-splittable flow ⋮ Minimum-Cost Single-Source 2-Splittable Flow

This page was built for publication: NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow