Output details
11 - Computer Science and Informatics
University of Leicester
Article title
Broadcast Scheduling: Algorithms and Complexity
Type
D - Journal article
Title of journal
ACM TRANSACTIONS ON ALGORITHMS
Article number
ARTN 47
Volume number
7
Issue number
4
First page of article
-
ISSN of journal
1549-6325
Year of publication
2011
URL
-
Number of additional authors
3
Additional information
<12>Journal version of SODA 2008 paper. The paper gives rigorous proofs of two results that were claimed earlier without proofs or with incomplete proofs, and a new NP-hardness construction that unifies hardness proofs for many variants of broadcast scheduling. The ideas of our NP-hardness construction were subsequently adopted by other authors (e.g. by Althaus et al., SWAT 2008, to prove NP-hardness of a constrained interval coloring problem). Our paper also proposes delay factor minimization as an interesting objective for broadcast scheduling, and this has led to follow-up work by Chekuri and Moseley (SODA 2009) and others.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
1
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
