Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates

Details Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates

2012-03-28

arxiv.org/abs/1203.6397v1

Computer Science

Data Structures and Algorithms

Scientific paper

Result diversification has many important applications in databases, operations research, information retrieval, and finance. In this paper, we study and extend a particular version of result diversification, known as max-sum diversification. More specifically, we consider the setting where we are given a set of elements in a metric space and a set valuation function $f$ defined on every subset. For any given subset $S$, the overall objective is a linear combination of $f(S)$ and the sum of the distances induced by $S$. The goal is to find a subset $S$ satisfying some constraints that maximizes the overall objective. This problem is first studied by Gollapudi and Sharma for modular set functions and for sets satisfying a cardinality constraint. We consider an extension of the modular case to the monotone submodular case, for which the previous algorithm no longer applies. Interestingly, we are able to match the 2-approximation using a natural, but different greedy algorithm. We then further extend the problem by considering any matroid constraint and show that a natural single swap local search algorithm provides a 2-approximation in this more general setting. The second part of the paper focuses on dynamic updates for the modular case. Suppose we have a good initial approximate solution and then there is a single weight-perturbation either on the valuation of an element or on the distance between two elements. Given that users expect some stability in the results they see, we ask how easy is it to maintain a good approximation without significantly changing the initial set. We measure this by the number of updates, where each update is a swap of a single element in the current solution with a single element outside the current solution. We show that we can maintain an approximation ratio of 3 by just a single update if the perturbation is not too large.

Affiliated with

Also associated with

No associations

Rating

Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-56932