MyJournals Home  

RSS FeedsEntropy, Vol. 21, Pages 108: Doubly Nonnegative and Semidefinite Relaxations for the Densest k-Subgraph Problem (Entropy)

 
 

24 january 2019 13:00:16

 
Entropy, Vol. 21, Pages 108: Doubly Nonnegative and Semidefinite Relaxations for the Densest k-Subgraph Problem (Entropy)
 




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’ 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.


Del.icio.us Digg Facebook Google StumbleUpon Twitter
 
38 viewsCategory: Informatics, Physics
 
Entropy, Vol. 21, Pages 109: Quasi-Concavity for Gaussian Multicast Relay Channels (Entropy)
Entropy, Vol. 21, Pages 107: An Analysis of Entropy-Based Eye Movement Events Detection (Entropy)
 
 
blog comments powered by Disqus


MyJournals.org
The latest issues of all your favorite science journals on one page

Username:
Password:

Register | Retrieve

Search:

Physics

Use these buttons to bookmark us:
Del.icio.us Digg Facebook Google StumbleUpon Twitter


Valid HTML 4.01 Transitional
Copyright © 2008 - 2019 Indigonet Services B.V.. Contact: Tim Hulsen. Read here our privacy notice.
Other websites of Indigonet Services B.V.: Nieuws Vacatures News Tweets Travel Photos Nachrichten Indigonet Finances Leer Mandarijn