Improved Algorithms in the Random-Order Model: Knapsack, GAP, and BeyondResearch Paper
Online services allocate limited resources to requests arriving over time. Accepting a request earns value but uses capacity a later, more valuable request might have needed, and decisions cannot be revised. The simplest such model is online knapsack; the generalized assignment problem (GAP) extends it to several machines on which an item may have different…