We consider two optimization problems related to finding dense subgraphs. The densest at-least-k-subgraph problem (DalkS) is to find an induced subgraph of highest average degree among all subgraphs with at least k vertices, and the densest at-most-k-subgraph problem (DamkS) is defined similarly. These problems are related to the well-known densest k-subgraph problem (DkS), which is to find the densest subgraph on exactly k vertices. We show that DalkS can be approximated efficiently, while DamkS is nearly as hard to approximate as the densest k-subgraph problem.
We will briefly survey a few results on the complexity of the densest @math -subgraph problem. The best approximation algorithm known for the general problem (when @math is specified as part of the input) is the algorithm of Feige, Peleg, and Kortsarz @cite_7 , which has ratio @math for some @math . For any particular value of @math , the greedy algorithm of @cite_10 gives the ratio @math . Algorithms based on linear programming and semidefinite programming have produced approximation ratios better than @math for certain values of @math , but have not improved the approximation ratio of @math for the general case @cite_9 @cite_1 .
@cite_1 @cite_9 @cite_10 @cite_7
2034543148 2010787744 2032279394 2036836182
The little Grothendieck problem consists of maximizing @math ijCijxixj for a positive semidefinite matrix C, over binary variables @math xi ?1 . In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given @math CRdn?dn a positive semidefinite matrix, the objective is to maximize @math ijtrCijTOiOjT restricting @math Oi to take values in the group of orthogonal matrices @math Od, where @math Cij denotes the (ij)-th @math d?d block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices @math Od and show a constant approximation ratio. Our method is based on semidefinite programming. For a given @math d1, we show a constant approximation ratio of @math R(d)2, where @math R(d) is the expected average singular value of a @math d?d matrix with random Gaussian @math N0,1d i.i.d. entries. For @math d=1 we recover the known @math R(1)2=2  approximation guarantee for the classical little Grothendieck problem. Our algorithm and analysis naturally extends to the complex valued case also providing a constant approximation ratio for the analogous little Grothendieck problem over the Unitary Group @math Ud. Orthogonal-Cut also serves as an approximation algorithm for several applications, including the Procrustes problem where it improves over the best previously known approximation ratio of @math 122. The little Grothendieck problem falls under the larger class of problems approximated by a recent algorithm proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were @math for both directed and undirected graphs, and @math for undirected graphs with @math , where @math is the number of nodes in the input graph. Our first algorithm has approximation ratio @math , which is @math except for very large values of @math , namely, @math . This algorithm is based on a new result on @math -connected @math -critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio @math for all values of @math . Combining these two gives an algorithm with approximation ratio @math , which asymptotically improves the best known approximation guarantee for directed graphs for all values of @math , and for undirected graphs for @math . Moreover, this is the first algorithm that has an approximation guarantee better than @math for all values of @math . Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation. We present the best known algorithms for approximating the minimum-size undirected @math -edge connected spanning subgraph. For simple graphs our approximation ratio is @math . The more precise version of this bound requires @math , and for all such @math it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], @math . The improvement comes in two steps. First we show that for simple @math -edge connected graphs, any laminar family of degree @math sets is smaller than the general bound ( @math versus @math ). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is @math . This improves the previous ratio @math [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant @math , an approximation ratio @math implies @math . Our approximation ratio extends to the minimum-size Steiner network problem, where @math denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. We obtain improved algorithms for finding small vertex covers in bounded degree graphs and hypergraphs. We use semidefinite programming to relax the problems and introduce new rounding techniques for these relaxations. On graphs with maximum degree at most @math , the algorithm achieves a performance ratio of @math for large @math , which improves the previously known ratio of @math obtained by Halld orsson and Radhakrishnan. Using similar techniques, we also present improved approximations for the vertex cover problem in hypergraphs. For k-uniform hypergraphs with n vertices, we achieve a ratio of @math for large n, and for k-uniform hypergraphs with maximum degree at most @math the algorithm achieves a ratio of @math for large @math . These results considerably improve the previous best ratio of @math for bounded degree k-uniform hypergraphs, and @math for general k-uniform hypergraphs, both obtained by Krivelevich. Using similar techniques, we also obtain an approximation algorithm for the weighted independent set problem, matching a recent result of Halldorsson.