O(log log Rank) Competitive Ratio for the Matroid Secretary Problem.
Oded LachishPublished in: FOCS (2014)
Keyphrases
- competitive ratio
- log log
- single machine
- lower bound
- positive integer
- average case
- online algorithms
- processing times
- optimal strategy
- convergence rate
- scheduling problem
- upper bound
- learning algorithm
- affine invariance
- combinatorial optimization
- affine transform
- worst case
- sample complexity
- branch and bound algorithm
- agnostic learning
- np hard
- online learning