Computers And Intractability A Guide To The Theory Of Np Completeness

By Klaudia Frankfurter. 2016

1,828 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

How Powerful are Graph Neural Networks? (2018, background): “This is a challenging problem: no polynomial-time algorithm is known for it yet (Garey, 1979; Garey & Johnson, 2002; Babai, 2016).”
A survey of swarm intelligence for dynamic optimization: Algorithms and applications (2017, background): “, it is strongly believed that they cannot be solved to optimality within polynomial computation time [109].”
UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats (2020, background): “Whole-system provenance graphs can grow large quickly [100], so NP-complete [42], [95] and even polynomial algorithms [71], [122] are too computationally expensive for streaming settings.”
A Survey on Device-to-Device Communication in Cellular Networks (2013, background): “The authors formulate the problem of joi t mode selection, resource allocation, and power alloc ti n through linear programming which is proven to be NP-Hard in a strong sense [60].”
Attention, Learn to Solve Routing Problems! (2018, unknown): “This seems discouraging as you know the problem is (NP-)hard (Garey & Johnson, 1979).”
Quantum circuits and low-degree polynomials over F2 (2016, unknown): “This is an NP-complete problem [21], but luckily an approximation h (cid:48) ( f ) ≤ 3 h ( f ) can be found in polynomial time (approximating h ( f ) any better than this is NP-hard [28], assuming the Unique Games Conjecture from complexity theory).”
Assortment Optimization under the Multinomial Logit Model with Random Choice Parameters (2014, unknown): “Q UESTION : Is there an assortment S ⊆ { 1, … , n } whose expected revenue is at least K , i.e., The proof of Theorem 1 involves a reduction from the P ARTITION problem, which is a well-known NP-complete problem (Garey and Johnson 1979).”
Security Arguments for Digital Signatures and Blind Signatures (2015, unknown): “Stated in a more accurate way, this approach proposes computational reductions to well established problems, such as factorization, RSA [49], the discrete logarithm problem or any NP-complete problem [24].”