"In the Partial Vertex Cover (PVC) problem we are given an undirected graph G = (V, E), a positive cost associated with each vertex and a positive integer k and the goal is to find a minimum cost subset of vertices S such that atleast k edges of the graph are covered. In this paper we consider two new generalization of the PVC problem. In the first variation which we call Partition Vertex Cover (Partition-VC) problem, the edges of the graph G are divided into n disjoint partitions $P_1, P_2... P_n$ and we have to select a minimum cost subset of vertices S such that atleast $k_i$ edges are covered from partition $P_i$. In the second variation which we call Knapsack Partition Vertex Cover (KPVC) problem, in addition to the previous conditions, each edge e has a profit $pi_{e}$ associated with it and we have an added knapsack constraint that the total profit of the covered edges in partition $P_i$ should be atleast $Pi_i$. We give an $O(log n)$ approximation for both the problems using a combination of deterministic rounding and randomized rounding approach that operates on the LP strengthened by adding Knapsack Cover inequalities as proposed by Carr, Fleischer, Leung & Phillips. We also show that these bounds can not be further improved by reducing the set cover problem to the Partition-VC problem in polynomial time. We also give an $O(f)$ approximation for the Partition-VC problem using a primal dual schema where f is the maximum number of edges in any partition."

"using the partitioning algorithm of this paper, we have designed a nearly-linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly-linear time algorithm for solving linear systems in symmetric, diagonally-dominant matrices."