# Can sparse set cover problem be solved or approximated more efficiently comparing to its non-sparse counter part?

I am an electrical engineer who is currently working with some bench table placement problem, and suddenly my problem look pretty much like the set cover problem here. After that, some of my colleague told me that most problem in engineering is quite sparse and this should be exploited.

Therefore, my question is:

Can sparse set cover problem be solved or approximated more efficiently comparing to its non-sparse counter part ?

• What I had in mind was not specific to set covering problems. For a general linear or mixed integer linear programming problem, you have a linear constraint set $Ax=b$ which, for a given basis, is partitioned into a basic part ($Bx_B=b,$ with $B$ nonsingular) and a nonbasic part ($Nx_N = 0,$ with $x_N = 0.$ In textbooks (and old solver codes) you would solve $Bx_B = b$ by inverting $B.$ Current practice does not invert $B$ but rather factors it, perhaps using an LU decomposition, perhaps SVD or some other decomposition. (I'm being vague because I'm not a solver author.)