We study two related problems: finding a set of k vertices and minimum number of edges (kmin) and finding a graph with at least m' edges and minimum number of vertices (mvms). Goldschmidt and Hochbaum GH97 show that the mvms problem is NP-hard and they give a 3-approximation algorithm for the problem. We improve GH97 by giving a ratio of 2. A 2(1+ )-approximation for the problem follows from the work of Carnes and Shmoys CS08 . We improve the approximation ratio to 2. algorithm for the problem. We show that the natural LP for has an integrality gap of 2-o(1). We improve the NP-completeness of GH97 by proving the pronlem are APX-hard unless a well-known instance of the dense k-subgraph admits a constant ratio. The best approximation guarantee known for this instance of dense k-subgraph is O(n^ 2 9 ) BCCFV . We show that for any constant >1, an approximation guarantee of for the problem implies a (1+o(1)) approximation for . Finally, we define we give an exact algorithm for the density version of kmin.
Consider an objective function in which we minimize @math . One can associate a cost @math with each vertex @math and a size @math for each vertex @math , and then the objective is just to minimize @math subject to @math . Carnes and Shmoys @cite_9 give a @math -approximation for the problem. Using this result and the observation that the objective function is at most a factor of @math away from the objective function for the problem, a @math -approximation follows for the problem.
@cite_9
1964001041
Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achieve the same performance guarantees as the LP-rounding algorithms of which rely on applying the ellipsoid algorithm to an exponentially-sized LP. Furthermore, we introduce new flow-cover inequalities to strengthen the LP relaxation of the more general capacitated single-item lot-sizing problem; using just these inequalities as the LP relaxation, we obtain a primal-dual algorithm that achieves a performance guarantee of 2. Computational experiments demonstrate the effectiveness of this algorithm on generated problem instances.