Randomized Rounding for Set Cover modification
$begingroup$
I know that the following is the standard Randomized Rounding for Set Cover problem:
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq 1 forall e in U$
$x(S) in [0,1] S in mathcal{S}$
The above linear program cover every element at least one time ($min sum_{S: e in S} x(S) geq 1 forall e in U$).
Set $S$ is picked with probability $p(S) = x^*(S)$
$E[ALG] = sum_{S in mathcal{S}} c(S)p(S) = sum_{S in mathcal{S}} c(S)x^*(S) = OPT^{LP} leq OPT$
Considering $a in S,
Pr[a is covered] = 1 - (1 - p(S_1)) times ... times (1 - p(S_k)) geq 1 - (1 - frac{1}{k})^k geq 1 - frac{1}{e} $
So each element $a in U$ is covered with $Prob geq 1 - frac{1}{e} $
Picking $d$ log $n$ subcollections $C^prime = C_1 cup ... cup C_{d log n}$ with $d$ such that :
$Pr[a not covered] leq (frac{1}{e})^{d log n} leq frac{1}{4n}$
We obtain:
$E[COST(C^prime)] leq d times log n OPT^{LP}$
$Pr[COST(C^prime)] geq 4d times log n OPT^{LP} leq frac{1}{4}$
$Pr[COST(C^prime) not easible] leq n times frac{1}{4n} leq frac{1}{4}$
$Pr[COST(C^prime) geq 4d times log n OPT^{LP} AND C^prime is feasible] geq frac{1}{2}$
Expected number of repetitions = 2.
Now my question is: how do thinks change if we consider the following LP?
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq m forall e in U$
$x(S) in [0,1] S in mathcal{S}$
Considering $m = 1,2,..,n$. Of course for $m = 1$ we re-obtain the above steps but for $m geq 2$? For example for $m = 3$? Is there a generalized solution $forall m$?
algorithms
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
$endgroup$
migrated from datascience.stackexchange.com Jan 6 at 16:21
This question came from our site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field.
add a comment |
$begingroup$
I know that the following is the standard Randomized Rounding for Set Cover problem:
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq 1 forall e in U$
$x(S) in [0,1] S in mathcal{S}$
The above linear program cover every element at least one time ($min sum_{S: e in S} x(S) geq 1 forall e in U$).
Set $S$ is picked with probability $p(S) = x^*(S)$
$E[ALG] = sum_{S in mathcal{S}} c(S)p(S) = sum_{S in mathcal{S}} c(S)x^*(S) = OPT^{LP} leq OPT$
Considering $a in S,
Pr[a is covered] = 1 - (1 - p(S_1)) times ... times (1 - p(S_k)) geq 1 - (1 - frac{1}{k})^k geq 1 - frac{1}{e} $
So each element $a in U$ is covered with $Prob geq 1 - frac{1}{e} $
Picking $d$ log $n$ subcollections $C^prime = C_1 cup ... cup C_{d log n}$ with $d$ such that :
$Pr[a not covered] leq (frac{1}{e})^{d log n} leq frac{1}{4n}$
We obtain:
$E[COST(C^prime)] leq d times log n OPT^{LP}$
$Pr[COST(C^prime)] geq 4d times log n OPT^{LP} leq frac{1}{4}$
$Pr[COST(C^prime) not easible] leq n times frac{1}{4n} leq frac{1}{4}$
$Pr[COST(C^prime) geq 4d times log n OPT^{LP} AND C^prime is feasible] geq frac{1}{2}$
Expected number of repetitions = 2.
Now my question is: how do thinks change if we consider the following LP?
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq m forall e in U$
$x(S) in [0,1] S in mathcal{S}$
Considering $m = 1,2,..,n$. Of course for $m = 1$ we re-obtain the above steps but for $m geq 2$? For example for $m = 3$? Is there a generalized solution $forall m$?
algorithms
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
$endgroup$
migrated from datascience.stackexchange.com Jan 6 at 16:21
This question came from our site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field.
add a comment |
$begingroup$
I know that the following is the standard Randomized Rounding for Set Cover problem:
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq 1 forall e in U$
$x(S) in [0,1] S in mathcal{S}$
The above linear program cover every element at least one time ($min sum_{S: e in S} x(S) geq 1 forall e in U$).
Set $S$ is picked with probability $p(S) = x^*(S)$
$E[ALG] = sum_{S in mathcal{S}} c(S)p(S) = sum_{S in mathcal{S}} c(S)x^*(S) = OPT^{LP} leq OPT$
Considering $a in S,
Pr[a is covered] = 1 - (1 - p(S_1)) times ... times (1 - p(S_k)) geq 1 - (1 - frac{1}{k})^k geq 1 - frac{1}{e} $
So each element $a in U$ is covered with $Prob geq 1 - frac{1}{e} $
Picking $d$ log $n$ subcollections $C^prime = C_1 cup ... cup C_{d log n}$ with $d$ such that :
$Pr[a not covered] leq (frac{1}{e})^{d log n} leq frac{1}{4n}$
We obtain:
$E[COST(C^prime)] leq d times log n OPT^{LP}$
$Pr[COST(C^prime)] geq 4d times log n OPT^{LP} leq frac{1}{4}$
$Pr[COST(C^prime) not easible] leq n times frac{1}{4n} leq frac{1}{4}$
$Pr[COST(C^prime) geq 4d times log n OPT^{LP} AND C^prime is feasible] geq frac{1}{2}$
Expected number of repetitions = 2.
Now my question is: how do thinks change if we consider the following LP?
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq m forall e in U$
$x(S) in [0,1] S in mathcal{S}$
Considering $m = 1,2,..,n$. Of course for $m = 1$ we re-obtain the above steps but for $m geq 2$? For example for $m = 3$? Is there a generalized solution $forall m$?
algorithms
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
$endgroup$
I know that the following is the standard Randomized Rounding for Set Cover problem:
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq 1 forall e in U$
$x(S) in [0,1] S in mathcal{S}$
The above linear program cover every element at least one time ($min sum_{S: e in S} x(S) geq 1 forall e in U$).
Set $S$ is picked with probability $p(S) = x^*(S)$
$E[ALG] = sum_{S in mathcal{S}} c(S)p(S) = sum_{S in mathcal{S}} c(S)x^*(S) = OPT^{LP} leq OPT$
Considering $a in S,
Pr[a is covered] = 1 - (1 - p(S_1)) times ... times (1 - p(S_k)) geq 1 - (1 - frac{1}{k})^k geq 1 - frac{1}{e} $
So each element $a in U$ is covered with $Prob geq 1 - frac{1}{e} $
Picking $d$ log $n$ subcollections $C^prime = C_1 cup ... cup C_{d log n}$ with $d$ such that :
$Pr[a not covered] leq (frac{1}{e})^{d log n} leq frac{1}{4n}$
We obtain:
$E[COST(C^prime)] leq d times log n OPT^{LP}$
$Pr[COST(C^prime)] geq 4d times log n OPT^{LP} leq frac{1}{4}$
$Pr[COST(C^prime) not easible] leq n times frac{1}{4n} leq frac{1}{4}$
$Pr[COST(C^prime) geq 4d times log n OPT^{LP} AND C^prime is feasible] geq frac{1}{2}$
Expected number of repetitions = 2.
Now my question is: how do thinks change if we consider the following LP?
$min sum_{S in mathcal{S}} c(S)x(S)$
s.t
$sum_{S: e in S} x(S) geq m forall e in U$
$x(S) in [0,1] S in mathcal{S}$
Considering $m = 1,2,..,n$. Of course for $m = 1$ we re-obtain the above steps but for $m geq 2$? For example for $m = 3$? Is there a generalized solution $forall m$?
algorithms
algorithms
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
asked Jan 6 at 10:10
CuriousMindCuriousMind
32
32
migrated from datascience.stackexchange.com Jan 6 at 16:21
This question came from our site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field.
migrated from datascience.stackexchange.com Jan 6 at 16:21
This question came from our site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint: the change is in the calculation of $P[text{a is covered}]$ and its effect on the part of after that. You should consider more cases if $m > 1$ which is different choosing a subset of $S_1, ldots, S_k$ which are not covered.
$$P[text{a is covered}] = 1 - left((1-P(S_1))times cdots times (1-P(S_k)) + binom{k}{1} (p(S_i)times text{multiplication of other $1-p(S_j)$}) + cdots + binom{k}{m} (p(S_i)times cdots times p(S_{i + m}))times text{multiplication of other $1-p(S_j)$}right) geq 1- left((1-frac{1}{k})^k + kfrac{1}{k}(1-frac{1}{k-1})^{k-1} + cdots + binom{k}{m}(frac{1}{k})^m(1-frac{1}{k-m})^{k-m}right) $$
which $S_i, ldots, S_{i+k}$ are covered in different cases.
As you can see, simplification of this is not that easy. You can't say it is greater than $1- frac{m}{e}$ here as the multiplier here is not simple here, in contrast with the first case.
answered Jan 6 at 10:51
OmGOmG
2,512824
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064062%2frandomized-rounding-for-set-cover-modification%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint: the change is in the calculation of $P[text{a is covered}]$ and its effect on the part of after that. You should consider more cases if $m > 1$ which is different choosing a subset of $S_1, ldots, S_k$ which are not covered.
$$P[text{a is covered}] = 1 - left((1-P(S_1))times cdots times (1-P(S_k)) + binom{k}{1} (p(S_i)times text{multiplication of other $1-p(S_j)$}) + cdots + binom{k}{m} (p(S_i)times cdots times p(S_{i + m}))times text{multiplication of other $1-p(S_j)$}right) geq 1- left((1-frac{1}{k})^k + kfrac{1}{k}(1-frac{1}{k-1})^{k-1} + cdots + binom{k}{m}(frac{1}{k})^m(1-frac{1}{k-m})^{k-m}right) $$
which $S_i, ldots, S_{i+k}$ are covered in different cases.
As you can see, simplification of this is not that easy. You can't say it is greater than $1- frac{m}{e}$ here as the multiplier here is not simple here, in contrast with the first case.
answered Jan 6 at 10:51
OmGOmG
2,512824
$endgroup$
add a comment |
$begingroup$
Hint: the change is in the calculation of $P[text{a is covered}]$ and its effect on the part of after that. You should consider more cases if $m > 1$ which is different choosing a subset of $S_1, ldots, S_k$ which are not covered.
$$P[text{a is covered}] = 1 - left((1-P(S_1))times cdots times (1-P(S_k)) + binom{k}{1} (p(S_i)times text{multiplication of other $1-p(S_j)$}) + cdots + binom{k}{m} (p(S_i)times cdots times p(S_{i + m}))times text{multiplication of other $1-p(S_j)$}right) geq 1- left((1-frac{1}{k})^k + kfrac{1}{k}(1-frac{1}{k-1})^{k-1} + cdots + binom{k}{m}(frac{1}{k})^m(1-frac{1}{k-m})^{k-m}right) $$
which $S_i, ldots, S_{i+k}$ are covered in different cases.
As you can see, simplification of this is not that easy. You can't say it is greater than $1- frac{m}{e}$ here as the multiplier here is not simple here, in contrast with the first case.
answered Jan 6 at 10:51
OmGOmG
2,512824
$endgroup$
add a comment |
$begingroup$
Hint: the change is in the calculation of $P[text{a is covered}]$ and its effect on the part of after that. You should consider more cases if $m > 1$ which is different choosing a subset of $S_1, ldots, S_k$ which are not covered.
$$P[text{a is covered}] = 1 - left((1-P(S_1))times cdots times (1-P(S_k)) + binom{k}{1} (p(S_i)times text{multiplication of other $1-p(S_j)$}) + cdots + binom{k}{m} (p(S_i)times cdots times p(S_{i + m}))times text{multiplication of other $1-p(S_j)$}right) geq 1- left((1-frac{1}{k})^k + kfrac{1}{k}(1-frac{1}{k-1})^{k-1} + cdots + binom{k}{m}(frac{1}{k})^m(1-frac{1}{k-m})^{k-m}right) $$
which $S_i, ldots, S_{i+k}$ are covered in different cases.
As you can see, simplification of this is not that easy. You can't say it is greater than $1- frac{m}{e}$ here as the multiplier here is not simple here, in contrast with the first case.
answered Jan 6 at 10:51
OmGOmG
2,512824
$endgroup$
Hint: the change is in the calculation of $P[text{a is covered}]$ and its effect on the part of after that. You should consider more cases if $m > 1$ which is different choosing a subset of $S_1, ldots, S_k$ which are not covered.
$$P[text{a is covered}] = 1 - left((1-P(S_1))times cdots times (1-P(S_k)) + binom{k}{1} (p(S_i)times text{multiplication of other $1-p(S_j)$}) + cdots + binom{k}{m} (p(S_i)times cdots times p(S_{i + m}))times text{multiplication of other $1-p(S_j)$}right) geq 1- left((1-frac{1}{k})^k + kfrac{1}{k}(1-frac{1}{k-1})^{k-1} + cdots + binom{k}{m}(frac{1}{k})^m(1-frac{1}{k-m})^{k-m}right) $$
which $S_i, ldots, S_{i+k}$ are covered in different cases.
As you can see, simplification of this is not that easy. You can't say it is greater than $1- frac{m}{e}$ here as the multiplier here is not simple here, in contrast with the first case.
answered Jan 6 at 10:51
OmGOmG
2,512824
answered Jan 6 at 10:51
OmGOmG
2,512824
answered Jan 6 at 10:51
OmGOmG
2,512824
answered Jan 6 at 10:51
OmGOmG
2,512824
2,512824
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064062%2frandomized-rounding-for-set-cover-modification%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
