Elastic algorithms for guaranteeing quality monotonicity in big data mining

In Big Data, 2013 IEEE International Conference on, pp. 45-50. IEEE, 2013 (2014)

Given a directed graph G   and a threshold L(r)

 for each node r  , the rule of deterministic threshold cascading is that a node r   fails if and only if it has at least L(r)

 failed in-neighbors. The cascading failure minimization problem is to find at most k   edges to delete, such that the number of failed nodes is minimized. We prove an n1−ϵ

 inapproximability result for the general case and a View the MathML source

 inapproximability result for the special case with the maximum threshold of 1.