{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:50Z","timestamp":1787337530275,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2013-T2-2-168"],"award-info":[{"award-number":["MOE2013-T2-2-168"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007040","name":"Singapore University of Technology and Design","doi-asserted-by":"publisher","award":["IDG31300105"],"award-info":[{"award-number":["IDG31300105"]}],"id":[{"id":"10.13039\/501100007040","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.<\/jats:p>","DOI":"10.1137\/16m109778x","type":"journal-article","created":{"date-parts":[[2018,3,13]],"date-time":"2018-03-13T10:45:50Z","timestamp":1520937950000},"page":"671-692","source":"Crossref","is-referenced-by-count":2,"title":["Bounds for Random Binary Quadratic Programs"],"prefix":"10.1137","volume":"28","author":[{"given":"Karthik","family":"Natarajan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongjian","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kim-Chuan","family":"Toh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1015"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1080\/00207729408928968"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.3.493"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"atypb5","unstructured":"J. E. Beasley,\n                      Heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem\n                      , working paper, The Management School, Imperial College, London, 1998."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403430610"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0710-z"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"J. R. Birge and F. Louveaux,\n                      Introduction to Stochastic Programming\n                      , Springer Ser. Oper. Res. Financ. Eng., 2nd ed., Springer, New York, 2011.","DOI":"10.1007\/978-1-4614-0237-4"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.5.838"},{"key":"atypb10","unstructured":"S. Boyd, L. Xiao, and A. Mutapcic,\n                      Subgradient Methods\n                      , lecture notes for EE392o, Stanford University, Stanford, CA, 2003-2004."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90037-X"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90111-2"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/130915315"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.1.100"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90058-7"},{"key":"atypb16","first-page":"132","author":"Gallo G.","year":"1980","journal-title":"Heidelberg"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/100802190"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.3.336"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"atypb20","first-page":"95","author":"Grant M. C.","year":"2008","journal-title":"London"},{"key":"atypb21","unstructured":"M. Grant and S. Boyd,\n                      CVX: Matlab Software for Disciplined Convex Programming, version 2.0 beta\n                      ,http:\/\/cvxr.com\/cvx, September 2013."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180206"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580072"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582072"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1080\/10556780108805819"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1080\/02331938808843386"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.12.014"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.3.454"},{"key":"atypb29","unstructured":"A. J. McNeil, R. Frey, and P. Embrechts,\n                      Quantitative Risk Management: Concepts, Techniques and Tools\n                      , Princeton University Press, Princeton, NJ, 2005."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.2307\/3213097"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02247879"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230050405"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01100205"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1287\/moor.16.2.223"},{"key":"atypb35","first-page":"1","author":"Rother C.","year":"2007","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition"},{"key":"atypb36","unstructured":"H. Scarf,\n                      A min-max solution of an inventory problem\n                      , in Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, Redwood City, CA, 1958, pp. 201-209."},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"A. Shapiro, D. Dentcheva, and A. Ruszczyn\u0301ski,\n                      Lectures on Stochastic Programming: Modeling and Theory\n                      , MOS-SIAM Ser. Optim. 9, SIAM, Philadelphia, 2009,https:\/\/doi.org\/10.1137\/1.9780898718751.","DOI":"10.1137\/1.9780898718751"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070233"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1080\/02331939508844086"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0347-5"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.4.595"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M109778X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:45Z","timestamp":1787336145000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M109778X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M109778X"],"URL":"https:\/\/doi.org\/10.1137\/16m109778x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}