  Diverse keyword suggestions for a given landing page or matching queries to
diverse documents is an active research area in online advertising. Modern
search engines provide advertisers with products like Dynamic Search Ads and
Smart Campaigns where they extract meaningful keywords/phrases from the
advertiser's product inventory. These keywords/phrases are representative of a
diverse spectrum of advertiser's interests. In this paper, we address the
problem of obtaining relevant yet diverse keywords/phrases for any given
document. We formulate this as an optimization problem, maximizing the
parameterized trade-off between diversity and relevance constrained over number
of possible keywords/phrases. We show that this is a combinatorial NP-hard
optimization problem. We propose two approaches based on convex relaxations
varying in complexity and performance. In the first approach, we show that the
optimization problem reduces to an eigen value problem. In the second approach,
we show that the optimization problem reduces to minimizing a quadratic form
over an l1-ball. Subsequently, we show that this is equivalent to a
semi-definite optimization problem. To prove the efficacy of our proposed
formulation, we evaluate it on various real-world datasets and compare it to
the state-of-the-art heuristic approaches.
