I profetens sekreterare problem, prover från en känd uppsättning sannolikhetsfördelningar anländer en efter en i en enhetligt slumpmässig ordning, och en algoritm måste oåterkalleligen plocka en av proven så snart den anländer. Målet är att maximera det förväntade värdet av det prov som plockas i förhållande till den förväntade maximala fördelningen. Detta är en av de mest enkla och grundläggande problem i online beslutsfattande som modellerar processen att sälja ett objekt till en sekvens av kunder. För ett närbesläktat problem som kallas Profeten Ojämlikhet där ordningen på de slumpmässiga variablerna är kontradiktorisk, är det känt att man kan uppnå i förväntan 1/2 av det förväntade maximum, och inget bättre förhållande är möjligt. För profetens sekreterare problem, det vill säga när variablerna anländer i en slumpmässig ordning, Esfandiari et al. (2015) visade att man faktiskt kan få 1 – 1/e av maximum. Den 1 - 1/ e bundet nyligen utökades till mer allmänna inställningar av Ehsani et al. (2018). Med tanke på dessa resultat kan man frestas att tro att 1 – 1/ e är den rätta gränsen. Vi visar att detta inte är fallet genom att tillhandahålla en algoritm för profetens sekreterare problem som slår 1 - 1/ e bundna och uppnår 1 - 1/ e + 1/ 400 gånger det förväntade maximum. Vi visar också en hårdhet resultat på prestanda algoritmer under en naturlig begränsning som vi kallar deterministisk distribution-insensitivitet.
Denna gräns på 1 – 1 e överträffades nyligen av REF till 1 – 1 e + 0,0025, och deras gräns sträcker sig också till slumpmässiga ordningsprofeter, i vilka de slumpmässiga variablerna anländer i en enhetlig slumpmässig ordning.
Prophet Secretary: Surpassing the 1-1/e Barrier
{'venue': "EC '18", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}