0
$\begingroup$

Hi everybody,

I stumbled upon the following variant of a Set-Covering problem:

Given are the usual universe $\mathcal{U} = \{ u_1 , \ldots , u_n \}$ of elements, and a family of subsets $\mathcal{S} =\{S_1,\ldots,S_m\}$ with costs $c(S_i)$.

There are sets $S_i = \{u_i\} \in \mathcal{S}, i=1,\ldots,n$ and we know all of their costs $c(S_i)$. These can be seen as "base prices" for the single elements. Furthermore we also know the prices for all sets in $\mathcal{S}' \subset \mathcal{S}$, but we do not know the rest of $\mathcal{S}$.

The question now is: Can we estimate probability for the sets in $\mathcal{S}'$ to be in the optimal cover $C \subseteq \mathcal{S}$?

Are you aware of any literature on this? I searched quite some time already, but all I could find are randomized algorithms for the original weighted set-covering problem, or papers on the probabilistic SCP, which both does not seem to help.

So, any hints / keywords / sources would be greatly appreciated!

Thanks in advance,

Hendrik.

Improve this question
$\endgroup$
1
  • $\begingroup$ Hendrik, this might be interesting, but I think you should provide some more information in order to clarify what it is you want from an answer. How did you stumble on this? What is the probabilistic model you have in mind? Are you interested in some sort of asymptotics as $n\to\infty$? Do you want an algorithm? What is missing in the literature you looked at? $\endgroup$
    – Johan Wästlund
    Jul 19, 2011 at 8:05

1 Answer 1

Reset to default
2
$\begingroup$

Hi Johan,

thanks for your answer! I came across this problem in the context of combinatorial auctions. The items to bid on are $u_1,\ldots,u_n$, and a bid, is a subsets of the items (often called "bundle") attached with a price, which corresponds to one of the sets $S_i$ and $c(S_i)$.

I currently work on something like a "bidding agent": A component that

  1. generates a bunch of bid candidates (the set $\mathcal{S}'$) and
  2. tries to select the most promising candidates, i.e., those that have a high chance to win, and present them to the user for evaluation.

So much for the background. What I have done so far, is to run several auctions and analyze the results. I found that, maybe not surprisingly, the value $v(S_i):=\frac{c(S_i) - \sum_{u \in S_i}c(u)}{|S_i|}$ plays a crucial role. This is what the bid saves on average per item compared to the sum of market prices $c(u)$. But it is not as easy as "submit the best bids in terms of $v(\cdot)$, of course, since submitting many overlapping bids will lower the chance that many of them win.

To get a probability for a bid candidate, I tried to compare the distribution of $v(S_i)$ for all candidates $\mathcal{S}$ with the distribution in the optimal cover $C$. But I'm really not sure if this is a good approach, as I'm no statistician at all. That's why I asked for general literature hints. And I simply could not find any papers so far that deal with this sort of problem at all.

I hope this clarifies things a bit..? If I can supply more information, let me know. And thanks for your time! :-)

Hendrik.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sorry, this was meant to appear as a comment, too. :-( $\endgroup$
    – Hendrik
    Aug 4, 2011 at 9:52

Your Answer

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

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