Detta papper behandlar stokastiska optimeringsproblem vars objektiva funktioner innebär krafter slumpmässiga variabler. För ett konkret exempel, överväga den klassiska STOCHASTIC l p LOAD BALANCING PROBLEM (STOCHLOADBAL p ): Det finns m maskiner och n jobb, och vi ges oberoende slumpvariabler Y ij beskriver fördelningen av den belastning som uppstår på maskinen i om vi tilldelar jobb j till det. Målet är att tilldela varje arbete till maskinerna för att minimera den förväntade l p - normen av den totala belastningen på maskinerna. Det vill säga, låta J i betecknar de jobb som tilldelats maskin i, vi vill minimera Medan konvex avkopplingar representerar en av de mest kraftfulla algoritmiska verktyg, i problem som STOCHLOADBAL p den största svårigheten är att fånga en sådan objektiv funktion på ett sätt som bara beror på varje slumpmässig variabel separat. I detta dokument, visa hur man fångar p-power-type mål på ett sådant åtskiljbart sätt genom att använda funktionsmetoden. Denna metod infördes just av Latała för att fånga på ett skarpt sätt ögonblicket av summor av slumpmässiga variabler genom de enskilda marginalerna. Vi visar först hur detta snabbt leder till en konstant faktor approximation för mycket allmänna delmängd urvalsproblem med p-moment mål. Dessutom ger vi en konstant-faktor approximation för STOCHLOADBAL p, förbättra på den senaste O ( p ln p ) - approximation av [Gupta et al., SODA 18]. Här är tillämpningen av metoden mycket mer involverad. I synnerhet måste vi bevisa strukturella resultat som förbinder den förväntade l p -normen för en slumpmässig vektor med p-momenten för dess koordinat-marginaler (maskinbelastningar) på ett skarpt sätt, med hänsyn till de olika skalor av laster som uppstår i de olika maskinerna genom ett okänt uppdrag. Dessutom har vår inledande konvexa (i själva verket linjära) avslappning exponentiellt många begränsningar som inte bidrar till integrerad avrundning; vi måste använda lösningen av denna LP för att få en reducerad LP som sedan kan användas för att få den önskade uppgiften.
Det stokastiska lastbalanseringsproblemet på icke-relaterade resurser har också studerats för allmänna l p - norms (observera att makespan motsvarar l ∞ - norm) och en approximation av konstant faktor är känd REF.
Stochastic $\ell_p$ Load Balancing and Moment Problems via the $L$-Function Method
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}