NDLI: Max-Sum diversification, monotone submodular functions and dynamic updates

Please wait, while we are loading the content...

What next?: a half-dozen data management research goals for big data and the cloud

Graph sketches: sparsification, spanners, and subgraphs

The ACM PODS Alberto O. Mendelzon test-of-time award 2012

Linguistic foundations for bidirectional transformations: invited tutorial

The power of the dinur-nissim algorithm: breaking privacy of statistical and graph databases

Space-efficient range reporting for categorical data

Approximate computation and implicit regularization for very large-scale data analysis

Query-based data pricing

The wavelet trie: maintaining an indexed sequence of strings in compressed space

Classification of annotation semirings over query containment

Space-efficient estimation of statistics over sub-sampled streams

Approximating and testing k-histogram distributions in sub-linear time

Worst-case optimal join algorithms: [extended abstract]

A rigorous and customizable framework for privacy

Dynamic top-k range reporting in external memory

Max-Sum diversification, monotone submodular functions and dynamic updates

Local transformations and conjunctive-query equivalence

On the optimality of clustering properties of space filling curves

Efficient approximations of conjunctive queries

Rectangle-efficient aggregation in spatial data streams

Mergeable summaries

Deterministic regular expressions in linear time

Static analysis and optimization of semantic web queries

Indexability of 2D range search revisited: constant redundancy and weak indivisibility

A dichotomy in the complexity of deletion propagation with functional dependencies

Nearest-neighbor searching under uncertainty

On the complexity of package recommendation problems

Randomized algorithms for tracking distributed count, frequencies, and ranks

The complexity of evaluating path expressions in SPARQL

Continuous distributed counting for non-monotonic streams

Max-Sum diversification, monotone submodular functions and dynamic updates

Content Provider	ACM Digital Library
Author	Lee, Hyun Chul Borodin, Allan Ye, Yuli
Abstract	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 in [17] for modular set functions and for sets satisfying a cardinality constraint (uniform matroids). In their paper, they give a 2-approximation algorithm by reducing to an earlier result in [20]. The first part of this paper considers an extension of the modular case to the monotone submodular case, for which the algorithm in [17] no longer applies. Interestingly, we are able to maintain the same 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. This extends the Nemhauser, Wolsey and Fisher approximation result [20] for the problem of submodular function maximization subject to a matroid constraint (without the distance function component). 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.
Starting Page	155
Ending Page	166
Page Count	12
File Format	PDF
ISBN	9781450312486
DOI	10.1145/2213556.2213580
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Local search Ranking Submodular functions Greedy algorithm Matroids Information retrieval Approximation algorithm Diversification Dynamic update
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Max-sum diversification, monotone submodular functions and dynamic updates (extended abstract) (2012).

Max-sum diversification, monotone submodular functions and dynamic updates

Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates

Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

Monotone submodular maximization over a matroid via non-oblivious local search (2012).

Monotone submodular maximization over a matroid via non-oblivious local search (2013).

Monotone submodular maximization over a matroid via non-oblivious local search (2014).

Maximizing non-monotone submodular functions (2007)

Max-Sum diversification, monotone submodular functions and dynamic updates

Similar Documents

Max-sum diversification, monotone submodular functions and dynamic updates (extended abstract) (2012).

Max-sum diversification, monotone submodular functions and dynamic updates

Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates

Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

Monotone submodular maximization over a matroid via non-oblivious local search (2012).

Monotone submodular maximization over a matroid via non-oblivious local search (2013).

Monotone submodular maximization over a matroid via non-oblivious local search (2014).

Maximizing non-monotone submodular functions (2007)

Max-Sum diversification, monotone submodular functions and dynamic updates