Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates

Summary: Extends max-sum diversification to monotone submodular valuations: a natural greedy yields a 2-approx for cardinality constraints and a single-swap local search gives a 2-approx for arbitrary matroids (extending Nemhauser–Wolsey–Fisher). For dynamic single-element or pairwise distance perturbations in the modular case, shows stability via at most one swap to maintain a 3-approx for bounded perturbations, measuring robustness by swap count. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1573
Venue: PODS
Year: 2012
Pagerank: 9.5010932e-05
Overall Rank: 1,908 | 86.92%
DOI: 10.1145/2213556.2213580

Incoming Non-self Citations Over Time

Authors

1. Allan Borodin (University of Toronto)
2. Hyun Chul Lee (LinkedIn)
3. Yuli Ye (University of Toronto)

BibTeX Citation

@inproceedings{borodin_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213580},
        doi = {10.1145/2213556.2213580},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Borodin, Allan and Lee, Hyun Chul and Ye, Yuli},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,807	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.7054469e-05
2,959	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS	7.9182968e-05
3,596	On the Complexity of Query Result Diversification	2013	VLDB	7.2722683e-05
3,908	Diversified Top-k Graph Pattern Matching	2013	VLDB	7.0262215e-05
4,631	Interactive Summarization and Exploration of Top Aggregate Query Answers	2018	VLDB	6.595034e-05
7,992	Diversity-Aware Top-k Publish/Subscribe for Text Stream	2015	SIGMOD	5.5098908e-05
8,728	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS	5.3766157e-05
8,917	A Blockchain System for Clustered Federated Learning with Peer-to-Peer Knowledge Transfer	2024	VLDB	5.3483178e-05
10,441	Data-Semantics-Aware Recommendation of Diverse Pivot Tables	2026	SIGMOD	5.093636e-05
11,170	Counterfactual Explanation at Will, with Zero Privacy Leakage	2024	SIGMOD	5.093636e-05
11,175	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,379	Structured Search Result Differentiation	2009	VLDB	8.666326e-05
4,967	DivDB: A System for Diversifying Query Results	2011	VLDB	6.4214182e-05
5,553	BROAD: Diversified Keyword Search in Databases	2011	VLDB	6.1777883e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,103	The Computation of Optimal Subset Repairs	2020	VLDB
2	3,700	Approximate MaxRS in Spatial Databases	2013	VLDB
3	9,849	Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization	2021	VLDB
4	3,596	On the Complexity of Query Result Diversification	2013	VLDB
5	9,899	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS
6	11,175	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD
7	7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS
8	10,305	Weighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation	2026	SIGMOD
9	2,959	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS
10	5,847	MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension	2017	VLDB