Abstrakt. Vi presenterar en 1 - 1 - 1 k - kompetitiv algoritm för online stokastiska generaliserade tilldelningsproblem under antagandet att inget objekt tar upp mer än 1 k bråkdel av kapaciteten i någon bin. Objekt anländer online; varje objekt har ett värde och en storlek; vid ankomst kan ett objekt placeras i en behållare eller kastas; målet är att maximera det totala värdet av placeringen. Både värdet och storleken på en vara kan bero på den bin i vilken objektet placeras; storleken på en vara avslöjas först efter det att den har placerats i en bin; distributionsinformation finns tillgänglig om värdet och storleken på varje objekt i förväg (inte nödvändigtvis i.i.d), men objekt anländer i motsatt ordning (icke-adaptiv motståndare). Vi presenterar även en tillämpning av vårt resultat på prenumerationsbaserad reklam där varje annonsör, om den serveras, kräver ett visst minsta antal intryck (dvs. "allt eller ingenting"-modellen).
-konkurrenskraftig algoritm i förväntan för online GAP REF, där liknar tidigare arbete två begränsningar görs; att vikter och storlekar för varje objekt är stokastiska och varje objekts storlek är mindre än en 1 k av bin kapacitet.
The Online Stochastic Generalized Assignment Problem
{'venue': 'APPROX-RANDOM', 'journal': None, 'mag_field_of_study': ['Computer Science']}