{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:32:16Z","timestamp":1760239936091,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T00:00:00Z","timestamp":1548288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The densest k-subgraph (DkS) maximization problem is to find a set of k vertices with maximum total weight of edges in the subgraph induced by this set. This problem is in general NP-hard. In this paper, two relaxation methods for solving the DkS problem are presented. One is doubly nonnegative relaxation, and the other is semidefinite relaxation with tighter relaxation compare with the relaxation of standard semidefinite. The two relaxation problems are equivalent under the suitable conditions. Moreover, the corresponding approximation ratios\u2019 results are given for these relaxation problems. Finally, some numerical examples are tested to show the comparison of these relaxation problems, and the numerical results show that the doubly nonnegative relaxation is more promising than the semidefinite relaxation for solving some DkS problems.<\/jats:p>","DOI":"10.3390\/e21020108","type":"journal-article","created":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T11:12:48Z","timestamp":1548328368000},"page":"108","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Doubly Nonnegative and Semidefinite Relaxations for the Densest k-Subgraph Problem"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2205-6158","authenticated-orcid":false,"given":"Chuan-Hao","family":"Guo","sequence":"first","affiliation":[{"name":"School of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, China"}]},{"given":"Yuan","family":"Guo","sequence":"additional","affiliation":[{"name":"School of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, China"}]},{"given":"Bei-Bei","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,1,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/s004530010050","article-title":"The Dense k-Subgraph Problem1","volume":"29","author":"Feige","year":"2001","journal-title":"Algorithmica"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1504\/IJOR.2008.017534","article-title":"A deterministic approximation algorithm for the densest k-subgraph problem","volume":"3","author":"Roupin","year":"2008","journal-title":"Int. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","article-title":"Clustering and domination in perfect graphs","volume":"9","author":"Corneil","year":"1984","journal-title":"Discret. Appl. Math."},{"key":"ref_4","first-page":"155","article-title":"The complexity of clustering in planar graphs","volume":"9","author":"Keil","year":"1991","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1380","DOI":"10.1016\/j.cor.2004.09.033","article-title":"Upper bounds and exact algorithms for dispersion problems","volume":"33","author":"Pisinger","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_6","unstructured":"Goldstein, D., and Langberg, M. (arXiv, 2009). The dense k-subgraph problem, arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/j.ipl.2010.05.011","article-title":"Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs","volume":"110","author":"Backer","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., and Vijayaraghavan, A. (2010, January 6\u20138). Detecting high log-densities: An O (n 1\/4) approximation for densest k-subgraph. Proceedings of the 42nd ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/1806689.1806719"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.ipl.2008.03.016","article-title":"A constant approximation algorithm for the densest k-subgraph problem on chordal graphs","volume":"108","author":"Liazi","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01100205","article-title":"A recipe for semidefinite relaxation for (0, 1)-quadratic programming","volume":"7","author":"Poljak","year":"1995","journal-title":"J. Glob. Optim."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1109\/78.992139","article-title":"Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous CDMA","volume":"50","author":"Ma","year":"2002","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1038","DOI":"10.1109\/JSTSP.2009.2035798","article-title":"The equivalence of semidefinite relaxation MIMO detectors for higher-order QAM","volume":"3","author":"Ma","year":"2009","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0012-365X(92)00057-X","article-title":"Stable sets and polynomials","volume":"124","author":"Lovasz","year":"1994","journal-title":"Discret. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s10107-008-0223-z","article-title":"On the copositive representation of binary and continuous nonconvex quadratic programs","volume":"120","author":"Burer","year":"2009","journal-title":"Math. Program"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"543","DOI":"10.3934\/jimo.2014.10.543","article-title":"Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems","volume":"10","author":"Bai","year":"2014","journal-title":"J. Ind. Manag. Optim."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s12532-010-0010-8","article-title":"Optimizing a polyhedral-semidefinite relaxation of completely positive programs","volume":"2","author":"Burer","year":"2010","journal-title":"Math. Program Comput."},{"key":"ref_18","first-page":"161","article-title":"Lagrangian-Conic relaxations, part I: A unified framework and its applications to quadratic optimization problems","volume":"14","author":"Arima","year":"2018","journal-title":"Pac. J. Optim."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.ejor.2011.04.026","article-title":"Copositive optimization-Recent developments and applications","volume":"216","author":"Bomze","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","article-title":"Quadratic programming with one negative eigenvalue is NP-hard","volume":"1","author":"Pardalos","year":"1991","journal-title":"J. Glob. Optim."},{"key":"ref_21","unstructured":"Dickinson, P., and Gijben, L. (2011). On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual, University of Groningen."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Diananda, P. (1962). On non-negative forms in real variables some or all of which are non-negative. Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press.","DOI":"10.1017\/S0305004100036185"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Berman, A., and Shaked-Monderer, N. (2003). Completely Positive Matrices, World Scientific.","DOI":"10.1142\/9789812795212"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Boyd, S., and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"ref_25","unstructured":"Ge, D., and Ye, Y. (2010, August 17). On Doubly Positive Semidefinite Programming Relaxations. Available online: http:\/\/www.optimization-online.org\/DB_HTML\/2010\/08\/2709.pdf."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1109\/MSP.2010.936019","article-title":"Semidefinite relaxation of quadratic optimization problems","volume":"27","author":"Luo","year":"2010","journal-title":"Signal Proc. Mag. IEEE"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1137\/070679041","article-title":"Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization","volume":"19","author":"He","year":"2008","journal-title":"SIAM J. Optim."},{"key":"ref_28","unstructured":"Grant, M., and Boyd, S. (2010, April 15). CVX: Matlab Software for Disciplined Convex Programming, Version 1.21. Available online: http:\/\/cvxr.com\/cvx."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","article-title":"Benchmarking optimization software with performance profiles","volume":"91","author":"Dolan","year":"2002","journal-title":"Math. Program."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s10288-012-0210-3","article-title":"Semidefinite relaxations for partitioning, assignment and ordering problems","volume":"10","author":"Rendl","year":"2012","journal-title":"Q. J. Oper. Res."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/2\/108\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:28:24Z","timestamp":1760185704000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/21\/2\/108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,24]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,2]]}},"alternative-id":["e21020108"],"URL":"https:\/\/doi.org\/10.3390\/e21020108","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2019,1,24]]}}}