Some NP-complete problems in quadratic and nonlinear programming
The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“In fact, global optimization problems are undecidable in unbounded domains [109], and NP-hard on bounded domains [110].”
From Reverse engineering and identification in systems biology: strategies, perspectives and challenges (2014) · cites this paper as [110]
Citations
Cites
(1979) · Cited by 43,841
Theory of Linear and Integer Programming
Letchford, A. N., & Schrijver, A. (2000) · The Journal of the Operational Research Society · doi:10.2307/253980 · Cited by 5,515
Mangasarian, O. L. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971255 · Cited by 3,220
Theory of Linear and Integer Programming
Smith, D. K. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.94 · Cited by 2,708
Nonlinear Programming: Sequential Unconstrained Minimization Techniques
Fiacco, A. V., & McCormick, G. P. (1968) · Defense Technical Information Center (DTIC) · Cited by 2,262
Nonlinear Programming--Sequential Unconstrained Minimization Techniques
Powell, M. J. D. (1969) · The Computer Journal · doi:10.1093/comjnl/12.3.207-a · Cited by 1,757 · cited 3×
“For nonconvex NLPs, under some CQ, necessary conditions for a local minimum are known, and there are some sufficient conditions [ 2 , 4, 7]. There are no known simple conditions, which are both necessary and sufficient for a given point to be a local minimum.”
BackgroundInfluentialLinear complementarity, linear and nonlinear programming
(1989) · European Journal of Operational Research · doi:10.1016/0377-2217(89)90500-6 · Cited by 978
Beale, E. M. L., Künzi, H. P., Krelle, W. E., Oettli, W., & Levin, F. (1968) · Journal of the Royal Statistical Society Series A (General) · doi:10.2307/2343863 · Cited by 713
Allgower, E. L., & Georg, K. (1980) · SIAM Review · doi:10.1137/1022003 · Cited by 439 · cited 1×
“The class of complementary pivot methods or simplicial methods for NLP [ 1 ,5,7, 10] are examples of algorithms in this class (these algorithms convert the system of first order necessary conditions into a Kakutani fixed point problem, which is then solved by complementary pivoting on a triangulation of the space).”
MethodLinear and Combinatorial Programming
Sergeant, C. R., & Murty, K. G. (1977) · Journal of the Operational Research Society · doi:10.2307/3008975 · Cited by 427
Self-citation
Research works printed but not linked: 2
- O.H. Merrill, “Application and extensions of an alogirithm that computes fixed points of upper semicontinous point to set mappings” Ph.D. Dissertation, University of Michigan, Ann Arbor, MI (1972).
- K.G. Murty,Linear Programming (Wiley, New York, 1983).
Cited by
Items 501–600 of 1,000
Structured model reduction for dynamical networked systems
Papachristodoulou, A., Chang, Y.-C., August, E., & Anderson, J. (2010) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2010.5718017 · Cited by 11
“This problem is numerically hard even if these two constraints were polynomial inequalities, as deciding polynomial non-negativity is NP-hard [26].”
BackgroundPiecewise-Linear Motion Planning amidst Static, Moving, or Morphing Obstacles
Khadir, B. E., Lasserre, J. B., & Sindhwani, V. (2021) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra48506.2021.9561614 · Cited by 11
“In fact it is NP-hard even when m 1 = 0 , m 2 = 0 , and p is a polynomial of degree four (see, e.g., [21]).”
BackgroundSublinear circuits and the constrained signomial nonnegativity problem
Murray, R., Naumann, H., & Theobald, T. (2022) · Mathematical Programming · doi:10.1007/s10107-022-01776-w · Cited by 11
“Deciding such nonnegativity problems is NP-hard in general [24].”
BackgroundExact and fast algorithms for mixed-integer nonlinear programming
Gleixner, A. (2015) · DepositOnce · doi:10.14279/depositonce-4938 · Cited by 20
Ithapu, V. K., Ravi, S. N., & Singh, V. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.08670 · Cited by 14
Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization ProblemsPreprint
Kong, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.09685 · Cited by 11
A Multigrid Approach to SDP Relaxations of Sparse Polynomial Optimization Problems
Campos, J. S., & Parpas, P. (2018) · SIAM Journal on Optimization · doi:10.1137/16m1109060 · Cited by 10
Fronthaul-Aware Resource Allocation for Energy Efficiency Maximization in C-RANs
Younis, A., Tran, T. X., & Pompili, D. (2018) · IEEE International Conference on Autonomic Computing (ICAC) · doi:10.1109/icac.2018.00019 · Cited by 10
“It can be seen that P 0 is a MINLP, which is NP-hard [23] and is highly difficult to solve optimally in polynomial time.”
BackgroundTian, Y., Fang, S., Deng, Z., & Xing, W. (2013) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2013.9.703 · Cited by 10
On the complexity of detecting convexity over a box
Ahmadi, A. A., & Hall, G. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01396-x · Cited by 10
A new certificate for copositivity
Dickinson, P. J. C. (2019) · Linear Algebra and its Applications · doi:10.1016/j.laa.2018.12.025 · Cited by 10
Energy-Efficient On-Demand Cloud Radio Access Networks Virtualization
Liu, Q., Han, T., & Ansari, N. (2018) · Globecom · doi:10.1109/glocom.2018.8647929 · Cited by 10
“The non-convex objective function and integer variables make problem P1 a highly complex mixed integer nonlinear programming problem, which lacks efficient solutions [18].”
BackgroundMangoubi, O., & Vishnoi, N. K. (2021) · Mathematics of Operations Research · doi:10.1145/3406325.3451097 · Cited by 22
Liu, X., Tao, W., & Pan, Z. (2022) · Information Sciences · doi:10.1016/j.ins.2022.08.090 · Cited by 10
Approximate Message Passing With Parameter Estimation for Heavily Quantized Measurements
Huang, S., Qiu, D., & Tran, T. D. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3167516 · Cited by 11
Sum-of-Squares Certificates for Copositivity via Test States
Schweighofer, M., & Vargas, L. F. (2024) · SIAM Journal on Applied Algebra and Geometry · doi:10.1137/23m1611798 · Cited by 10
Global Optimization: A Quadratic Programming Perspective
Bomze, I. M. (2010) · Lecture notes in mathematics · doi:10.1007/978-3-642-11339-0_1 · Cited by 10
“This is not surprising in view of the result that checking local optimality of KKT points is NPhard [ 52 ].”
ResultReduciendo distancias entre el control borroso y el control no lineal: luces y sombras
Sala, A., & Ariño, C. V. (2009) · Revista Iberoamericana de Automática e Informática Industrial RIAI · doi:10.1016/s1697-7912(09)70090-1 · Cited by 10
Speeding up a memetic algorithm for the max-bisection problem
Zhu, W., Liu, Y., & Lin, G. (2015) · Numerical Algebra Control and Optimization · doi:10.3934/naco.2015.5.151 · Cited by 10
“MBP is a known NP-complete problem [32], and has a large number of applications in various areas, such as sparse matrix computation [1], scientific computing [18, 38], and VLSI design [3, 6, 27].”
BackgroundDetermining input‐to‐state and incremental input‐to‐state stability of nonpolynomial systems
Voßwinkel, R., & Röbenack, K. (2020) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.5012 · Cited by 10
“The constraints directly induced by the recasting process are given by x2 = F(x1), (8)”
MethodA Game Theory-Based Multi-Agent System for Expensive Optimisation Problems
Salhi, A., & Töreyen, Ö. (2010) · Adaptation, learning, and optimization · doi:10.1007/978-3-642-12775-5_9 · Cited by 11
“Indeed, even checking a given solution for optimality is NP-hard [10, 17, 32].”
BackgroundMatrix cones, complementarity problems, and the bilinear matrix inequality
Mesbahi, M., Papavassilopoulos, G. P., & Safonov, M. G. (2002) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.1995.478622 · Cited by 10
Resource Allocation for Periodic Applications in a Shipboard Environment
Shestak, V., Chong, E. K. P., Maciejewski, A. A., Siegel, H. J., Benmohamed, L., Wang, I.-J., & Daley, R. A. (2005) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2005.382 · Cited by 10
“However, with such a condition, the problem falls into the category of NP-complete Integer Programming (IP) problems [27].”
BackgroundRelative Robust Portfolio Optimization
Hauser, R., Krishnamurthy, V., & Tütüncü, R. H. (2013) · Oxford University Research Archive (ORA) (University of Oxford) · doi:10.48550/arxiv.1305.0144 · Cited by 14
“Testing whether a given matrix belongs to this cone is coNP-hard [16].”
BackgroundA Max-Min Entropy Framework for Reinforcement LearningPreprint
Han, S., & Sung, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.10517 · Cited by 15
“However, non-convex max-min problems are more challenging [38] and there are several recent studies to find (approximiate) solutions to non-convex max-min optimization problems [6, 42, 44].”
BackgroundPositive Maps and Extendibility Hierarchies From Copositive Matrices
Gulati, A., Nechita, I., & Park, S. (2026) · Annales Henri Poincaré · doi:10.1007/s00023-026-01763-3 · Cited by 9
A Complete Set of Quadratic Constraints for Repeated ReLU and Generalizations
Noori, S. V., Hu, B., Dullerud, G. E., & Seiler, P. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3640487 · Cited by 9
Steady‐state process optimization with guaranteed robust stability under parametric uncertainty
Chang, Y., & Sahinidis, N. V. (2010) · AIChE Journal · doi:10.1002/aic.12530 · Cited by 9
Next-to-leading order unitarity fits in the extended Georgi-Machacek model
Chowdhury, D., Mondal, P., & Samanta, S. (2026) · Journal of Physics G Nuclear and Particle Physics · doi:10.1088/1361-6471/ae9894 · Cited by 9
Global optimization technique for fixed-order control design
Famularo, D., Pugliese, P., & Sergeyev, Y. D. (2004) · International Journal of Systems Science · doi:10.1080/00207720410001734192 · Cited by 9
On the exactness of sum-of-squares approximations for the cone of 5 × 5 copositive matrices
Laurent, M., & Vargas, L. F. (2022) · Linear Algebra and its Applications · doi:10.1016/j.laa.2022.06.015 · Cited by 9
“Determining whether a matrix M is copositive is a co-NP-complete problem (see [20]).”
BackgroundEquivalences and differences in conic relaxations of combinatorial quadratic optimization problems
Ito, N., Kim, S. Y., Kojima, M., Takeda, A., & Toh, K.-C. (2018) · Journal of Global Optimization · doi:10.1007/s10898-018-0676-4 · Cited by 9
“However, these CPP reformulations of QOPs are mainly of theoretical interest as CPPs are known to be numerically intractable [18].”
BackgroundBeyond Submodular Maximization via One-Sided Smoothness
Ghadiri, M., Santiago, R., & Shepherd, F. B. (2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976465.63 · Cited by 14
Wang, J., & Xia, Y. (2020) · SIAM Journal on Optimization · doi:10.1137/19m1294459 · Cited by 9
Computational Complexity, NP Completeness and Optimization Duality: A Survey.Preprint
Manyem, P., & Ugon, J. (2012) · Cited by 9
Lu, S., Razaviyayn, M., Yang, B., Huang, K., & Hong, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.04450 · Cited by 9
Complexity Theory: Quadratic Programming
Vavasis, S. A. (2008) · Springer eBooks · doi:10.1007/978-0-387-74759-0_81 · Cited by 9
Approximating the ACOPF problem with a hierarchy of SOCP problems
Kuang, X., Zuluaga, L. F., Ghaddar, B., & Naoum‐Sawaya, J. (2015) · IEEE Power Engineering Society General Meeting · doi:10.1109/pesgm.2015.7285718 · Cited by 8
Panuccio, P., Ghasemzadeh, H. G., Fortino, G., & Jafari, R. (2011) · ACM Workshop on Mobile Systems, Applications, and Services for Healthcare (mHealthSys) · doi:10.1145/2064942.2064950 · Cited by 8
“2 Problem Complexity The optimization problem presented in (5) poses several difficulties in arriving at an optimal solution: 1) The communication cost in (3) is a concave function and minimizing a concave function is considered to be hard in general [5].”
BackgroundLearning kernels for variants of normalized cuts: Convex relaxations and applications
Mukherjee, L., Singh, V., Peng, J., & Chris Hinrichs, A. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5540076 · Cited by 8
“The problem is NP-hard [25] for Q ⋡ 0; several algorithms have been proposed [23;26] that consider various convex relaxations for StQP.”
BackgroundInfluentialOn the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials
Ahmadi, A. A., & Parrilo, P. A. (2010) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2010.5717510 · Cited by 8
“to be computationally intractable (already NP-hard for polynomials of degree four [1]).”
BackgroundA positive definite polynomial Hessian that does not factor
Ahmadi, A. A., & Parrilo, P. A. (2009) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2009.5400519 · Cited by 8
“It is well known that in the absence of convexity, global minimization of polynomials is generally NP-hard [1], [2], [3].”
BackgroundInverse function theorem for polynomial equations using semidefinite programming
Ashraphijuo, M., Madani, R., & Lavaei, J. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7403257 · Cited by 8
“Due to this equivalence, every polynomial optimization problem can be transformed into a quadratically-constrained quadratic program (QCQP), whose complexity is extensively studied in the literature [16], [17].”
BackgroundPiecewise Semi-Ellipsoidal Control Invariant Sets
Legat, B., Raković, S. V., & Jungers, R. M. (2020) · IEEE Control Systems Letters · doi:10.1109/lcsys.2020.3005326 · Cited by 8
“While checking copositivity of a matrix is co-NP-complete [11], sufficient conditions such as Proposition 2 can be encoded as a LMI.”
BackgroundFast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence
Fort, G., Gach, P., & Moulines, É. (2021) · Statistics and Computing · doi:10.1007/s11222-021-10023-9 · Cited by 8
An active-set algorithm for norm constrained quadratic problems
Rontsis, N., Goulart, P. J., & Nakatsukasa, Y. (2021) · Mathematical Programming · doi:10.1007/s10107-021-01617-2 · Cited by 8
An approximation algorithm for indefinite mixed integer quadratic programming
Pia, A. D. (2022) · Mathematical Programming · doi:10.1007/s10107-022-01907-3 · Cited by 8
“In particular, Theorem 2 strengthens the result by Murty and Kabadi [26] that deciding whether a QP is bounded or not is NP-hard.”
BackgroundComplex Event Summarization Using Multi-Social Attribute Correlation
Chen, X., Zhou, X., Chan, J., Chen, L., Sellis, T., & Zhang, Y. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3227906 · Cited by 8
“We will prove that the Optimal Summary Set Selection is NP-complete by a two-step reduction from the classic NP-complete problem, Subset Sum problem [49].”
MethodResource Scheduling for UAV-Assisted Failure-Prone MEC in Industrial Internet
Li, X., Fang, Y., Pan, C., Cai, Y., & Zhou, M. (2023) · Drones · doi:10.3390/drones7040259 · Cited by 8
A completely positive representation of 0–1 linear programs with joint probabilistic constraints
Cheng, J., & Lisser, A. (2013) · Operations Research Letters · doi:10.1016/j.orl.2013.08.008 · Cited by 8
Lu, J. J.-Q., August, E., & Koeppl, H. (2012) · Journal of Mathematical Biology · doi:10.1007/s00285-012-0523-z · Cited by 9
A new approximation hierarchy for polynomial conic optimization
Dickinson, P. J. C., & Povh, J. (2019) · Computational Optimization and Applications · doi:10.1007/s10589-019-00066-0 · Cited by 8
Polyhedral approximations of the semidefinite cone and their application
Wang, Y., Tanaka, A., & Yoshise, A. (2021) · Computational Optimization and Applications · doi:10.1007/s10589-020-00255-2 · Cited by 8
A Nonconvex Optimization Approach to IMRT Planning with Dose–Volume Constraints
Maass, K. L., Kim, M., & Aravkin, A. Y. (2022) · INFORMS journal on computing · doi:10.1287/ijoc.2021.1129 · Cited by 8
“More generally, it is an NP-hard problem just to certify whether a point of a nonlinear function is a local minimum (let alone a global one) [65].”
BackgroundProjection-free Decentralized Online Learning for Submodular Maximization over Time-Varying Networks
Zhu, J., Wu, Q., Zhang, M., Zheng, R., & Li, K. (2021) · Journal of Machine Learning Research · Cited by 8
Obtaining certificates for complete synchronisation of coupled oscillators
August, E., & Barahona, M. (2011) · Physica D Nonlinear Phenomena · doi:10.1016/j.physd.2010.12.008 · Cited by 8
“On the other hand, testing positivity of a polynomial is NP-hard [17].”
BackgroundAn objective general index for multivariate ordered data
Sei, T. (2016) · Journal of Multivariate Analysis · doi:10.1016/j.jmva.2016.02.005 · Cited by 8
SPN graphs: When copositive = SPN
Shaked-Monderer, N. (2016) · Linear Algebra and its Applications · doi:10.1016/j.laa.2016.07.018 · Cited by 8
“It has been proved in [16] that checking whether a given matrix is copositive is a co-NP-complete problem.”
BackgroundEmbedded variable selection method using signomial classification
Hwang, K., Kim, D., Lee, K., Lee, C., & Park, S. (2017) · Annals of Operations Research · doi:10.1007/s10479-017-2445-z · Cited by 8
On approximation algorithms for concave mixed-integer quadratic programming
Pia, A. D. (2017) · Mathematical Programming · doi:10.1007/s10107-017-1178-8 · Cited by 8
“We remark that detecting if a general MIQP problem is unbounded isNP-hard even in the pure continuous case (see [11,22]).”
BackgroundA simplex algorithm for rational cp-factorization
Sikirić, M. D., Schürmann, A., & Vallentin, F. (2020) · Mathematical Programming · doi:10.1007/s10107-020-01467-4 · Cited by 8
Computational Complexity of Lyapunov Stability Analysis Problems for a Class of Nonlinear Systems
McConley, M. W., Appleby, B. D., Dahleh, M. A., & Féron, É. (1998) · SIAM Journal on Control and Optimization · doi:10.1137/s0363012997320316 · Cited by 8
On some interior-point algorithms for nonconvex quadratic optimization
Tseng, P., & Ye, Y. (2002) · Mathematical Programming · doi:10.1007/s10107-002-0310-5 · Cited by 8
“Notice that the origin is a local minimum of this problem (which is equivalent to the origin being a global minimum of this problem) if and only if there does not exist an x ∗ ≥ 0 with f( x ∗ ) 4 ], [5, Section 5.1].”
BackgroundInfluentialEfficiently testing local optimality and escaping saddles for ReLU networksPreprint
Yun, C., Sra, S., & Jadbabaie, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.10858 · Cited by 8
Engineering and Business Applications of Sum of Squares PolynomialsPreprint
Hall, G. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.07961 · Cited by 8
“Indeed, searching for polynomial Lyapunov functions that verify (i)-(iii) is a hard problem as it requires constraining polynomials to be positive on R n , a problem that we know to be hard for degree-4 polynomials already [ MK87 ].”
BackgroundStability analysis and controller synthesis for a class of piecewise smooth systems
Samadi, B. (2008) · Spectrum Research Repository (Concordia University) · Cited by 8
An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs
Yıldırım, E. A. (2021) · Journal of Global Optimization · doi:10.1007/s10898-021-01066-3 · Cited by 7
The Complexity of Computing KKT Solutions of Quadratic Programs
Fearnley, J., Goldberg, P. W., Hollender, A., & Savani, R. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649647 · Cited by 7
“Recently [14] showed that CLS is equal to the intersection of PPAD and PLS , in the process showing that it is CLS -complete to find KKT solutions of piecewise polynomial functions defined by a certain class of arithmetic circuits.”
Argus: Federated Non-Convex Bilevel Learning Over 6G Space-Air-Ground Integrated Network
Liu, Y., Yang, K., Zhu, Y., Yang, K., & Zhao, H. (2025) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2025.3582695 · Cited by 8
“Index Terms —6G, bilevel learning, decentralized optimization, federated learning.”
Differentially Private Distributed Nonconvex Stochastic Optimization With Quantized Communication
Chen, J., Wang, J., & Zhang, J. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3590872 · Cited by 7
“Theorem 2: If Assumptions 1-4 hold, then for any node i ∈ V and K ≥ 1 , we have lim inf K →∞ E ∥∇ F ( x i,K +1 ) ∥ 2 = 0 .”
Grassmannian Optimization Is NP-Hard
Lai, Z., Lim, L., & Ye, K. (2025) · SIAM Journal on Optimization · doi:10.1137/24m1672596 · Cited by 7
Parameter Identifiability and Optimal Experimental Design
August, E. (2009) · doi:10.1109/cse.2009.39 · Cited by 7
“On the other hand, testing positivity of a polynomial is NP-hard [25].”
BackgroundOn the geometric analysis of a quartic–quadratic optimization problem under a spherical constraint
Zhang, H., Milzarek, A., Wen, Z., & Yin, W. (2021) · Mathematical Programming · doi:10.1007/s10107-021-01702-6 · Cited by 10
A note on the convergence of an augmented Lagrangian algorithm to second-order stationary points
Andreani, R., & Secchin, L. D. (2018) · Proceeding Series of the Brazilian Society of Computational and Applied Mathematics · doi:10.5540/03.2018.006.01.0303 · Cited by 7
Dynamic and Static Enhanced BIRCH for Functional Data Clustering
Li, W., Li, H., & Luo, Y. (2023) · IEEE Access · doi:10.1109/access.2023.3322929 · Cited by 8
“Assuming x i = ( x i 1 , x i 2 , . . . , x iq ), if a cluster contains n samples and its centroid is denoted as x 0 , then it follows that cannot be rigorously proven [53].”
BackgroundSynthesizing Control Laws from Data using Sum-of-Squares Optimization
Bramburger, J. J., Dahdah, S., & Forbes, J. R. (2024) · IEEE Conference on Control Technology and Applications (CCTA) · doi:10.1109/ccta60707.2024.10666531 · Cited by 7
“Although these coefficients appear linearly in (2), tuning them to satisfy such a polynomial inequality is an NP-hard task in general [18].”
BackgroundConic approximation to quadratic optimization with linear complementarity constraints
Zhou, J., Fang, S., & Xing, W. (2016) · Computational Optimization and Applications · doi:10.1007/s10589-016-9855-8 · Cited by 7
“For example, when F is R n+, Murty and Kabadi [29] proved that this checking is co-NP-complete.”
BackgroundInfluentialSEA-PARAM: Exploring Schedulers in Parametric MDPs
Arming, S., Bartocci, E., & Sokolova, A. (2017) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.250.3 · Cited by 7
“Nevertheless, again, in general the computation of the score of a multivariate rational function is NP-hard [15, 26, 22].”
BackgroundResearch of NP-Complete Problems in the Class of Prefractal Graphs
Kochkarov, R. A. (2021) · Mathematics · doi:10.3390/math9212764 · Cited by 7
“In [3], a special class of indefinite quadratic programs with simple constraints and integer data was proposed.”
BackgroundMultiscale Semidefinite Programming Approach to Positioning Problems with Pairwise Structure
Chen, Y., Khoo, Y., & Lindsey, M. (2024) · Journal of Scientific Computing · doi:10.1007/s10915-024-02676-1 · Cited by 7
“In spite of the NP-hardness of optimizing general pairwise objectives [12], such an optimizer may avoid the pitfalls of local optimization and could be hoped to succeed on important practical problems.”
BackgroundDeciding positivity of multisymmetric polynomials
Görlach, P., Riener, C., & Weißer, T. (2015) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2015.10.001 · Cited by 7
Contribution of copositive formulations to the graph partitioning problem
Povh, J. (2011) · Optimization · doi:10.1080/02331934.2011.560385 · Cited by 7
“It is known that the decision problem ‘is given matrix copositive’ is co-NP-complete, hence it is not in NP unless co-NP ¼ NP [9,14].”
BackgroundApproachability in repeated games: Computational aspects and a Stackelberg variant
Mannor, S., & Tsitsiklis, J. N. (2008) · Games and Economic Behavior · doi:10.1016/j.geb.2008.03.008 · Cited by 7
“It is well known that solving a system of general quadratic inequalities is NP-hard (see Murty and Kabadi, 1987 ).”
BackgroundSum-of-Squares Proofs of Logarithmic Sobolev Inequalities on Finite Markov Chains
Faust, O., & Fawzi, H. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3338292 · Cited by 7
“Whilst it is generally NP-hard to decide whether a polynomial takes only nonnegative values on R n [18], there are efficient algorithms for solving SDPs to any desired precision using floating point arithmetic.”
MethodLiu, X., Pan, Z., & Tao, W. (2022) · Knowledge-Based Systems · doi:10.1016/j.knosys.2022.109277 · Cited by 14
“In general, it is NP-hard to obtain the global-optimal solution for handling non-convex problems [15].”
BackgroundLearning from Learning Machines: Optimisation, Rules, and Social NormsPreprint
LaCroix, T., & Bengio, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.00006 · Cited by 7
“…Convex optimisation problems are standard in computer science, and many classes of convex optimisation problems admit polynomial-time algorithms (Nesterov and Nemirovskii, 1994), though mathematical optimisation generally is NP-hard (Sahni, 1974; Murty and Kabadi, 1987; Pardalos and Vavasis, 1991).”
BackgroundConvex optimizationPreprint
Vorontsova, E., Hildebrand, R., Gasnikov, A. V., & Stonyakin, F. S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.01946 · Cited by 10
Learning preferences with multiple-criteria models
Sobrie, O. (2016) · theses.fr (ABES) · doi:10.70675/3fb9135fzb3e6z4bddz9995z98422d4ef215 · Cited by 15
“Testing the non-negativity of a polynomial of several variables and of a degree equal to or greater than 4 is NP-hard (Murty and Kabadi, 1987).”
BackgroundRobust threshold design for cooperative sensing in cognitive radio networks
Gong, S., Wang, P., & Huang, J. (2012) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2012.6195766 · Cited by 6
“However, the separation problem is proved to be NP-hard in [11].”
BackgroundThe Geometry of Equality-constrained Global Consensus Problems
Li, Q., Zhu, Z., Tang, G., & Wakin, M. B. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682568 · Cited by 8
Why Do Local Methods Solve Nonconvex Problems?
Ma, T. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108637435.027 · Cited by 14
“7 Notes Hillar and Lim [2013] show that a degree four polynomial is NP-hard to optimize and Murty and Kabadi [1987] show that it’s also NP-hard to check whether a point is not a local minimum.”
BackgroundSamala, T., Manupati, V. K., Nikhilesh, B. B. S., Varela, L., & Putnik, G. D. (2021) · Sustainability · doi:10.3390/su13095295 · Cited by 6
He, C., & Lu, Z. (2023) · SIAM Journal on Optimization · doi:10.1137/21m1457011 · Cited by 6
Nie, L., Wang, H., Feng, G., Sun, J., Lv, H., & Cui, H. (2023) · Journal of Cloud Computing Advances Systems and Applications · doi:10.1186/s13677-023-00503-w · Cited by 6
Black Holes and the loss landscape in machine learning
Kumar, P., Mandal, T., & Mondal, S. (2023) · Journal of High Energy Physics · doi:10.1007/jhep10(2023)107 · Cited by 6
“Finding a global minimum of a general non-convex function is hard [58, 59, 60], in fact NPhard [61], [62].”
BackgroundOn the hardness of deciding the finite convergence of Lasserre hierarchies
Vargas, L. F. (2024) · Numerical Algebra Control and Optimization · doi:10.3934/naco.2024024 · Cited by 6
Optimality and stability of symmetric evolutionary games with applications in genetic selection
Huang, Y., Hao, Y., Wang, M., Zhou, W. H., & Wu, Z. (2015) · Mathematical Biosciences & Engineering · doi:10.3934/mbe.2015.12.503 · Cited by 6
Interior-point algorithms for global optimization
Ye, Y. (1990) · Annals of Operations Research · doi:10.1007/bf02283687 · Cited by 6
“In one sense it is a continuous optimization and a fundamental subroutine for general nonlinear programming (see, for example, Gill and Murray [10]), but it is also considered one of the most challenging global optimization problems (see, for example, Garey and Johnson [8], Kalantari and Rosen [14], Murty and Kabadi […”
BackgroundAlgorithm for local input‐to‐state stability analysis
Qin, B., Zhang, X., Ma, J., & Mei, S. (2016) · IET Control Theory and Applications · doi:10.1049/iet-cta.2016.0007 · Cited by 6
Arahata, S., Okuno, T., & Takeda, A. (2023) · Computational Optimization and Applications · doi:10.1007/s10589-023-00501-3 · Cited by 6
Metadata
- Authors
- Murty, K. G., & Kabadi, S. N.
- Affiliations
- University of Michigan (US)
- University of New Brunswick (CA)
- Venue
- Mathematical Programming
- Published
- 1987-06
- Volume
- 39
- Issue
- 2
- Pages
- 117-129
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2079135578
- Cited by
- 1,003
- References
- 12
- Citations by year
- 2026: 17 · 2025: 21 · 2024: 32 · 2023: 42 · 2022: 51 · 2021: 79 · 2020: 66 · 2019: 68 · 2018: 62 · 2017: 55 · 2016: 55 · 2015: 38 · 2014: 42 · 2013: 47 · 2012: 27
- FWCI
- 7.23
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Mathematical Programming (publishedVersion)
- Topics
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- NP-completeness, nonconvex nonlinear programming, indefinite quadratic programming, computational complexity, copositive matrices, integer data
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.