Given a graph @math , a non-negative integer @math , and a weight function that maps each vertex in @math to a positive real number, the is about finding a maximum weighted independent set in @math of cardinality at most @math . A special case of MWBIS, when the weight assigned to each vertex is equal to its degree in @math , is called the problem. In other words, the MIVC problem is about finding an independent set of cardinality at most @math with maximum coverage. Since it is a generalization of the well-known Maximum Weighted Independent Set (MWIS) problem, MWBIS too does not have any constant factor polynomial time approximation algorithm assuming @math . In this paper, we study MWBIS in the context of bipartite graphs. We show that, unlike MWIS, the MIVC (and thereby the MWBIS) problem in bipartite graphs is NP-hard. Then, we show that the MWBIS problem admits a @math -factor approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation.
 Graphs are often used to model risk management in various systems. Particularly, in [6] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. It is well-known that the vertex cover problem is in P on bipartite graphs; however, the computational complexity of the partial vertex cover problem on bipartite graphs is open. In this paper, we show that the partial vertex cover problem is NP-hard on bipartite graphs. Then, we show that the budgeted maximum coverage problem (a problem related to partial vertex cover problem) admits an ( 8 9 )-approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation. Linear programming relaxations have been used extensively in designing approximation algorithms for optimization problems. For vertex cover, linear programming and a thresholding technique gives a 2-approximate solution, rivaling the best known performance ratio. For a generalization of vertex cover we call vc t, in which we seek to cover t edges, this technique may not yield a feasible solution at all. We introduce a new method for massaging a linear programming solution to get a good, feasible solution for vc t. Our technique manipulates the values of the linear programming solution to prepare them for thresholding. We prove that this method achieves a performance ratio of 2 for vc t with unit weights. A second algorithm extends this result, giving a 2-approximation for vc t with arbitrary weights. We show that this is tight in the sense that any α-approximation algorithm for vc t with α < 2 implies a breakthrough α-approximation algorithm for vertex cover. In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold ??, our objective is to find a subset of the vertices with minimum total cost, such that at least a length of ?? of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|2+|H|)-time, ?E-approximation algorithm for this problem, where ?E?2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where ?E=2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|2), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.