Algorithm to answer questions on dominated input Consider a setting where we see inputs one-by-one, with each input being an $n$-tuple $(a_1,a_2,...,a_n)$, where each $a_i\in\{0,1\}$. For each new input we see, we have to answer two questions:
1) Have we seen this input before?
2) Is the input dominated by some input we've seen before? (An input $A=(a_1,\ldots,a_n)$ is said to be dominated by an input $B=(b_1,\ldots,b_n)$ if $a_i\leq b_i$ for all $i$.)
How fast can we answer these two questions for each input?
For question 1), we can use a hash table. We check whether the input has been seen before in $O(1)$ time, and if not, insert the input into the hash table in $O(1)$ time.
To accommodate question 2), the trivial way is to compare the new input with each one of the previous inputs, which would take $O(k)$ time, where $k$ is the number of elements in the hash table. This could be up to $O(2^n)$ time. Is there a way to reduce this to something polynomial in $n$?
 A: If we treat each $n$-tuple as a subset of $1,2,\ldots, n$ in the natural way, then we see that $A$ dominates $B$ if $B$ is a subset of $A$. The paper "New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems" (pdf) by Charikar, Indyk, and Panigrahy presents some time/space tradeoff results for this problem.
A: I 'll take it you mean $a_i\in (0,1)$ not $\{0,1\}$ because this is a binary string. Non the less, what I am thinking apllies to both cases.
Since you get your tuples one by one we will sort them with an insertion sort algorithm a little modified to sort the tuples lexicographically . This is like a dictionary, e.g. $(1, 0.5, 0.4) \geq (1, 0.6, 1)\geq(0.9, 1,0.6)$ because: $0.5<0.6$.
Leaving the details,
1) when a tuple is sorted in its place it can only be identical with the ones adjacent to it, which is easy to check.
2) Starting from the last tuple and going up, check if each tuple is dominated by its previous. If $A$ and $B$ are two tuples and $A$ dominates $B$ then for sure $a_1\geq b_1$ and $A\geq B$, $A$ must be greater than $B$ to dominate $B$.
The overall time of insertion sort is $O(n^2)$ and the checks can be performes in linear time after the inputs are sorted.
