Mixed-integer quadratic programming is in NP
By Alberto Del Pia, Santanu S. Dey, Marco S. Molinaro. 2014
150 citations recorded by the source corpus.
Mixed-integer quadratic programming is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generalizes and unifies classical results that quadratic programming is in NP (Vavasis in Inf Process Lett 36(2):73–77 [17]) and integer linear programming is in NP (Borosh and Treybig in Proc Am Math Soc 55:299–304 [1], von zur Gathen and Sieveking in Proc Am Math Soc 72:155–158 [18], Kannan and Monma in Lecture Notes in Economics and Mathematical Systems, vol. 157, pp. 161–172. Springer [9], Papadimitriou in J Assoc Comput Mach 28:765–768 [15]).
Subfields: Computational Theory and Mathematics, Numerical Analysis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Numerical Analysis
Citations in the corpus
- Adaptive Task Allocation for Asynchronous Federated Mobile Edge Learning (2019, background): “In our case, this will translate into a max-constrained optimization and our problem is already NP-hard.”
- Adaptive Task Allocation for Mobile Edge Learning (2018, background): “Being an NP-hard problem, the paper relaxes it to a non-convex problem over real variables.”
- Task Allocation for Mobile Federated and Offloaded Learning with Energy and Delay Constraints (2020, background): “Due to integer decision variables, the problem of interest in this paper is NP-hard as shown in section II.”