I det (klassiska) sekreteraren problemet, måste man anställa de bästa bland n kandidater. Kandidaterna intervjuas, en i taget, i en enhetlig slumpmässig ordning, och man måste bestämma på plats, om man ska anställa en kandidat eller fortsätta intervjua. Det är väl känt att den bästa kandidaten kan anställas med en sannolikhet på 1/e (Dynkin, 1963). Nya arbeten utvidga detta problem till inställningar där flera kandidater kan anställas, med förbehåll för vissa begränsningar. Här vill man hyra en uppsättning kandidater som maximerar en given objektiv funktion. Nästan alla förlängningar som beaktas i litteraturen antar att den objektiva uppsättningen funktionen är antingen linjär eller submodulär. Tyvärr, verkliga funktioner kanske inte har någon av dessa egenskaper. Tänk till exempel på ett scenario där man anställer forskare för ett projekt. Det kan faktiskt vara så att vissa forskare kan ersätta andra för den delen. Men det kan också vara så att vissa kombinationer av forskare resulterar i synergi (se t.ex. Woolley et al., Science 2010, för en forskning om kollektiv intelligens). Det första fenomenet kan modelleras av en submoudlar set-funktion, medan det senare inte kan. I detta arbete studerar vi sekreterare problemet med en godtycklig icke-negativ monoton värdering funktion, under förutsättning att en allmän matris begränsning. Det är inte svårt att bevisa att endast mycket dåliga resultat kan uppnås för denna klass av objektiva funktioner. Vi tar itu med denna hårdhet genom att kombinera följande: (1) Parametrisera våra algoritmer genom den supermodulära graden av den objektiva funktionen (definierad av Feige och Izsak, ITCS 2013), som i stort sett mäter avståndet till en funktion från att vara submodulär. (2) Föreslå en (berättigat) naturlig modell som tillåter approximativa garantier som är polynom i supermodulär grad (i motsats till standardmodellen som endast tillåter exponentiella garantier). Våra algoritmer lär sig inmatningen genom att köra en icke-trivial skattningsalgoritm på en del av den vars storlek beror på den supermodulära graden. Vi ger också bättre approximativa garantier för specialfallet med en enhetlig matrisrestriktion. Såvitt vi vet representerar våra resultat de första algoritmerna för ett sekreterarproblem som hanterar godtyckliga icke-negativa monotona värderingsfunktioner.
Av särskilt intresse för oss är en färsk tidning av Feldman och Izsak REF som anser matroid sekreterare problem med allmänna monotona objektiva funktioner, parametrized av supermodulär grad.
Building a Good Team: Secretary Problems and the Supermodular Degree
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}