About: Correlation gap     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FCorrelation_gap&invfp=IFP_OFF&sas=SAME_AS_OFF

In stochastic programming, the correlation gap is the worst-case ratio between the cost when the random variables are correlated to the cost when the random variables are independent. As an example, consider the following optimization problem. A teacher wants to know whether to come to class or not. There are n potential students. For each student, there is a probability of 1/n that the student will attend the class. If at least one student attends, then the teacher must come and his cost is 1. If no students attend, then the teacher can stay at home and his cost is 0. The goal of the teacher is to minimize his cost. This is a stochastic-programming problem, because the constraints are not known in advance – only their probabilities are known. Now, there are two cases regarding the correla

AttributesValues
rdfs:label
  • Correlation gap (en)
rdfs:comment
  • In stochastic programming, the correlation gap is the worst-case ratio between the cost when the random variables are correlated to the cost when the random variables are independent. As an example, consider the following optimization problem. A teacher wants to know whether to come to class or not. There are n potential students. For each student, there is a probability of 1/n that the student will attend the class. If at least one student attends, then the teacher must come and his cost is 1. If no students attend, then the teacher can stay at home and his cost is 0. The goal of the teacher is to minimize his cost. This is a stochastic-programming problem, because the constraints are not known in advance – only their probabilities are known. Now, there are two cases regarding the correla (en)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
date
  • July 2016 (en)
reason
  • see talk page--where did this come from? (en)
has abstract
  • In stochastic programming, the correlation gap is the worst-case ratio between the cost when the random variables are correlated to the cost when the random variables are independent. As an example, consider the following optimization problem. A teacher wants to know whether to come to class or not. There are n potential students. For each student, there is a probability of 1/n that the student will attend the class. If at least one student attends, then the teacher must come and his cost is 1. If no students attend, then the teacher can stay at home and his cost is 0. The goal of the teacher is to minimize his cost. This is a stochastic-programming problem, because the constraints are not known in advance – only their probabilities are known. Now, there are two cases regarding the correlation between the students: * Case #1: the students are uncorrelated: each student decides whether to come to class or not by tossing a coin with probability , independently of the others. The expected cost in this case is . * Case #2: the students are correlated: one student is selected at random and comes to class, while the others stay at home. Note that the probability of each student to come is still . However, now the cost is 1. The correlation gap is the cost in case #2 divided by the cost in case #1, which is . prove that the correlation gap is bounded in several cases. For example, when the cost function is a submodular set function (as in the above example), the correlation gap is at most (so the above example is a worst-case). An upper bound on the correlation gap implies an upper bound on the loss that results from ignoring the correlation. For example, suppose we have a stochastic programming problem with a submodular cost function. We know the marginal probabilities of the variables, but we do not know whether they are correlated or not. If we just ignore the correlation and solve the problem as if the variables are independent, the resulting solution is a -approximation to the optimal solution. (en)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 56 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software