Inspirerad av online annons allokering, studerar vi online stokastiska förpackning linjära program från teoretiska och praktiska ståndpunkter. Vi presenterar först en nästan optimal online-algoritm för en allmän klass av förpackning linjära program som modellerar olika online resursfördelningsproblem inklusive online-varianter av routing, annonstilldelningar, generaliserade uppdrag, och kombinatoriska auktioner. Som vårt huvudsakliga teoretiska resultat, bevisar vi att en enkel primal-dual träningsbaserad algoritm uppnår en (1 − o(1))-approximation garanti i slumpmässig ordning stokastisk modell. Detta är en signifikant förbättring jämfört med logaritmiska eller konstanta approximationer för de kontradiktoriska varianterna av samma problem (t.ex. faktor 1 – 1 e för annonstilldelning online, och log(m) för online routing). Vi fokuserar sedan på online-display ad allocation problem och studera effektiviteten och rättvisan i olika utbildningsbaserade och online tilldelningsalgoritmer på datamängder som samlats in från verkliga display ad allocation system. Vår experimentella utvärdering bekräftar effektiviteten hos utbildningsbaserade primal-dual algoritmer på verkliga datauppsättningar, och indikerar också en inneboende kompromiss mellan rättvisa och effektivitet.
REF presenterar liknande utbildningsbaserade algoritmer för mer allmänna linjära online tilldelningsproblem med liknande ångergarantier.
Online Stochastic Packing Applied to Display Ad Allocation
{'venue': 'ESA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}