Vi introducerar ett nytt ramverk av Profet Ojämlikheter för kombinatoriska värderingsfunktioner. För en (icke-monoton) submodulär objektiv funktion över en godtycklig matris genomförbarhet begränsning, ger vi en O(1)-konkurrenskraftig algoritm. För en monoton subadditiv objektiv funktion över en godtycklig nedåtstängd genomförbarhetsbegränsning, ger vi en O (log n log 2 r)-konkurrenskraftig algoritm (där r är kardinaliteten i den största möjliga delmängd). Inspirerade av beviset på vår subadditiva profet ojämlikhet, får vi också en O (log n · log 2 r)-konkurrenskraftiga algoritm för Sekreteraren Problem med en monoton subadditive objektiv funktion som är föremål för en godtycklig nedåt-stängd genomförbarhet begränsning. Även för det speciella fallet av en kardinalitet genomförbarhetsbegränsning, kringgår vår algoritm en  under Bateni, Hajiaghayi, och Zadimoghaddam [BHZ13] i en begränsad frågemodell. På vägen till vår submodulära profet ojämlikhet, visar vi ett tekniskt resultat av oberoende intresse: vi visar en variant av Correlation Gap Lemma [CCPV07, ADSY12] för icke-monoton submodulära funktioner.
Rubinstein och Singla REF införde ramar för kombinatoriska värderingsfunktioner.
Combinatorial Prophet Inequalities
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}