Finding sets that do not intersect. Approximation algorithm I am trying to solve the following problem. Let $S$ be a set and $F \subset {S \choose k}$  that is $F$ is a subset of the set of all $k$-sets of $S$.
A set  $M \subset F$ such that no two elements of $M$ intersect is called a solution for the problem.
I am looking for an algorithm $A$ that finds a solution to the above problem such that if the given solution is a set $M$ and the largest set that is a solution for the same instance is $M^*$ then
$$\frac{|M|}{|M^*|} \geq \frac1{k}\qquad (1) $$
The only algorithm I can see for the above problem is to pick an element $P$ from $F$, remove all the elements in $F$ that intersect with $P$ and continue.
However I am not able to analyze the above procedure to obtain the given bound (if even attainable).
Any hints on this problem?
 A: This problem is usually called the unweighted set-packing problem. As a side-note, this problem is NP-complete; in fact, as I came to know only today (thanks, OP!), it is one of Karp's gang of 21! 
Here's a simple proof that the heuristic sketched in the question gives a set $M$ that is at most a factor $k$ from the optimum, call this $M^*$. Create a bipartite graph with the sets in $M$ as the left vertices, and the sets in $M^*$ as the right vertices. Add an edge between $A \in M$ and $B \in M^*$ iff $A$ intersects $B$. Here are some basic observations:


*

*Every right vertex has at least one left neighbor. Otherwise, we could add this set safely to $M$ to get a bigger family, contradicting the maximality of $M$. 

*Every left vertex has at most $k$ right neighbors. Otherwise two of the right neighbors will be forced to "share" a common element, contradicting the assumption that $M^*$ is a disjoint family of sets. 


Putting these two together, you should be able to deduce that $|M^*| \leq  |M|/k$. (Note that we do not have strict inequality.) Btw, the set-packing problem for the case $k=2$ is the well-known maximum matching problem. If you have seen matchings before, I encourage you to work out the proof for this specific case; it's quite illuminating. 
This bound is tight, as seen from the following example: let $S$ be the set of $k^2$ points arranged as a $k \times k$ grid. Define $M$ to be just the leftmost column. Define $M^*$ to be the family of $k$ rows, each of which contains $k$ points. Take $F$ to be $M \cup M^*$. Clearly $|M| =1$ and $|M^*|=k$. 
Better heuristics. Apparently, better local-heuristics heuristics are known for this problem, achieving a factor $k/2+\epsilon$ approximation. See e.g.: "Approximating  Discrete  Collections  via  Local  Improvements" by Halldorsson. 
A: What is wrong with partitioning $S$ into $k$ element disjoint sets?
