Vi presenterar generaliserade sekreterare problem som en ram för online auktioner. Element, såsom potentiella anställda eller kunder, anländer en efter en på nätet. Efter att ha observerat värdet som härrör från ett element, men utan att känna till värdena för framtida element, måste algoritmen fatta ett oåterkalleligt beslut om huruvida elementet ska behållas som en del av en lösning, eller förkasta det. Det sätt på vilket sekreterarens ramverk skiljer sig från traditionella online-algoritmer är att elementen anländer i enhetlig slumpmässig ordning. Många naturliga online auktion scenarier kan användas som generaliserade sekreterare problem, genom att införa naturliga begränsningar för de genomförbara uppsättningar. För många sådana inställningar presenterar vi förvånansvärt starka konstanta faktorgarantier på det förväntade värdet av lösningar som erhållits av online-algoritmer. Ramen är också lätt att utöka för att ta hänsyn till tidsdiskonterade intäkter och incitamentskompatibilitet. Vi ger en översikt över aktuella resultat och framtida forskningsinriktningar.
En generaliserad sekreteraralgoritmram presenterades av Babaioff et al. REF för onlineauktioner.
Online auctions and generalized secretary problems
{'venue': 'SECO', 'journal': None, 'mag_field_of_study': ['Computer Science']}