Publication Details
Title: Broadcasting Time Cannot be Approximated Within a Factor of 57/56-epsilon
Author: C. Schindelhauer
Group: ICSI Technical Reports
Date: March 2000
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/2000/tr-00-002.pdf
Overview:
In the beginning the information is available only at some sources of a given network. The aim is to inform all nodes of the given network. Therefore, every node can inform its neighborhood sequentially and newly informed nodes can proceed in parallel within their neighborhoods. The process of informing one node needs one time unit. The broadcasting problem is to compute the minimum length of such a broadcasting schedule. The computational complexity of broadcasting is investigated and for the first time a constant lower inapproximability bound is stated, i.e. it is NP-hard to distinguish between graphs with broadcasting time smaller than b and larger than (57/56-ε)b for any ε>0. This improves on the lower bounds known for multiple and single source broadcasting, which could only state that it is NP-hard to distinguish between graphs with broadcasting time b and b+1, for any b >= 3. This statement is proven by reduction from E3-SAT, the analysis of which needs a carefully designed book-keeping and counting argument.
Bibliographic Information:
ICSI Technical Report TR-00-002
Bibliographic Reference:
C. Schindelhauer. Broadcasting Time Cannot be Approximated Within a Factor of 57/56-epsilon. ICSI Technical Report TR-00-002, March 2000
Author: C. Schindelhauer
Group: ICSI Technical Reports
Date: March 2000
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/2000/tr-00-002.pdf
Overview:
In the beginning the information is available only at some sources of a given network. The aim is to inform all nodes of the given network. Therefore, every node can inform its neighborhood sequentially and newly informed nodes can proceed in parallel within their neighborhoods. The process of informing one node needs one time unit. The broadcasting problem is to compute the minimum length of such a broadcasting schedule. The computational complexity of broadcasting is investigated and for the first time a constant lower inapproximability bound is stated, i.e. it is NP-hard to distinguish between graphs with broadcasting time smaller than b and larger than (57/56-ε)b for any ε>0. This improves on the lower bounds known for multiple and single source broadcasting, which could only state that it is NP-hard to distinguish between graphs with broadcasting time b and b+1, for any b >= 3. This statement is proven by reduction from E3-SAT, the analysis of which needs a carefully designed book-keeping and counting argument.
Bibliographic Information:
ICSI Technical Report TR-00-002
Bibliographic Reference:
C. Schindelhauer. Broadcasting Time Cannot be Approximated Within a Factor of 57/56-epsilon. ICSI Technical Report TR-00-002, March 2000