{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T05:24:45Z","timestamp":1786166685953,"version":"3.56.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,12,18]],"date-time":"2007-12-18T00:00:00Z","timestamp":1197936000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["cent.eur.j.oper.res."],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s10100-007-0052-9","type":"journal-article","created":{"date-parts":[[2007,12,17]],"date-time":"2007-12-17T09:42:28Z","timestamp":1197884548000},"page":"111-125","source":"Crossref","is-referenced-by-count":65,"title":["The complexity of optimizing over a simplex, hypercube or sphere: a short survey"],"prefix":"10.1007","volume":"16","author":[{"given":"Etienne","family":"de Klerk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,12,18]]},"reference":[{"key":"52_CR1","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"G Ausiello","year":"1980","unstructured":"Ausiello G, D\u2019Atri A and Protasi M (1980). Structure preserving reductions among convex optimization problems. J Comput Syst Sci 21: 136\u2013153","journal-title":"J Comput Syst Sci"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Barvinok (2007) A integration and optimization of multivariate polynomials by restriction onto a random subspace. Found Comput Math (to appear)","DOI":"10.1007\/s10208-005-0178-x"},{"key":"52_CR3","first-page":"429","volume":"69","author":"M Bellare","year":"1995","unstructured":"Bellare M and Rogaway P (1995). The complexity of approximating a nonlinear program. Math Program 69: 429\u2013441","journal-title":"Math Program"},{"issue":"1","key":"52_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"Blum L, Shub M and Smale S (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull Am Math Soc (NS) 21(1): 1\u201346","journal-title":"Bull Am Math Soc (NS)"},{"issue":"3","key":"52_CR5","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/S00361445003756","volume":"44","author":"IM Bomze","year":"2002","unstructured":"Bomze IM (2002). Regularity versus degeneracy in dynamics, games and optimization: a unified approach to different aspects. SIAM Rev 44(3): 394\u2013414","journal-title":"SIAM Rev"},{"issue":"2","key":"52_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/A:1020209017701","volume":"24","author":"I Bomze","year":"2002","unstructured":"Bomze I and De Klerk E (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J Glob Optim 24(2): 163\u2013185","journal-title":"J Glob Optim"},{"key":"52_CR7","unstructured":"Burer S (2006) On the copositive representation of binary and continuous nonconvex quadratic programs. Manuscript. http:\/\/dollar.biz.uiowa.edu\/~burer\/papers\/021-copos.pdf"},{"key":"52_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-1-4613-0251-3_6","volume-title":"Frontiers in global optimization","author":"L Faybusovich","year":"2004","unstructured":"Faybusovich L (2004). Global optimization of homogeneous polynomials on the simplex and on the sphere. In: Floudas, C and Pardalos, P (eds) Frontiers in global optimization, pp 109\u2013121. Kluwer, Dordrecht"},{"key":"52_CR9","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR and Johnson DS (1979). Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, Publishers, San Fransisco"},{"issue":"6","key":"52_CR10","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX and Williamson DP (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6): 1115\u20131145","journal-title":"J ACM"},{"key":"52_CR11","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J (1999). Clique is hard to approximate within |V 1-\u03b5 |. Acta Math 182: 105\u2013142","journal-title":"Acta Math"},{"key":"52_CR12","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J (2001). Some optimal inapproximability results. J ACM 48: 798\u2013859","journal-title":"J ACM"},{"issue":"2","key":"52_CR13","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/S003614299630587X","volume":"35","author":"JS Hesthaven","year":"1998","unstructured":"Hesthaven JS (1998). From electrostatics to almost optimal nodal sets for polynomial interpolation in a simplex. SIAM J Numer Anal 35(2): 655\u2013676","journal-title":"SIAM J Numer Anal"},{"key":"52_CR14","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jco.2005.06.006","volume":"22","author":"M Horn","year":"2006","unstructured":"Horn M (2006). Optimal algorithms for global optimization in case of unknown Lipschitz constant. J Complex 22: 50\u201370","journal-title":"J Complex"},{"key":"52_CR15","first-page":"191","volume":"20","author":"L Khachiyan","year":"1979","unstructured":"Khachiyan L (1979). A polynomial time algorithm in linear programming. Sov Math Dokl 20: 191\u2013194","journal-title":"Sov Math Dokl"},{"key":"52_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/S0895480104442741","volume":"20","author":"E Klerk de","year":"2006","unstructured":"Maharry J, Pasechnik DV, Richter B and Salazar G (2006). Improved bounds for the crossing numbers of K m,n and K n . SIAM J Discrete Math 20: 189\u2013202","journal-title":"SIAM J Discrete Math"},{"key":"52_CR17","doi-asserted-by":"crossref","unstructured":"de Klerk E, den Hertog D, Elabwabi G (2007a) On the complexity of optimization over the standard simplex. Eur J Oper Res (to appear)","DOI":"10.1016\/j.ejor.2007.01.055"},{"key":"52_CR18","unstructured":"de Klerk E, Laurent M, Parrilo P (2007b) A PTAS for the minimization of polynomials of fixed degree over the simplex. Theor Comput Sci (to appear)"},{"key":"52_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani R and Raghavan P (1995). Randomized algorithms. Cambridge University Press, Cambridge"},{"key":"52_CR20","doi-asserted-by":"crossref","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"TS Motzkin","year":"1965","unstructured":"Motzkin TS and Straus EG (1965). Maxima for graphs and a new proof of a theorem of T\u00faran. Can J Math 17: 533\u2013540","journal-title":"Can J Math"},{"key":"52_CR21","volume-title":"Problem complexity and method efficiency in optimization","author":"AS Nemirovsky","year":"1983","unstructured":"Nemirovsky AS and Yudin DB (1983). Problem complexity and method efficiency in optimization. Wiley\u2013Interscience, New York"},{"key":"52_CR22","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1080\/10556789808805690","volume":"9","author":"Y Nesterov","year":"1998","unstructured":"Nesterov Y (1998). Semidefinite relaxation and nonconvex quadratic optimization. Optim Methods Softw 9: 141\u2013160","journal-title":"Optim Methods Softw"},{"key":"52_CR23","unstructured":"Nesterov Y (2003) Random walk in a simplex and quadratic optimization over convex polytopes. CORE Discussion Paper 2003\/71, CORE-UCL"},{"key":"52_CR24","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/978-1-4615-4381-7_13","volume-title":"Handbook of semidefinite programming","author":"Y Nesterov","year":"2000","unstructured":"Nesterov Y, Wolkowicz H and Ye Y (2000). Semidefinite programming relaxations of nonconvex quadratic optimization. In: Wolkowicz, H, Saigal, R, and Vandenberghe, L (eds) Handbook of semidefinite programming, pp 361\u2013419. Kluwer, Norwell"},{"key":"52_CR25","doi-asserted-by":"crossref","unstructured":"Novak E (1988) Deterministic and stochastic error bounds in numerical analysis. In: Lecture Notes in Mathematics, vol. 1349. Springer, Heidelberg","DOI":"10.1007\/BFb0079792"},{"key":"52_CR26","unstructured":"Parrilo PA (2000) Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization. PhD Thesis, California Institute of Technology, Pasadena, California, USA. Available at: http:\/\/www.cds.caltech.edu\/~pablo\/"},{"key":"52_CR27","doi-asserted-by":"crossref","unstructured":"P\u00f3lik I, Terlaky T (2007) A survey of the S-lemma. SIAM Rev (to appear)","DOI":"10.1137\/S003614450444614X"},{"key":"52_CR28","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1023\/A:1021798932766","volume":"99","author":"BT Polyak","year":"1998","unstructured":"Polyak BT (1998). Convexity of quadratic transformations and its use in control and optimization. J Optim Theory Appl 99: 553\u2013583","journal-title":"J Optim Theory Appl"},{"issue":"2","key":"52_CR29","first-page":"129","volume":"77","author":"M Ramana","year":"1997","unstructured":"Ramana M (1997). An exact duality theory for semidefinite programming and its complexity implications. Math Program Ser B 77(2): 129\u2013162","journal-title":"Math Program Ser B"},{"key":"52_CR30","volume-title":"Infomation-based complexity","author":"JF Traub","year":"1988","unstructured":"Traub JF, Wasilkowski GW and Wo\u017aniakowski H (1988). Infomation-based complexity. Academic Press, Inc., New York"},{"key":"52_CR31","volume-title":"Nonlinear optimization: complexity issues","author":"SA Vavasis","year":"1991","unstructured":"Vavasis SA (1991). Nonlinear optimization: complexity issues. Oxford University Press, New York"},{"key":"52_CR32","first-page":"3","volume-title":"Recent advances in global optimization","author":"SA Vavasis","year":"1992","unstructured":"Vavasis SA (1992). Approximation algorithms for concave quadratic programming. In: Floudas, CA and Pardalos, P (eds) Recent advances in global optimization, pp 3\u201318. Princeton University Press, New Jersey"},{"key":"52_CR33","volume-title":"Computable analysis","author":"K Weirauch","year":"1998","unstructured":"Weirauch K (1998). Computable analysis. Springer, Heidelberg"},{"key":"52_CR34","unstructured":"Yakubovich VA (1973) The S-procedure and duality theorems for nonconvex problems of quadratic programming, vol. 1. Vestnik Leningrad. University, pp 81\u201387"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-007-0052-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10100-007-0052-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-007-0052-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-007-0052-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T00:31:02Z","timestamp":1557102662000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10100-007-0052-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,18]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["52"],"URL":"https:\/\/doi.org\/10.1007\/s10100-007-0052-9","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"value":"1435-246X","type":"print"},{"value":"1613-9178","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,18]]}}}