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.00010748322
- Overall Rank
- 1,725 | 88.01%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 2,000 |
DisC Diversity: Result Diversification based on Dissimilarity and Coverage |
2013 |
VLDB |
9.8229527e-05 |
| 2,752 |
Composable Core-sets for Diversity and Coverage Maximization |
2014 |
PODS |
8.1742326e-05 |
| 4,056 |
On the Complexity of Query Result Diversification |
2013 |
VLDB |
6.4883623e-05 |
| 4,614 |
Interactive Summarization and Exploration of Top Aggregate Query Answers |
2018 |
VLDB |
6.0467204e-05 |
| 4,807 |
Diversified Top-k Graph Pattern Matching |
2013 |
VLDB |
5.9092289e-05 |
| 8,027 |
Diversity-Aware Top-k Publish/Subscribe for Text Stream |
2015 |
SIGMOD |
4.6029624e-05 |
| 8,747 |
A Blockchain System for Clustered Federated Learning with Peer-to-Peer Knowledge Transfer |
2024 |
VLDB |
4.456315e-05 |
| 10,152 |
Data-Semantics-Aware Recommendation of Diverse Pivot Tables |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,927 |
Computing A Well-Representative Summary of Conjunctive Query Results |
2024 |
PODS |
4.1945683e-05 |
| 10,954 |
Counterfactual Explanation at Will, with Zero Privacy Leakage |
2024 |
SIGMOD |
4.1945683e-05 |
| 10,961 |
Faster Algorithms for Fair Max-Min Diversification in Rd |
2024 |
SIGMOD |
4.1945683e-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 |
| 10,000 |
A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions |
2026 |
PODS |
4.1945683e-05 |
| 7,605 |
The Computation of Optimal Subset Repairs |
2020 |
VLDB |
4.697534e-05 |
| 3,805 |
Approximate MaxRS in Spatial Databases |
2013 |
VLDB |
6.7521192e-05 |
| 9,713 |
Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization |
2021 |
VLDB |
4.299267e-05 |
| 4,056 |
On the Complexity of Query Result Diversification |
2013 |
VLDB |
6.4883623e-05 |
| 9,772 |
Minimum Coresets for Maxima Representation of Multidimensional Data |
2021 |
PODS |
4.2856106e-05 |
| 10,961 |
Faster Algorithms for Fair Max-Min Diversification in Rd |
2024 |
SIGMOD |
4.1945683e-05 |
| 6,755 |
Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives |
2019 |
PODS |
4.9383139e-05 |
| 2,752 |
Composable Core-sets for Diversity and Coverage Maximization |
2014 |
PODS |
8.1742326e-05 |
| 5,883 |
MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension |
2017 |
VLDB |
5.2890537e-05 |