We formally define the lexical overlap of a dataset D as where is the number of problem pairs in D. Given a dataset D and a target subset size k, MAWPS automatically finds a subset D of reduced lexical overlap by solving the following optimization problem: This is the remote clique problem 1 , which is NP hard.
we resort to a greedy strategy which gives an approximation ratio of 2 (Birnbaum and Goldman, 2007).