Cubrir los bordes de un grafo bipartito con un conjunto mínimo de grafos completos bipartitos (bicliques) es un problema básico de teoría de grafos, con numerosas aplicaciones. En particular, se utiliza para caracterizar modelos parsimoniosos de un conjunto de observaciones (cada biclique corresponde a una o que relaciona las observaciones en los dos conjuntos de nodos conectados por la biclique). La versión de decisión del problema de cobertura mínima de bicliques es NP-Completo, y a menos que , el tamaño de la cobertura no puede aproximarse en general a menos de un factor sublineal del número de nodos (o bordes) en el grafo. En este trabajo, consideramos dos restricciones naturales al problema, motivadas por aplicaciones prácticas. En el primer caso, restringimos la cantidad de bicliques a las que un nodo puede pertenecer. Mostramos que cuando este número es al menos 5, el problema sigue siendo NP-duro. En contraste, mostramos que cuando los nodos pertenecen a no más de dos bicliques, el problema tiene aproximaciones eficientes. El segundo modelo que consideramos corresponde a observar un conjunto de muestras independientes de un modelo desconocido, gobernado por un número posiblemente grande de factores. El modelo está definido por un grafo bipartito, donde a cada nodo en se le asigna a un subconjunto arbitrario de hasta un número constante de factores, mientras que los nodos en (las observaciones independientes) se asignan a subconjuntos aleatorios del conjunto de factores donde puede crecer con el tamaño del grafo. Mostramos que esta versión práctica del problema de cobertura de bicliques es susceptible a aproximaciones eficientes.