# Tag Info

Accepted

### How to design an online algorithm for secretary problem with multiple players?

Per @usul's suggestion, consider the following online greedy algorithm $A$. When bin $i$ is revealed, $A$ considers all subsets $S$ of not-yet assigned balls such that all balls in $S$ can fit ...
• 10.9k
Accepted

### Solving an online problem without maximizing or minimizing an objective

@orlp's intuition is correct. lemma. No online algorithm solves the problem in the worst case. Proof. Consider the following instance: $$f(p) = (1+p_1)(1+p_2)(1+p_3) \ge 8 \text{ with } B=3.$$ ...
• 10.9k
Accepted

### Searching for the original definition of online algorithms

Thanks. With Garmow's comment I was able to find the first two references which also called on-line algorithms as on-line: Johnson, David S. "Fast algorithms for bin packing." Journal of Computer ...

### Algorithms in preprocessed universe

As Ricky Demer said in his comment, many search problems can be sped up with sorting or building some other index structure Lowest common ancestor queries can be answered in constant time with linear ...
• 877
Accepted

### Online/approximate weighted and capacitated bipartite matching

I think there is no paper solving that exact problem, but "Online Vertex-Weighted Matching" by Aggarwal, Goel, Karande, and Mehta (2011) is very close. If I understood correctly, they solve your ...
• 7,738
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 ...
• 12.3k
1 vote

Here is what you are looking for. It is quite new: https://arxiv.org/pdf/1810.07362.pdf
• 167
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 \$...
• 10.9k
1 vote

### Competitive ratio of Move To Front in alternate access - List Update Problem

This question is given as an exercise in the textbook by Borodin and El-Yaniv. Unfortunately, it is impossible to solve. Indeed, it was later discovered that MTF-every-other-access is not 2-...

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