Improving set intersection lexicographically 
Let $A=\{1,2,\dots,n\}$, and let $A_1,\dots,A_m$ be subsets of $A$ of the same size.
  Let $k$ be a fixed positive integer.
  We want to choose $B\subseteq A$ of size $k$ such that $\min(|A_1\cap B|,\dots,|A_m\cap B|)$ is maximized.

I'm not sure whether a direct approach to find such $B$ exists, so one way is to proceed greedily. First choose an arbitrary set $B$ of size $k$. Then, if possible, we try to "improve" it by replacing an element in $B$ with an element outside it.
If the criterion for improvement is that $\min(|A_1\cap B|,\dots,|A_m\cap B|)$ should increase, we may get stuck. For example $n=4$, $m=k=2$, $A_1=\{1\}$, $A_2=\{2\}$. Initially $B=\{3,4\}$, and we cannot improve using this criterion. Yet a better $B$ is $B=\{1,2\}$.
So, how about the improvement criterion being that the sequence $(|A_1\cap B|,\dots,|A_m\cap B|)$ improves lexicographically? For sequences $(a_1,\dots,a_r)$ and $(b_1,\dots,b_r)$, where we sort $a_1\leq\dots\leq a_r$ and $b_1\leq\dots\leq b_r$, we say that the latter improves the former if, for the first $i$ such that $b_i\neq a_i$, we have $b_i>a_i$. In the example above, we would change $B=\{3,4\}$ to $B=\{1,4\}$, then to $B=\{1,2\}$, resulting in a desired set $B$.
Does this algorithm always end with a desired set $B$, or can it get stuck?
 A: For me convergence of the proposed algorithm sounds too optimistic and indeed it can get stuck even in the following special case. 
Let $G$ be a graph with the set $V$ of vertices. Let $A_1,\dots, A_n$ be edges of $G$ considered as set of size two. If $G$ has a vertex cover of size $k$ then the required minimum is at least one. On the other hand, the algorithm can get stuck  in this case. Indeed, let $V$ be a disjoint union of set $V_1$ and $V_2$ of size four each. Let every vertex of $V_1$ is adjacent to every vertex of $V_2$ and the subgraph of $G$ induced on $V_1$ is a cycle of length four. Then $V_1$ is a vertex-cover of $G$. On the other hand, the algorithm get stuck at a set $V_2$, because it covers all edges of $G$ but four edges of the cycle, whereas each four-element subset $B$ of $V$ with $|B\cap V_2|=3$ covers all but five edges of $G$.
A: Dualize the problem. Build auxiliary sets $C_1,C_2,.., C_m$ that are subsets of $\{1,2,\dots, n\}$ such that $C_i$ contains $j$ if and only if $A_j$ contains $i$.
What happens if we solve the set cover problem with the sets $C_i$? The result is $k$ or less if and only if there is a solution to the original problem in which $\min(|A_1\cap B|,\dots,|A_m\cap B|)$ is at least $1$.
We conclude this problem is at least as hard as the set cover problem. (because moving the $k$ would allow us to solve the set cover problem).
A: The idea is to consider all of the different cases of the relation $|\cap_i A_i|\overset{?}{=} k $. We consider the easier case first as it makes the jump to the 2nd case easier:

Case #1 $|\cap_i A_i| \geq k $

Algorithm for Case #1: 


*

*While $|B|<k$
1.1. Search for any $x \in \cap_i A_i \setminus B$ 
1.2. Set $B := B \cup \{x \}$

Claim 2 Algorithm #1 is well-defined and optimal.
(Proof): The correctness of the algorithm follows from the fact that $|\cap_i A_i| \geq k $ and therefore there always exists some $x \in \cap_i A_i \setminus B$ in line 1.2 of the while loop. It is easy to see that see that $\min \{ |A_i \cap B| \ | \ i \in [m]\}$ is always smaller or equal to $|B|$ and furthermore it is also easy to see that the output of this algorithm gives us $|A_i \cap B| = |B|$ for all $i$; therefore the $B$ is optimal.

The remaining case is more difficult but it contains the crux of the problem:

Case #2 $|\cap_i A_i| <  k $

Algorithm for Case #2: 


*

*Set $B := \cap_i A_i$

*Set $I := [m]$

*While $|B|<k$
3.1. Search for the $x \in A \setminus B$ that mixmizes the number of $A_i$ it is contained in, i.e. $x$ maximizes $\#|\{ i \in I\ | \ x \in A_i \}|$
3.2. Set $B := B \cup \{x \}$
3.3. Set $I := I \setminus \{ i \in [m] \ | \ x \in  A_i \}$
3.3. If $I == \emptyset$ set $I := [m] \setminus \{ i \in [m] \ | \ |B\cap A_i| > |\min \{ |A_i \cap B| \ | \ i \in [m]\}| \}$

Claim 2 Algorithm #2 is well-defined and optimal.
(Proof): The correctness of the algorithm is trivial in this case, however the optimaility requires a bit more work. Suppose there were some $C = \{c_1,...,c_k\}$ that gave a better solution than $B = \{b_1,...,b_k\}$; we make a "matrix of labels," $\mathcal{N}^X$, for $X=A,B$ as follows: 
Algorithm #3 to construct matrix $\mathcal{N}^X$ 
Input: $X =  B,C$
  
  
*
  
*Let $\mathcal{N}^X$ be an arbitrarily large matrix of empty strings with potentially varying row lengths
  
*Set $I = [m]$
  
*While $X \neq \emptyset $ do 
3.1. search for $Y = \{y_1,...,y_l\} \subset X $ such that $|Y \cap A_i | = |Y \cap A_j |$ for all $i,j \in I $ and $|Y|$ is minimal
3.2. if such a $Y$ exists then do
  
  
*
  
*Set the next empty row of $\mathcal{N}^X$ equal to $(y_1,...,y_l)$, ordered according to the size of $\#|\{ i \in I\ | \ y_j \in A_i \}|$
  
*Set $X : = X \setminus \{y_1,...,y_l\}$
  
*Set $I := I \setminus \{ i \in [m] \ | \ (\exists y \in Y) \ y \in  A_i \}$
  
*If $I == \emptyset$ set $I := [m] \setminus \{ i \in [m] \ | \ |\mathcal{N}^X \cap A_i| > |\min \{ |A_i \cap \mathcal{N}^X| \ | \ i \in [m]\}| \}$ where we consider $\mathcal{N}^X$ as a set  
3.3. else do
  
  
*
  
*Set the next empty row of $\mathcal{N}^X$ equal to $(x_1,...,x_l) = X$
  
*Set $X : = \emptyset$
  
  
*delete all of the empty rows/labels in $\mathcal{N}^X$
The proof is completed by proving the following lemma:
Claim 3 The number of rows in $\mathcal{N}^X $ is equal to $\min \{ |A_i \cap X| \ | \ i \in [m]\}  $ or $\min \{ |A_i \cap X| \ | \ i \in [m]\}  + 1$.
(Proof):  We prove it by induction on the number of rows. For the base case notice that if Algorithm 3 halted before it created a second row then it found at most one set $Y = \{y_1,...,y_l\} \subset X $ such that $|Y \cap A_i | = |Y \cap A_j |$ and was not able to find a second $Y' = \{y_1,...,y_l\} \subset (X \setminus Y)$ that brought the value of $\min \{ |A_i \cap \mathcal{N}^X| \ | \ i \in [m]\}  $ up higher than 1; which proves the base case (because by the end of the algorithm $\mathcal{N}^X = X$ if considered as a set). Assume the induction hypothesis is true if the number of rows of $\mathcal{N}^X$ is equal to $1,...,l$. If we remove the $(l+1)^{th}$ row of $\mathcal{N}^X$ we have that the number of rows in $\mathcal{N}^X _{(1:l)}$ is equal to $\min \{ |A_i \cap (X \setminus \mathcal{N}^X _{l+1})| \ | \ i \in [m]\} +1   $ or $\min \{ |A_i \cap (X \setminus \mathcal{N}^X _{l+1})| \ | \ i \in [m]\}  $ by the induction hypothesis. If the number of rows in $\mathcal{N}^X _{(1:l)}$ is equal to $\min \{ |A_i \cap (X \setminus \mathcal{N}^X _{l+1})| \ | \ i \in [m]\} +1   $ then the last step of the algorithm can at most bring the value of $\min \{ |A_i \cap \mathcal{N}^X| \ | \ i \in [m]\}  $ up by one. Therefore 
$ l +1 =  \min \{ |A_i \cap (X \setminus \mathcal{N}^X _{l+1})| \ | \ i \in [m]\} +2  \geq \min \{ |A_i \cap \mathcal{N}^X| \ | \ i \in [m]\}   + 1 = \min \{ |A_i \cap X| \ | \ i \in [m]\}   + 1 $
where the last inequality is at most a difference by 1; as was needed to be shown. If the number of rows in $\mathcal{N}^B _{(1:l)}$ is equal to $\min \{ |A_i \cap (X \setminus \mathcal{N}^X _{l+1})| \ | \ i \in [m]\}   $ then by similar reasoning we have that
$ l +1 =  \min \{ |A_i \cap (X \setminus \mathcal{N}^X _{l+1})| \ | \ i \in [m]\} +1  \leq \min \{ |A_i \cap \mathcal{N}^X| \ | \ i \in [m]\}   + 1 = \min \{ |A_i \cap X| \ | \ i \in [m]\}   + 1 $
where the last inequality is at most a difference by 1; which completes the proof.

Claim 3 completes Claim 2 because it is straight forward to see that the output of Algorithm 2 maximizes the output of Algorithm 3; indeed if $B$ is the output of Algorithm 2 then it is easy to see that $\mathcal{N}^B$ will have the maximum number of rows because Algorithm 2 essentially performs the same steps as Algorithm 3 except that it has all of $A$ to choose from. In particular, we have that 

Claim 4 If $B$ is the output of Algorithm #2 then $\mathcal{N}^B$ has the maximum number of rows for any set $X$ such that $|X| = |B|$. 

(Proof sketch): Spelled out explicitly, if $C$ is any other solution we see that at, after possibly reordering $C$, every step where a new row is created in Algorithm 3 the corresponding steps for Algorithm 2 will find the smallest $Y$ that will make $\min \{ |A_i \cap (\mathcal{N}^C \cup Y)| \ | \ i \in [m]\} $ go up by one (if it exists). Therefore Algorithm 2 will always find the optimal "completion" of a set and the proof is completed by a simple induction. 

Answer to your question about greedy algorithm Yes a greedy solution works but you must be careful. Your locally optimal choices (or replacements) should either be 



*

*Search for any $x \in \cap_i A_i \setminus B$

or when you run out of those



*Search for the $x \in A \setminus B$ that maximizes the number of $A_i$ it is contained in, for the $i$ such that $ i \notin \{ j \in [m] \ | \ |B\cap A_j| > |\min \{ |A_j \cap B| \ | \ j \in [m]\}| \}$

as given in algorithms 1 and 2 respectively. 

