Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/335097 
Erscheinungsjahr: 
2025
Quellenangabe: 
[Journal:] Journal of Global Optimization [ISSN:] 1573-2916 [Volume:] 93 [Issue:] 4 [Publisher:] Springer US [Place:] New York, NY [Year:] 2025 [Pages:] 1121-1144
Verlag: 
Springer US, New York, NY
Zusammenfassung: 
In this paper, we apply the Rank-Sparsity Matrix Decomposition to the planted Maximum Quasi-Clique Problem (MQCP). This problem has the planted Maximum Clique Problem (MCP) as a special case. The maximum clique problem is NP-hard. A Quasi-clique or γ-clique is a dense graph with the edge density of at least γ, γ∈(0,1]. The maximum quasi-clique problem seeks to find such a subgraph with the largest cardinality in a given graph. Our method of choice is the low-rank plus sparse matrix splitting technique. We present a theoretical basis for when our convex relaxation problem recovers the planted maximum quasi-clique. We have derived a new bound on the norm of the dual matrix that certifies the recovery using l∞,2norm. We have showed that when certain conditions are met, our convex formulation recovers the planted quasi-clique exactly. The numerical experiments we have performed corroborate our theoretical findings.
Schlagwörter: 
Quasi-clique
Adjacency matrix
Rank minimization
Nuclear norm
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.