19

I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution." For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual ...


10

The most common use of 'fractional' is when you're solving an integer program. You relax it by dropping the constraints that the solution be integers, thus yielding a linear program in which the variables can take fractional values (fractional comes from fraction). Later, you can convert the fractional values into integers via a process called 'rounding'.


7

In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following: Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space. Approximate bit counting on a sliding ...


7

A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack. See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. ) About how to maintain on stacks: Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one ...


6

Brute-force case analysis reveals that the optimal competitive ratio for the special case $n=3$, with no other restrictions on the cost matrix, is the golden ratio $\phi = (\sqrt{5}+1)/2$. Thus, no online algorithm can achieve a competitive ratio better than $\phi$. Suppose $C_{1,2}=0$, $C_{1,3}=1$, and $C_{2,3}=\phi$. Without loss of generality, the ...


4

There are several algorithms for estimating cardinality. This problem seems to be important enough in practice. For example, Redis, which describes itself as a ‘data structure server’, supports it. I suspect students would find this a good motivation. The algorithm that Redis uses, HyperLogLog, may be too difficult to analyze in an undergrad course. But, ...


3

the question does not seem to have been studied much (one possibility is attempting to find a relationship with a "nearby" complexity class say P/poly etc); although here is at least one ref that touches on it: Language operations with regular expressions of polynomial size Gruber/Holzer This work deals with questions regarding to what extent regularity-...


2

It seems that there are no recent books or survey papers on online algorithms.


2

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 together in bin $i$. It chooses any largest such set, say $A_i$, then assigns all balls in $A_i$ to bin $i$. The post asks for an algorithm that each ball can use ...


2

@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.$$ This instance has just one solution (one $p$ that satisfies it), namely $p=(1,1,1)$. So, given $B=3$ and $L=8$ and just the first factor $1+p_1$, the algorithm ...


2

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 and System Sciences 8.3 (1974): 272-314. and Johnson, David S. Near-optimal bin packing algorithms. Diss. Massachusetts Institute of Technology, 1973.


2

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 preprocessing. Lots of text problems can be sped up with some preprocessing, e.g. building a suffix array


2

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 problem only with all capacities equal to one. My best guess is that you will have to do some work to extend their guarantees and algorithm to your setting. On the ...


2

If you allow randomization, the CountMin (CM) sketch can be used with weights without modification, and can also handle negative weights. When all weights are positive, the standard analysis of CM shows that with a sketch of size $O(\varepsilon^{-1}\log 1/\delta)$ you can compute a $\tilde{w}_i$ so that $\tilde{w_i} \geq w_i$ always, and $\tilde{w}_i \leq ...


2

Here's a generic randomized solution. (Do we even have deterministic solutions in the unweighted case? Don't Space Saving and Batch Decrement both need hash maps?) This is probably not the ideal solution, but it's a start. Weighted Heavy Hitters Algorithm. Input: $S=\{(\text{id}_i,\text{weight}_i)\}_{i=1}^N$ a weighted stream. 1. Create an unweighted ...


2

Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree. Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$. Now at most one downward path (of length $O(\log n)$) reports no ...


1

If I understand your question correctly and the elements arrive in sorted order, I believe the usual bottom-up AVL tree insertion algorithm meets your criteria. In particular, insert-only AVL trees have $O(1)$ amortized (and $O(\lg n)$ worst-case) update time. Simply maintain a pointer to the last element of the tree and perform each insertion at that ...


1

Here is what you are looking for. It is quite new: https://arxiv.org/pdf/1810.07362.pdf


1

Another reason for not using cryptographic algorithms in practice is speed. In the streaming setting, we typically do not want to spend too long processing each item in the stream. Computing k cryptographic hash functions will be much more expensive than computing k fast non-cryptographic hash functions, e.g. MurmurHash. In practice, I think most people use ...


1

The obvious problem is that if you use a cryptographic pseudorandom number generator (PRNG), the correctness of your algorithm is conditional on a complexity conjecture. However, usually this can be avoided, because the full strength of cryptographic pseudorandmness is usually a huge overkill for streaming. If your streaming algorithm uses a small amount of ...


1

You can solve this in $O(n \lg n)$ time through an appropriate use of interval trees. I'm going to explain how to process the $x$'s in an incremental, streaming fashion. So, suppose we've already received $x_1,\dots,x_n$. Define the sequence $m_1,\dots,m_n$ by $m_i=\max(x_i,x_{i+1},\dots,x_n)$. In previous processing, we'll have accumulated a data ...


1

You can solve this in $O(n \lg^2 n)$ time. Build a (balanced) binary tree with $n$ nodes, where the leaves are annotated with the values $x_1,x_2,\dots,x_n$, and $x_i$ is placed on the $i$th leaf from the left. Annotate each internal node $v$ in the tree with the maximum value over all the leaves in the subtree rooted at $v$. For instance, the root is ...


1

I am still unclear about the precise objective you want to optimise over, but you could look at Peter Brucker, Andreas Drexl, Rolf Möhring, Klaus Neumann, and Erwin Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research 112 3–41, 1999. doi:10.1016/S0377-2217(98)00204-5 for a ...


1

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-competitive. See arxiv.org/abs/1311.7357 for a proof that the competitive ratio of the algorithm is in fact 2.5, and for a history of the false belief that the algorithm ...


1

T. Wagners dissertation is about "Incremental Software Development Environments". You can find a bunch of resources at the Harmonia and Ensemble Homepage


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