Fetching the paper…
Reading the bibliography…
We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems.
Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Research Logistics Quarterly 3
1956
Earlier work this paper cites.
Khachiyan, L.: Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics 20
1980
Earlier work this paper cites.
Andronov, V., Belousov, E., V.M., S.: On solvability of the problem of polynomial programming (in russian). Izvestija Akadem. Nauk SSSR, Tekhnicheskaja Kibernetika. Translation appeared in News of the Academy of Science of USSR, Dept. of Technical Sciences, Technical Cybernetics. 4
1982
Earlier work this paper cites.
Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4
1984
Earlier work this paper cites.
Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA (1986)
1986
Earlier work this paper cites.
Karmarkar, N.: An interior-point approach to NP-complete problems (1989), manuscript
1989
Earlier work this paper cites.
Vavasis, S., Zippel, R.: Proving polynomial-time for sphere-constrained quadratic programming. Tech. rep., Tech. Report 90-1182, Department of Computer Science, Cornell University (1990)
1990
Earlier work this paper cites.
Vavasis, S.A.: Quadratic programming is in NP. Information Processing Letters 36
1990
Earlier work this paper cites.
Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. Journal of Global Optimization 1
1991
Earlier work this paper cites.
Renegar, J.: On the Computational Complexity and Geometry of the First-order Theory of the Reals. Part I: Introduction. Preliminaries. The Geometry of Semi-algebraic Sets. The decision Problem for the Existential Theory of the Reals. Journal of Symbolic Computation 13
1992
Earlier work this paper cites.
Renegar, J.: On the computational complexity of approximating solutions for real algebraic formulae. SIAM Journal on Computing 21
1992
Earlier work this paper cites.
1992
Earlier work this paper cites.
Barvinok, A.: Feasibility testing for systems of real quadratic equations. Disc. Comput. Geometry 10
1993
Cited alongside, same era.
Belousov, E., Andronov, V.: Solvability and stability of problems of polynomial programming (in russian). Tech. rep., Moscow University Publ., Moscow (1993)
1993
Cited alongside, same era.
Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization 5
1995
Cited alongside, same era.
Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific (1997)
1997
Cited alongside, same era.
Ramana, M.: An exact duality theory for semidefinite programming and its complexity implications. Mathematical Programming 77
1997
Cited alongside, same era.
Heubach, S., Mansour, T.: Combinatorics of Compositions and Words. Discrete Mathematics and Its Applications, CRC Press (2009)
2009
Later among the works it cites.
Albu, T.: The irrationality of sums of radicals via cogalois theory. Analele stiintifice ale Universitatii Ovidius Constanta 19(2)
2011
Later among the works it cites.
De Loera, J.A., Lee, J., Malkin, P.N., Margulies, S.: Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz. Journal of Symbolic Computation 46
2011
Later among the works it cites.
Waki, H., Nakata, M., Muramatsu, M.: Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization. Comput. Optim. Appl. 53
2012
Later among the works it cites.
Geronimo, G., Perrucci, D., Tsigaridas, E.: On the minimum of a polynomial function on a basic closed semialgebraic set and applications. SIAM Journal on Optimization 23
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Renegar, J.: Recent progress on the complexity of the decision problem for the reals. In: Caviness, B.F., Johnson, J.R. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition. pp. 220–241. Springer Vienna, Vienna (1998)
1998
Cited alongside, same era.
Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation. Applicable Algebra in Engineering, Communication and Computing 9
1999
Cited alongside, same era.
Grigoriev, D., Vorobjov, N.: Complexity of Null- and Positivstellensatz proofs. Annals of Pure and Applied Logic 113
2001
Cited alongside, same era.
Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry. Springer Berlin Heidelberg (2006). https://doi.org/10.1007/3-540-33099-2, https://doi.org/10.1007/3-540-33099-2
2006
Cited alongside, same era.
Byrd, R.H., Nocedal, J., Waltz, R.A.: KNITRO: An integrated package for nonlinear optimization. In: di Pillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization, pp. 35–59. Springer (2006)
2006
Cited alongside, same era.
Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Mathematical Programming 106
2006
Cited alongside, same era.
Hochbaum, D.S.: Complexity and algorithms for nonlinear optimization problems. Annals of Operations Research 153
2007
Cited alongside, same era.
2013
Later among the works it cites.
Basu, S.: Algorithms in real algebraic geometry: A survey (2014)
2014
Later among the works it cites.
Bienstock, D.: A note on polynomial solvability of the CDT problem. SIAM J. Optimization 26
2016
Later among the works it cites.
Del Pia, A., Dey, S.S., Molinaro, M.: Mixed-integer quadratic programming is in NP. Mathematical Programming 162
2016
Later among the works it cites.
O’Donnell, R.: SOS Is Not Obviously Automatizable, Even Approximately. In: Papadimitriou, C.H. (ed.) 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), vol. 67, pp. 59:1–59:10. Dagstuhl, Germany (2017). https://doi.org/10.4230/LIPIcs.ITCS.2017.59, http://drops.dagstuhl.de/opus/volltexte/2017/8198
2017
Later among the works it cites.
Letchford, A., Parkes, A.J.: A guide to conic optimisation and its applications. RAIRO-Oper. Res. pp. 1087–1106 (2018)
2018
Later among the works it cites.
Klatte, D.: On a Frank-Wolfe type theorem in cubic optimization. Optimization 68
2019
Later among the works it cites.
Pataki, G., Touzov, A.: How do exponential size solutions arise in semidefinite programming? (2021)
2021
Closest in time.