New answers tagged lower-bounds
1
One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it. This will output all of the minimal sets. The running time is $O(nk)$ set comparisons plus $O(n \log n)$ steps for sorting, where $n$ is the number of sets you have and $k$ is ...
0
I have found a solution in this paper, p.12.
The algorithm mentioned there as proof should translate to the following python code:
T = set([]);
for x in X:
rem = set([]);
spe = False;
for a in T:
rel = oracle(x,a);
if rel == "x>a":
spe = True;
break;
elif rel == "x<a":
rem.add(a);...
Top 50 recent answers are included
