Vi undersöker onlinealgoritmer för maximal (vikt) oberoende uppsättning på graf klasser med avgränsade induktiva oberoende nummer som t.ex. intervall och disk grafer med applikationer till, t.ex., schemaläggning och spektrumallokering. I online-inställningen antas det att noder av en okänd graf anländer en efter en över tiden. En online-algoritm måste avgöra om en ankommande nod ska ingå i den oberoende uppsättningen. Tyvärr kan detta naturliga och praktiskt relevanta online-problem inte studeras på ett meningsfullt sätt inom ramen för en klassisk konkurrensanalys, eftersom konkurrensförhållandet på värsta tänkbara ingångssekvenser är lägre än vad som avgränsas av (n). Denna förödande nedre gräns håller även för randomiserade algoritmer på oviktade intervallgrafer och därmed för en av de mest begränsade grafklass som övervägs. Eftersom en värsta-fall analys är meningslöst, studerar vi online oberoende set i en stokastisk analys. I stället för att fokusera på en särskild stokastisk inmatningsmodell presenterar vi en generisk provtagningsmetod som gör det möjligt för oss att ta fram online-algoritmer som ger prestandagarantier för en mängd olika indatamodeller. I synnerhet täcker vår analys stokastiska indatamodeller som sekreterarmodellen, där en kontradiktorisk graf presenteras i slumpmässig ordning, och profet-inquality-modellen, i vilken en slumpmässigt genererad graf presenteras i kontradiktorisk ordning. Vår provtagning närmar sig broar alltså mellan stokastiska ingångsmodeller av helt olika natur. Dessutom visar vi att vårt tillvägagångssätt kan tillämpas på en praktiskt motiverad inställning av antagningskontroll där algoritmen använder indata från en föregående period som exempeldiagram för den aktuella perioden. Vår provtagningsmetod ger en online-algoritm för maximal oberoende uppsättning på intervall och diskgrafer med konkurrenskraftigt förhållande O(1) med avseende på alla nämnda stokastiska ingångsmodeller. Mer allmänt, för grafklasser med induktivt oberoende nummer ρ är konkurrensförhållandet O(ρ2). Metoden kan utvidgas mot maximal vikt oberoende uppsättning genom att förlora endast en faktor av O(log n) i konkurrensförhållandet med n som anger (förväntat) antal noder. Denna övre gräns kompletteras med en nedre gräns av  och 2 log n (log n/ log 2 log n) som visar att vår provtagningsmetod uppnår nästan det optimala konkurrensförhållandet i alla de aktuella modellerna. Dessutom generaliserar vi vår analys för att ta itu med flera praktiskt motiverade förlängningar av det oberoende set-problemet, t.ex. ankomst- och avgångstider för noder eller kantviktade grafer som fångar SINR-liknande interferenskonflikter i trådlösa nätverk.
Framträdande graf klasser i nätverksprogram tillåter bra sekreterare algoritmer för oberoende uppsättning REF.
Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}