Maximizing a Nonnegative, Monotone, Submodular Function Constrained to
  Matchings
  Submodular functions have many applications. Matchings have many
applications. The bitext word alignment problem can be modeled as the problem
of maximizing a nonnegative, monotone, submodular function constrained to
matchings in a complete bipartite graph where each vertex corresponds to a word
in the two input sentences and each edge represents a potential word-to-word
translation. We propose a more general problem of maximizing a nonnegative,
monotone, submodular function defined on the edge set of a complete graph
constrained to matchings; we call this problem the CSM-Matching problem.
CSM-Matching also generalizes the maximum-weight matching problem, which has a
polynomial-time algorithm; however, we show that it is NP-hard to approximate
CSM-Matching within a factor of e/(e-1) by reducing the max k-cover problem to
it. Our main result is a simple, greedy, 3-approximation algorithm for
CSM-Matching. Then we reduce CSM-Matching to maximizing a nonnegative,
monotone, submodular function over two matroids, i.e., CSM-2-Matroids.
CSM-2-Matroids has a (2+epsilon)-approximation algorithm - called LSV2. We show
that we can find a (4+epsilon)-approximate solution to CSM-Matching using LSV2.
We extend this approach to similar problems.
