Mixing
Deterministic algorithm to solve weighted set cover in O(2^n)
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
A weighted set cover problem is:
Given a universe $U=1,2,...,n$ and a collection of subsets of $U$, $mathcal S=S_1,S_2,...,S_m$, and a cost function $c:mathcal Sto Q^+$ , find a minimum cost subcollection of $mathcal S$ that covers all elements of $U$.
The question is how to design a deterministic algorithm to solve weight set cover in $O(2^n)$ (just find the optimum solution)?
If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.
Thanks in advanced!
After some experiment I find that when a the $mathcal S$ is acutally equals to the power set of the universe $U$($m=2^n$),there are less than $2^n$ combination of the power set of $mathcal S$($2^n^n$) can cover the universe $U$. But how can I prove that the coverable combination of $mathcal S$ is less than $2^n$?
discrete-mathematics algorithms
asked Jul 28 at 15:08
wst
114
add a comment |Â
up vote
2
down vote
favorite
A weighted set cover problem is:
Given a universe $U=1,2,...,n$ and a collection of subsets of $U$, $mathcal S=S_1,S_2,...,S_m$, and a cost function $c:mathcal Sto Q^+$ , find a minimum cost subcollection of $mathcal S$ that covers all elements of $U$.
The question is how to design a deterministic algorithm to solve weight set cover in $O(2^n)$ (just find the optimum solution)?
If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.
Thanks in advanced!
After some experiment I find that when a the $mathcal S$ is acutally equals to the power set of the universe $U$($m=2^n$),there are less than $2^n$ combination of the power set of $mathcal S$($2^n^n$) can cover the universe $U$. But how can I prove that the coverable combination of $mathcal S$ is less than $2^n$?
discrete-mathematics algorithms
asked Jul 28 at 15:08
wst
114
A hint maybe is that from strong exponential time hypothesis(SETH) one cannot find a algorithm faster than O(2^n).
– wst
Jul 29 at 2:58
Maybe cstheory.stackexchange.com could answer your question
– Mike Earnest
Jul 31 at 14:12
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
A weighted set cover problem is:
Given a universe $U=1,2,...,n$ and a collection of subsets of $U$, $mathcal S=S_1,S_2,...,S_m$, and a cost function $c:mathcal Sto Q^+$ , find a minimum cost subcollection of $mathcal S$ that covers all elements of $U$.
The question is how to design a deterministic algorithm to solve weight set cover in $O(2^n)$ (just find the optimum solution)?
If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.
Thanks in advanced!
After some experiment I find that when a the $mathcal S$ is acutally equals to the power set of the universe $U$($m=2^n$),there are less than $2^n$ combination of the power set of $mathcal S$($2^n^n$) can cover the universe $U$. But how can I prove that the coverable combination of $mathcal S$ is less than $2^n$?
discrete-mathematics algorithms
asked Jul 28 at 15:08
wst
114
A weighted set cover problem is:
Given a universe $U=1,2,...,n$ and a collection of subsets of $U$, $mathcal S=S_1,S_2,...,S_m$, and a cost function $c:mathcal Sto Q^+$ , find a minimum cost subcollection of $mathcal S$ that covers all elements of $U$.
The question is how to design a deterministic algorithm to solve weight set cover in $O(2^n)$ (just find the optimum solution)?
If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.
Thanks in advanced!
After some experiment I find that when a the $mathcal S$ is acutally equals to the power set of the universe $U$($m=2^n$),there are less than $2^n$ combination of the power set of $mathcal S$($2^n^n$) can cover the universe $U$. But how can I prove that the coverable combination of $mathcal S$ is less than $2^n$?
discrete-mathematics algorithms
asked Jul 28 at 15:08
wst
114
edited Jul 29 at 5:10
asked Jul 28 at 15:08
wst
114
asked Jul 28 at 15:08
wst
114
asked Jul 28 at 15:08
wst
114
114
A hint maybe is that from strong exponential time hypothesis(SETH) one cannot find a algorithm faster than O(2^n).
– wst
Jul 29 at 2:58
Maybe cstheory.stackexchange.com could answer your question
– Mike Earnest
Jul 31 at 14:12
add a comment |Â
A hint maybe is that from strong exponential time hypothesis(SETH) one cannot find a algorithm faster than O(2^n).
– wst
Jul 29 at 2:58
Maybe cstheory.stackexchange.com could answer your question
– Mike Earnest
Jul 31 at 14:12
A hint maybe is that from strong exponential time hypothesis(SETH) one cannot find a algorithm faster than O(2^n).
– wst
Jul 29 at 2:58
A hint maybe is that from strong exponential time hypothesis(SETH) one cannot find a algorithm faster than O(2^n).
– wst
Jul 29 at 2:58
Maybe cstheory.stackexchange.com could answer your question
– Mike Earnest
Jul 31 at 14:12
Maybe cstheory.stackexchange.com could answer your question
– Mike Earnest
Jul 31 at 14:12
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865315%2fdeterministic-algorithm-to-solve-weighted-set-cover-in-o2n%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
A hint maybe is that from strong exponential time hypothesis(SETH) one cannot find a algorithm faster than O(2^n).
– wst
Jul 29 at 2:58
Maybe cstheory.stackexchange.com could answer your question
– Mike Earnest
Jul 31 at 14:12