Vi studerar generaliseringar av "Prophet Inequality" och "Secretary Problem", där algoritmen är begränsad till ett godtyckligt nedåtstängt set-system. För värden {0, 1} ger vi O (log n)-kompetitiva algoritmer för båda problemen. Detta ligger nära den nedre gränsen (log n/ log log n) på grund av Babaioff, Immorlica och Kleinberg. För allmänna värden, våra resultat översätta till O (log n · log r)-konkurrenskraftiga algoritmer, där r är kardinaliteten i den största möjliga uppsättningen. Detta löser (upp till O (log r · log n) faktorer) en öppen fråga som ställs till oss av Bobby Kleinberg [13].
Nedre stängda genomförbarhetsbegränsningar REF.
Beyond matroids: secretary problem and prophet inequality with general constraints
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}