2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – AstridNeu Sep 18 at 20:51
  • $\begingroup$ '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. $\endgroup$ – Tayyab Sep 19 at 18:38
2
+25
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.