Back to papers
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
- 1574
- Venue
- PODS
- Year
- 2012
- Pagerank
- 0.00010768447
- Overall Rank
- 1,717 | 88.07%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 1,984 |
DisC Diversity: Result Diversification based on Dissimilarity and Coverage |
2013 |
VLDB |
9.8645751e-05 |
| 2,756 |
Composable Core-sets for Diversity and Coverage Maximization |
2014 |
PODS |
8.1682323e-05 |
| 4,060 |
On the Complexity of Query Result Diversification |
2013 |
VLDB |
6.4840236e-05 |
| 4,608 |
Interactive Summarization and Exploration of Top Aggregate Query Answers |
2018 |
VLDB |
6.046643e-05 |
| 4,748 |
Diversified Top-k Graph Pattern Matching |
2013 |
VLDB |
5.9432853e-05 |
| 8,028 |
Diversity-Aware Top-k Publish/Subscribe for Text Stream |
2015 |
SIGMOD |
4.5985485e-05 |
| 8,521 |
Computing A Well-Representative Summary of Conjunctive Query Results |
2024 |
PODS |
4.4893996e-05 |
| 8,743 |
A Blockchain System for Clustered Federated Learning with Peer-to-Peer Knowledge Transfer |
2024 |
VLDB |
4.4520434e-05 |
| 10,152 |
Data-Semantics-Aware Recommendation of Diverse Pivot Tables |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,957 |
Counterfactual Explanation at Will, with Zero Privacy Leakage |
2024 |
SIGMOD |
4.1905499e-05 |
| 10,964 |
Faster Algorithms for Fair Max-Min Diversification in Rd |
2024 |
SIGMOD |
4.1905499e-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.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 9,999 |
A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions |
2026 |
PODS |
4.1905499e-05 |
| 8,014 |
The Computation of Optimal Subset Repairs |
2020 |
VLDB |
4.6020746e-05 |
| 3,842 |
Approximate MaxRS in Spatial Databases |
2013 |
VLDB |
6.7082659e-05 |
| 9,712 |
Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization |
2021 |
VLDB |
4.2951473e-05 |
| 4,060 |
On the Complexity of Query Result Diversification |
2013 |
VLDB |
6.4840236e-05 |
| 9,753 |
Minimum Coresets for Maxima Representation of Multidimensional Data |
2021 |
PODS |
4.2856385e-05 |
| 10,964 |
Faster Algorithms for Fair Max-Min Diversification in Rd |
2024 |
SIGMOD |
4.1905499e-05 |
| 6,758 |
Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives |
2019 |
PODS |
4.9335749e-05 |
| 2,756 |
Composable Core-sets for Diversity and Coverage Maximization |
2014 |
PODS |
8.1682323e-05 |
| 5,888 |
MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension |
2017 |
VLDB |
5.2843653e-05 |