1 vote

Generalized assignment problem with overall budget

The problem is NP-hard, by reduction from the the knapsack problem. ($B$ represents the maximum weight capacity of the knapsack, and for each item, add a new pair of task and worker with cost equal ...
D.W.'s user avatar
  • 12k
1 vote

Cheap online selection with weighted comparisons

As a function of $n=|S|$, the optimal competitive is $\Theta(n)$: Lemma 1. There is a deterministic $O(n)$-competitive online algorithm. Lemma 2. No deterministic (or randomized) online algorithm is $...
Neal Young's user avatar
  • 10.5k

Only top scored, non community-wiki answers of a minimum length are eligible