2 votes
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 ...
Neal Young's user avatar
  • 10.1k
2 votes
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.$$ ...
Neal Young's user avatar
  • 10.1k
2 votes
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 ...
kombinatorix's user avatar
2 votes

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 ...
adrianN's user avatar
  • 877
2 votes
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 ...
usul's user avatar
  • 7,615
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

Follow the Perturbed Leader for nonlinear cost functions

Here is what you are looking for. It is quite new: https://arxiv.org/pdf/1810.07362.pdf
user3680510's user avatar
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