Find N best subset of quotations

I am faced with the following problem;

We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations $$Q_1 ... Q_k$$. Each Quotation is a $$M \times N$$ matrix with weights categories of packets along one axis and size categories along the other axis. We are provided with a list of packets as well with respective weights and sizes such that we can convert the packages to be shipped into a 2d matrix of size $$M \times N$$ as well based on categorization of each packet and each cell shall contain the relevant number of packets in that weight+size category. Let's call this matrix $$P$$.

The total shipping cost for all the packets should we chose a shipping company '$$i$$' is sum of ( $$Q_i \times P$$ ) where '$$\times$$' is the element-wise multiplication of the two matrices.

We are required to find a subset of size '$$w$$' shipping companies (or quotations) such that the overall shipping cost is minimum.

I understand that a brute force algorithm trying out all combinations is not going to work due to the explosion of the number of combinations as '$$w$$' starts to increase. Moreover, I have also convinced myself that I can not iteratively build out a solution by first selecting two best quotations, merging them into one and then continue to add one more till I reach '$$w$$'.

Can someone help me find the relevant class of problems and suggest a solution?

• I don't understand the problem here. If you can add as many shipping companies as you want to $w$, then you just need to find the $Q_i$ with the cheapest price for each of the $m \cdot n$ different types of packages. That's a $m \cdot n \cdot k$ time solution. Am I missing a some requirement for the solution? – AstridNeu Sep 18 at 20:51
• 'w' is a number which represents the number of shipping companies you can add to the solution set. This number is an input for the problem. – Tayyab Sep 19 at 18:38

This problem is $$\textrm{NP}$$-hard by a reduction from (the decision version of) set-cover: given an integer $$k$$, a set of items $$I = \{x_1, \dots, x_n\}$$ and a collection $$S = \{S_1, \dots, S_m \} \subseteq 2^I$$ of subsets of $$I$$, decide whether there is a subset $$C$$ of $$S$$ such that $$|C| \le k$$ and $$\bigcup_{S_j \in C} S_j = I$$.

Given an instance of set-cover, we can reduce it to your problem as follows:

• There are $$n$$ packages to be shipped. Each package has a unique combination of weight class and category. For simplicity you can think of all the packages being in same category but having different weight classes. I will denote by $$W_i$$ the weight class of the $$i$$-th package.

• There are $$m$$ shipping companies. The $$j$$-th shipping company ships a package of weight class $$W_i$$, with $$x_i \in S_j$$, for a cost of $$\varepsilon < \frac{1}{n}$$ and a package of weight class $$W_i$$, $$x_i \not\in S_j$$, for a cost of $$1$$.

• Pick $$w = k$$.

There is a set-cover of size at most $$k$$ iff the cost for shipping all the packages using at most $$w$$ companies is at most $$\varepsilon n < 1$$.

Indeed, given a set-cover $$C = \{ S_{j_1}, \dots, S_{j_\ell} \}$$ of size $$\ell < k$$ we know that $$\bigcup_{i=1}^\ell S_{j_\ell} = I$$, i.e., if we select the $$j_1$$-th, $$j_2$$-th, $$\dots$$, and $$j_\ell$$-th shipping companies, we can send each of the $$n$$ packages at a cost of $$\varepsilon$$.

On the other hand, if there is a way to send all the packages using at most $$w$$ shipping companies with a cost of at most $$\varepsilon n < 1$$ then, for each of the $$n$$ packages, there must be at least one selected company that ships it with a cost of $$\varepsilon$$. In other words the sets $$S_j$$ corresponding to the selected companies are a set-cover of size at most $$w = k$$.

Notice that any solution has either a cost of $$\varepsilon n$$ or a cost of at least $$1$$. Choosing $$\varepsilon$$ small enough shows that this problem is also inapproximable (in fact, if a shipping cost of $$0$$ is allowed, you can directly set $$\varepsilon = 0$$).