Låt X = {1, 2,..., n} vara en mark uppsättning av n element, och låt S vara en familj av undergrupper av X,  tills = m, med en positiv kostnad cS i samband med varje S  och S. Betrakta följande online-version av set omslag problem, beskrivs som ett spel mellan en algoritm och en motståndare. En motståndare ger element till algoritmen från X en efter en. När ett nytt element väl har getts måste algoritmen täcka det med någon uppsättning S som innehåller det. Vi antar att elementen i X och medlemmarna i S är kända i förväg för algoritmen, men, den uppsättning X X X av element som ges av motståndaren är inte känd i förväg till algoritmen. (I allmänhet kan X vara en strikt delmängd av X.) Målet är att minimera den totala kostnaden för de uppsättningar som valts av algoritmen. Låt C betecknar familjen av uppsättningar i S som algoritmen väljer. I slutet av spelet motståndaren producerar också (off-line) en familj av uppsättningar COP T som täcker X. Prestanda av algoritmen är förhållandet Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga citering på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. STOC '03 juni 9-11, 2003. San Diego, Kalifornien, USA. Upphovsrätt 2003 mellan kostnaden för C och kostnaden för COP T. Det maximala förhållandet, som tas över alla inmatningssekvenser, är det konkurrenskraftiga förhållandet mellan algoritmen. Vi presenterar en O(log m log n) konkurrenskraftig deterministisk algoritm för problemet, och etablera en nästan matchande log n log m log log m+log log n lägre gräns för alla intressanta värden av m och n. De tekniker som används är motiverade av liknande tekniker som utvecklats i beräkningsteori för online förutsägelse (t.ex., WINNOW algoritm) tillsammans med ett nytt sätt att omvandla den fraktionerade lösning de levererar till en deterministisk online algoritm.
Samma tillvägagångssätt användes också underförstått i REF, där en deterministisk online-O(log n log m)-konkurrenskraftig algoritm för den integrerade uppsättningen täckningsproblem tillhandahölls.
The online set cover problem
{'venue': "STOC '03", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}