1
$\begingroup$

I am looking for a formal name and an algorithmic approach to the following problem.

Given is a set of services each coming with a price:

  • {s1, 300}
  • {s2, 400}
  • {s3, 800}

Additionally there is a set of servicepackages each with a price that may differ from the total cost of the individual services:

  • {p1, {s1, s2}, 600}
  • {p2, {s2, s3}, 1050}
  • {p3, {s1, s3}, 950}
  • {p4, {s1, s2, s3}, 1250}

Now given a list of services (each service may appear many times) you want performed find the combination of packages and individual services with the lowest price. You can only use a package if you can completely fill it with services. A package may be ordered many times.

For example: Services to order :{s1,s2,s1,s3,s2,s3,s1}

possible Solutions:

  • {p4, p4, s1} : 2800
  • {p1, p1, p3, s3} : 2950

In this case the first solution would be the winner.

An exhaustive approach will quickly explode because it is O(n!) or even worse.

What is the formal name of this problem (if there is one)? How would you algorithmically approach that problem for hundreds of services and packages?

$\endgroup$
1
  • $\begingroup$ Sounds like some kind of combinatorial auction? $\endgroup$ Jul 2, 2015 at 13:35

1 Answer 1

1
$\begingroup$

I don't know the name of your problem, if there is one.

But, concerning the complexity: The decision-version of your problem seems to be strongly NP-complete. You can easily reduce ExactCoverBy3Sets to it:

Given a ground set $X = \{1, \ldots, 3q\}$ and a set $\mathcal{C}$ of 3-element subsets $C_i$ of $X$. Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ of disjoint subsets that cover $X$ ?

Assume we have $3q$ services $1,\ldots,3q$, each with a price of $q+1$. Furthermore, for each $C_i$, we have a package of the corresponding three elements at a price of $1$. Now, given the list $1,\ldots,3q$ of services to order, there is a solution with cost at most $q$ if and only if there is a solution to the given instance of ExactCoverBy3Sets. Since there are no double orders and since "You can only use a package if you can completely fill it with services", the sets are disjoint and cover the whole ground set $X$.

So, you won't succeed in finding a polynomial (exact) algorithm or an FPTAS. However, you can search for approximation algorithms for the above problem and/or the related problems SetPacking and MinimumCover (cf. Garey/Johnson, "Computers and Intractibility", Problems SP2, SP3 and SP5).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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