  We consider a general task called partial Wasserstein covering with the goal
of providing information on what patterns are not being taken into account in a
dataset (e.g., dataset used during development) compared with another
dataset(e.g., dataset obtained from actual applications). We model this task as
a discrete optimization problem with partial Wasserstein divergence as an
objective function. Although this problem is NP-hard, we prove that it
satisfies the submodular property, allowing us to use a greedy algorithm with a
0.63 approximation. However, the greedy algorithm is still inefficient because
it requires solving linear programming for each objective function evaluation.
To overcome this inefficiency, we propose quasi-greedy algorithms that consist
of a series of acceleration techniques, such as sensitivity analysis based on
strong duality and the so-called C-transform in the optimal transport field.
Experimentally, we demonstrate that we can efficiently fill in the gaps between
the two datasets and find missing scene in real driving scenes datasets.
