För ett antal problem i teorin om online-algoritmer, är det känt att antagandet att element anländer i enhetligt slumpmässig ordning möjliggör utformningen av algoritmer med mycket bättre prestanda garantier än i värsta fall antaganden. Det väsentliga exemplet på detta fenomen är sekreterarens problem, där en algoritm försöker stoppa en sekvens i det ögonblick den observerar det maximala värdet i sekvensen. Som bekant, om sekvensen presenteras i jämnt slumpmässig ordning finns det en algoritm som lyckas med sannolikhet 1/e, medan ingen icke-trivial prestandagaranti är möjlig om elementen anländer i värsta fall ordning. I många av applikationerna av online-algoritmer, är det rimligt att anta att det finns någon slumpmässighet i inmatningssekvensen, men orimligt att anta att ankomst beställningen är enhetligt slumpmässig. Detta arbete initierar en undersökning av avslappning av slumpmässig ordning hypotes i online-algoritmer, genom att fokusera på sekreterare problem och fråga vilka prestanda garantier man kan bevisa under avslappnade antaganden. I detta syfte presenterar vi två uppsättningar av egenskaper distributioner över permutationer som tillräckliga villkor, som kallas (p, q, δ)-block-oberoende egendom och (k, δ)-uniform-framkallad-order egendom. Vi visar att dessa två är asymptotiskt likvärdiga genom att låna några tekniker från den berömda approximationsteorin. Dessutom visar vi att de båda antyder förekomsten av sekreterare algoritmer med konstant sannolikhet för korrekt urval, närmar sig den optimala konstanten 1/e som de relaterade parametrarna för fastigheten tenderar att sina extrema värden. Båda dessa egenskaper är betydligt svagare än det vanliga antagandet om enhetlig slumpmässighet; vi underbygger detta genom att tillhandahålla flera konstruktioner av distributioner som uppfyller (p, q, δ)-block-oberoende. Som en tillämpning av vår undersökning, bevisar vi att  till (log log n) är den minsta entropi för varje permutation distribution som tillåter konstant sannolikhet för korrekt urval i sekreterare problem med n element. Även om vårt block-oberoende villkor är tillräckligt för konstant sannolikhet för korrekt urval, är det inte nödvändigt, men vi presenterar komplexitet-teoretiska bevis för att det inte finns några enkla nödvändiga och tillräckliga kriterier. Slutligen undersöker vi i vilken utsträckning prestandagarantierna för andra algoritmer bevaras när man slappnar av den enhetliga slumpmässiga beställning antagande till (p, q, δ)-blockoberoende, erhålla ett negativt resultat för den viktade bipartite matchande algoritmen Korula och Pál.
Kesselheim m.fl. REF försöker lätta på antagandet att data anländer i slumpmässig ordning och definiera en klass av distributioner för vilka antagandet överträds, men prestandan för standard sekreteraralgoritmen förblir begränsad.
Secretary Problems with Non-Uniform Arrival Order
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}