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 ...
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 $...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
online-algorithms × 56ds.algorithms × 23
approximation-algorithms × 10
reference-request × 8
graph-algorithms × 7
online-learning × 6
randomized-algorithms × 5
graph-theory × 4
optimization × 4
ds.data-structures × 4
lg.learning × 4
streaming-algorithms × 4
machine-learning × 3
data-streams × 3
stochastic-process × 3
cc.complexity-theory × 2
fl.formal-languages × 2
automata-theory × 2
lower-bounds × 2
pr.probability × 2
gt.game-theory × 2
directed-acyclic-graph × 2
matching × 2
convex-optimization × 2
scheduling × 2