Vi anser att en robust modell som föreslagits av Scarf, 1958, för stokastisk optimering när endast marginal sannolikheter (binär) slumpvariabler anges, och korrelationen mellan de slumpmässiga variablerna är okänd. I den robusta modellen är målet att minimera förväntade kostnader mot värsta möjliga gemensamma fördelning med dessa marginaler. Vi introducerar begreppet korrelationsgap för att jämföra denna modell med den stokastiska optimeringsmodellen som ignorerar korrelationer och minimerar förväntade kostnader under oberoende Bernoulli distribution. Vi identifierar en klass av funktioner, med hjälp av koncept för sammanfattande kostnadsdelningssystem från spelteorin, där korrelationsgapet är väl avgränsat och den robusta modellen kan approximeras nära av den oberoende distributionsmodellen. Som ett resultat härleder vi effektiva approximativa faktorer för många populära kostnadsfunktioner, såsom submodulära funktioner, anläggningsplats, och Steiner träd. Som biprodukt ger vår analys också några nya resultat inom områdena social välfärdsmaximering och existens av Walrasian equilibria, som kan vara av oberoende intresse.
Vårt övre band är nära relaterat till korrelationsgapet REF.
Correlation robust stochastic optimization
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}