Fair Diversity Maximization with Few Representatives

Florian Adriaens; Nikolaj Tatti

REVIEW 3 major objections 5 minor 45 references

Fair Diversity Maximization with Few Representatives

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper's central claim is that when $k \le m$, a randomized algorithm based on padded decompositions approximates fair max-min diversification within a factor of $\sqrt{\log m}/(3m)$, improving the previous best polynomial-time factor…

desk verdict Good idea, solid proofs around a load-bearing parameter typo: Algorithm 2 defines α differently from what the proof of Prop 4 requires, so the main theorem as written is false; the fix is simple and the paper deserves review. read the letter →

arxiv 2506.08110 v1 pith:7T2WCXML submitted 2025-06-09 cs.DS

Florian Adriaens , Nikolaj Tatti This is my paper

classification cs.DS

keywords fairdiversitymaximizationmax-mindiversificationpaddeddecompositionsrandomizedalgorithmsapproximationCKRpartitionsfairnessconstraints

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks: when a dataset is partitioned into $m$ labeled groups, how can one select $k$ items so that the smallest pairwise distance is as large as possible while each group stays within its lower and upper representation bounds? Its central claim is that in the 'few representatives' regime ($k \le m$), a randomized algorithm called Breach approximates this fair max-min diversification problem within a factor of $\sqrt{\log m}/(3m)$ in polynomial time, improving the previous best polynomial-time guarantee of roughly $1/(m+1)$. The improvement matters because many applications—forming committees, siting facilities, summarizing documents—want only a handful of representatives per category, and a provably larger minimum distance means a more spread-out, more useful selection. The paper proves the guarantee through a three-stage pipeline and confirms on real datasets that it matches or beats existing polynomial-time methods.

What carries the argument

The engine is the CKR random partition (a standard padded decomposition of a metric space into random clusters with bounded diameter), applied with parameter $\alpha = \sqrt{\log m/m}$. The decomposition builds a graph on points with edges between points closer than $\gamma\alpha$, orders the points by a random permutation, and carves out clusters as BFS balls of a random radius; vertices on cluster boundaries are discarded as guards. Two facts make the argument work: any cluster ball of radius $\Delta_2$ has diameter below $\gamma$ by the triangle inequality, so after pruning it contains at most one point of each color (at most $m$ points total), and a known bound on the probability that a given point becomes a guard yields a per-point survival probability that compounds to $\Omega(1/m)$ across the $k$ points of an optimal solution. The assignment phase is an integral max-flow network with a node per cluster and per color, plus a slack node $z$ that absorbs the difference between lower and upper bounds, which is what allows general $\ell_i \le |S \cap V_i| \le u_i$ constraints rather than exact quotas.

What would settle it

On a small metric instance (say $n \le 12$ points, $m \le 4$ colors, $k \le m$), compute the optimal FMMD value by exhaustive search, run Breach with the stated parameters for many repetitions, and record the worst ratio of the output's diversity to the optimum; a ratio below $\sqrt{\log m}/(3m)$ within the claimed failure regime would refute Theorem 1.

Watch

Extended reading notes

Core claim

The central result is Theorem 1: if $k \le m$, Algorithm 4 (Breach) runs in polynomial time and, with high probability, returns a feasible set whose diversity score is at least $\sqrt{\log m}/(3m)$ times the optimum for the fair max-min diversification problem with lower and upper bounds $\ell_i, u_i$ per color. The algorithm first prunes each color so that same-color points are at distance at least a threshold; it then randomly decomposes the pruned space into clusters using a CKR padded partition and removes boundary 'guard' points, so that any two surviving clusters are at distance at least $\gamma\alpha$ with $\alpha = \sqrt{\log m/m}$; finally, a max-flow network assigns clusters to colors and extracts one point per chosen cluster, which yields a feasible solution whenever one exists in the decomposition. The proof shows that an optimal solution survives the decomposition with probability $\Omega(1/m)$, and that any set with at most one point per surviving cluster is automatically diverse.

Load-bearing premise

The load-bearing premise is that distances obey the triangle inequality: the pruning step relies on it to map distinct optimal points to distinct surviving points, and the decomposition relies on it to conclude that a cluster ball contains at most one point of each color.

Editorial extensions

If this is right

Any application that needs at most one or a few representatives per category—committee formation, facility siting, document summarization—can now guarantee a minimum pairwise distance within $\sqrt{\log m}/(3m)$ of optimal in polynomial time, where the old guarantee was only about $1/(m+1)$.
Because the flow assignment handles arbitrary lower and upper bounds, the algorithm covers fairness constraints that the earlier exact-quota methods did not, so the theoretical improvement extends to the full FMMD problem as defined in the paper.
The two parameter settings give a user a trade-off: the $O(T m^2 n^2)$ version with ratio $\sqrt{\log m}/(3m)$, or the faster $O(k m n + T m^3 k^2)$ version with ratio $\sqrt{\log m}/(5m)$, both polynomial and practical on the tested datasets.
The guarantee extends to $k > m$ by adding $k-m$ artificial empty colors, so the polynomial-time algorithm covers the entire FMMD problem, with the ratio degrading smoothly to $\sqrt{\log m'}/(3m')$ for $m' = \max(k,m)$.
The success probability can be amplified to $1 - 2^{-\Omega(T)}$ by repeating the random decomposition $T m$ times, so the high-probability guarantee is robust.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The $\sqrt{\log m}$ factor is characteristic of padded-decomposition arguments, so a deterministic alternative would likely need a different technique to remove the log factor; a natural test is whether the decomposition's guard probability can be improved for structured metrics such as Euclidean spaces.
The flow-assignment stage is agnostic to how clusters are produced, so the same decomposition-plus-flow recipe might apply to other constrained diversity objectives, such as fair max-sum diversification, by replacing only the assignment network.
The paper's experiments show a few iterations suffice in practice, suggesting the worst-case $\Omega(1/m)$ survival probability is pessimistic; a tighter empirical or average-case analysis could reduce the $T m$ repetitions without hurting the guarantee.
For $k$ proportional to $m$ ($k \le \beta m$), the paper notes the success probability drops to $\Omega(1/m^\beta)$, so the method degrades in repetitions as $\beta$ grows; closing this gap for linear $k$ would extend the few-representatives regime substantially.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The real contribution here is using CKR padded decompositions for max-min fair diversity, and the flow network that handles general interval fairness constraints. The high-level cluster-then-assign structure isn't new—it follows Addanki et al. and Moumoulidou et al.—but the decomposition technique and the generality of the constraints are. The proofs of Props 2, 3, 5, and 6 are clean, and the assignment flow argument in Prop 6 is correct. If the central claim holds, the improvement from 1/(m+1) to sqrt(log m)/(3m) in the few-representatives regime is a real step forward.

The problem is that the central claim doesn't hold for the algorithm as written. Algorithm 2 sets α = sqrt(log m / m), but the proof of Prop 4 needs α = sqrt(log m) / m. With the printed α, the bound log m ≥ 2ωm fails: ωm grows like sqrt(m log m) log(m), not o(log m). For m=2, Δ2 becomes 0, breaking the interval for R. So the success probability Ω(1/m) and the repeated-trial argument in Prop 7 are not justified. The reader's take treated this as a minor typo in the direction of a product inequality; it's actually a parameter mismatch between the algorithm and the analysis. The good news is that changing α to sqrt(log m)/m fixes it, and the rest of the proof then closes. But Theorem 1 as stated is false for the algorithm in the text.

The experiments are suggestive but not fully controlled. The paper admits that the headline comparison is partially explained by looser constraints on Breach, and the promised results with identical constraints are not shown. That's a presentation gap, not a fatal flaw.

All of this is addressable. The idea is sound, the analysis framework is mostly rigorous, and the fix is a one-line change. I'd send this to peer review, with a specific request that the authors correct α, verify the bounds hold for small m, and show the same-constraint experiments. It deserves a serious referee despite the current error.

Referee Report

3 major / 5 minor

Summary. The paper studies the fair max-min diversification (FMMD) problem in the regime where each color contributes at most a few representatives (k ≤ m). It proposes a randomized algorithm, Breach, built in three phases: a preprocessing step that prunes each color so that same-color points are well separated; a random CKR-style padded decomposition with a set of 'guard' vertices removed; and a maximum-flow assignment that maps clusters to colors while respecting the interval constraints. The main theoretical claim, Theorem 1, is that when k ≤ m, Breach approximates FMMD within a factor of sqrt(log m)/(3m) in polynomial time, improving on the previous polynomial-time 1/(m+1) bound by a factor of Theta(sqrt(log m)). Two variants are given: a slower one with ratio sqrt(log m)/(3m) and a faster one with ratio sqrt(log m)/(5m). The paper also reports experiments on four real-world datasets and synthetic data, comparing Breach with FairFlow, GreedyFlow, and the coreset-based Core algorithm.

Significance. If the main theorem holds, this is a genuine asymptotic improvement over the state of the art for polynomial-time FMMD approximation in the few-representatives regime. The CKR-partition approach is an interesting and non-obvious technique for this problem, and the flow-based assignment is a clean way to handle the general interval constraints rather than the exact-size constraints studied in prior work. The availability of source code and the experimental comparison with existing baselines are also strengths. However, the main guarantee as stated is not established for the algorithm as printed, because the definition of alpha in Algorithm 2 and Section 3.2 does not match the value of alpha used in the proofs. This is a load-bearing inconsistency that a revision must fix. The core idea is sound and the required fix appears local, so the paper merits a major revision rather than rejection.

major comments (3)

[Section 3.2, Algorithm 2, Propositions 4, 5, and 7] There is a parameter mismatch in the definition of alpha. Algorithm 2 line 1 and Section 3.2 define alpha = sqrt(log m / m), but the proofs of Propositions 4 and 5 and the ratio in Proposition 7 require alpha = sqrt(log m) / m. With the printed value, the key inequality log m >= 2*omega*m from Proposition 4 fails for all sufficiently large m: since omega = 4*alpha*log(4*m*alpha), we get omega*m = 4*sqrt(m*log m)*log(4*sqrt(m*log m)), so at m = 10^6, log m is about 13.8 while 2*omega*m is about 2.86*10^5. The chain (1-omega)^k >= exp(-omega*m/(1-omega)) >= 1/m, and with it the claimed Omega(1/m) success probability, therefore does not follow. In addition, for m = 2 the printed value gives Delta_2 = floor(1/(2*alpha)) = 0 while Delta_1 = 1, so R is drawn from an empty interval. Replacing alpha by sqrt(log m)/m makes Delta_2 = floor(m/(2*sqrt(log m))) >= 1 and gives omega*m = 4*sqrt(log m)*log(4*sqrt(log m)) = o(log m), which closes the proof. Consequently, the algorithm whose guarantee is proved is not the algorithm stated in the text.
[Proposition 4, proof] The displayed chain for the probability that O has no guards has the wrong direction. The text states p(O not having guards) = product over o in O of p(o is not a guard) <= (1-omega)^k, but since p(o is a guard) <= omega, each factor is at least 1-omega and the product is at least (1-omega)^k. As printed, the subsequent lower bound (1-omega)^k >= 1/m does not imply the desired lower bound on the success probability. The surrounding argument evidently intends the >= direction, but the displayed inequality must be corrected for the proof to be valid.
[Proposition 8 and Table 1] The running-time bound for the faster variant is missing one factor of m. In that variant the pruned space U has O(km) points, and each call to Decompose costs O(R*|U|^2) = O(m*(km)^2) = O(k^2*m^3), since R is O(1/alpha) = O(m) with the corrected alpha. Algorithm 4 repeats line 3 T*m times, so the total decomposition cost is O(T*m^4*k^2), not O(T*m^3*k^2) as stated in the proof of Proposition 8 and in Table 1. This does not destroy polynomiality, but the stated complexity claim is incorrect and should be corrected (or the repetition count should be defined differently).

minor comments (5)

[Algorithm 4, line 5] The call to Assign uses {k_i} as the upper-bound argument, but the notation for upper bounds elsewhere is {u_i}; {k_i} is not defined. This should be corrected to Assign({D_i}, {ell_i}, {u_i}, k).
[Section 4, Figure 3] The panel label 'Celab (S+A)' contains a typo and should read 'CelebA (S+A)'.
[Section 5 (Conclusions)] The word 'inapproxabimility' is a typo and should be 'inapproximability'.
[Section 3.4] The phrase 'This comes yields a weaker guarantee' is grammatically incomplete; it should be 'This yields a weaker guarantee'.
[Section 3.2] The sentence 'It is easy to verify that Delta_1 <= Delta_2 for m >= 1' is not true with the printed value of alpha when m = 2, because Delta_2 = 0 and Delta_1 = 1. After the alpha correction, the statement should be stated with the required lower bound on m.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the approximation chain is derived from explicit metric-space arguments and standard CKR partition properties; the guessed optimal value is handled by an independent grid search.

full rationale

This paper contains no significant circularity. The derivation chain is: Preprocess prunes same-color points using a triangle-inequality argument (Propositions 2-3); Decompose applies the standard CKR random partition and a cited external lemma (Har-Peled-Rahul, Lemma 1.2) to bound the guard probability (Proposition 4), and uses the graph edge threshold gamma*alpha plus the triangle inequality to show cross-cluster separation (Proposition 5); Assign extracts a feasible solution via an integral max-flow argument (Proposition 6). Each step's assumptions, namely the metric triangle inequality, k<=m, and the color-separation property inherited from preprocessing, are stated explicitly. No fitted parameter is renamed as a prediction, and no central result reduces to its own inputs by construction. The only guessed quantity is the optimal value tau, which is handled by an independent grid search over distance values in Section 3.4, losing only a (1+epsilon) factor and not feeding back into the probability or diversity analysis. The paper does cite prior work by the same authors [28], but only in related-work discussion of asymmetric distances, not as load-bearing support for the FMMD result. A possible parameter mismatch between the alpha printed in Algorithm 2 and the factor stated in Proposition 7 is a correctness or consistency concern, not circularity, because the proof does not define its conclusion into its assumptions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on standard metric-space assumptions and known CKR partition bounds; no free parameters are fitted to data, and no new entities are postulated.

assumptions (3)

domain assumption (V,d) is a metric space satisfying the triangle inequality.
Used throughout the proofs, notably in Proposition 2 for the injectivity of the closest-point mapping and in Proposition 4 for the ball-size bound |B_G(o, Delta2)| <= m.
standard math CKR padded decomposition guard probability bound (Har-Peled and Rahul, Lemma 1.2): the probability that a point is a guard is at most (1/(Delta2-Delta1+1)) * log(|B_G(o,Delta2)| / |B_G(o,Delta1-1)|).
Invoked in the proof of Proposition 4 to bound the probability that the optimal solution gets partially removed by the decomposition.
standard math Max-flow integrality: a maximum flow with integral capacities can be chosen integral.
Used in Proposition 6 to guarantee that the flow-based assignment selects a feasible set S with exactly one point per assigned cluster.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fair Diversity Maximization with Few Representatives." pith.science (2026). https://pith.science/paper/7T2WCXML

@misc{pith2026250608110,
  author       = {Pith},
  title        = {Pith review of: Fair Diversity Maximization with Few Representatives},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7T2WCXML}},
  note         = {Machine review of arXiv:2506.08110}
}

abstract

Diversity maximization problem is a well-studied problem where the goal is to find $k$ diverse items. Fair diversity maximization aims to select a diverse subset of $k$ items from a large dataset, while requiring that each group of items be well represented in the output. More formally, given a set of items with labels, our goal is to find $k$ items that maximize the minimum pairwise distance in the set, while maintaining that each label is represented within some budget. In many cases, one is only interested in selecting a handful (say a constant) number of items from each group. In such scenario we show that a randomized algorithm based on padded decompositions improves the state-of-the-art approximation ratio to $\sqrt{\log(m)}/(3m)$, where $m$ is the number of labels. The algorithms work in several stages: ($i$) a preprocessing pruning which ensures that points with the same label are far away from each other, ($ii$) a decomposition phase, where points are randomly placed in clusters such that there is a feasible solution with maximum one point per cluster and that any feasible solution will be diverse, $(iii)$ assignment phase, where clusters are assigned to labels, and a representative point with the corresponding label is selected from each cluster. We experimentally verify the effectiveness of our algorithm on large datasets.

Figures

Figures reproduced from arXiv: 2506.08110 by the authors.

**Figure 1.** Selected 𝑘 = 20 of existing nuclear power plants in US, at most one per state. web search [8, 34, 35, 43], information exposure in social networks [31] and e-commerce [45], among others. The goal is to find a set of diverse items within the data, which means that the selected items should be highly dissimilar to each other. In metric spaces this naturally translates to seeking a set with large distances between its … view at source ↗

**Figure 2.** Flow network used to solve the assignment of clus [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Diversity scores of the solutions of different algorithms versus the solution size [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Running time of different algorithms versus the solution size [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 5.** Figure 5: Diversity scores and the running times of the algo [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

45 extracted references · 39 canonical work pages

[1]

Zeinab Abbassi, Vahab S Mirrokni, and Mayur Thakur. 2013. Diversity max- imization under matroid constraints. InProceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 32–40

work page 2013
[2]

Dimitris Achlioptas. 2001. Database-friendly random projections. InProceed- ings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 274–281

work page 2001
[3]

Raghavendra Addanki, Andrew McGregor, Alexandra Meliou, and Zafeiria Moumoulidou. 2022. Improved Approximation and Scalability for Fair Max- Min Diversification. In25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference) (LIPIcs, Vol. 220). Schloss Dagstuhl - Leibniz-Zentrum für Informatik,...

work page doi:10.4230/lipics.icdt.2022.7 2022
[4]

Noga Alon. 1988. The linear arboricity of graphs.Israel Journal of Mathematics 62, 3 (1988), 311–325

work page 1988
[5]

Daichi Amagata. 2023. Diversity maximization in the presence of outliers. In Proceedings of the AAAI conference on artificial intelligence, Vol. 37. 12338–12345

work page 2023
[6]

Daichi Amagata and Takahiro Hara. 2016. Diversified set monitoring over distributed data streams. InProceedings of the 10th ACM International Con- ference on Distributed and Event-Based Systems(Irvine, California)(DEBS ’16). Association for Computing Machinery, New York, NY, USA, 1–12. https: //doi.org/10.1145/2933267.2933298

work page arXiv 2016
[7]

Aditya Bhaskara, Mehrdad Ghadiri, Vahab Mirrokni, and Ola Svensson. 2016. Lin- ear relaxations for finding diverse elements in metric spaces. InProceedings of the 30th International Conference on Neural Information Processing Systems(Barcelona, Spain)(NIPS’16). Curran Associates Inc., Red Hook, NY, USA, 4105–4113

work page 2016
[8]

Sayan Bhattacharya, Sreenivas Gollapudi, and Kamesh Munagala. 2011. Consid- eration set generation in commerce search. InProceedings of the 20th international conference on World wide web. 317–326

work page 2011

Show all 45 references

[9]

Allan Borodin, Aadhar Jain, Hyun Chul Lee, and Yuli Ye. 2017. Max-sum diversifi- cation, monotone submodular functions, and dynamic updates.ACM Transactions on Algorithms (TALG)13, 3 (2017), 1–25

2017
[10]

Gruia Calinescu, Howard Karloff, and Yuval Rabani. 2005. Approximation algo- rithms for the 0-extension problem.SIAM J. Comput.34, 2 (2005), 358–372

2005
[11]

Pablo Castells, Neil Hurley, and Saul Vargas. 2021. Novelty and diversity in recommender systems. InRecommender systems handbook. Springer, 603–646

2021
[12]

Matteo Ceccarello, Andrea Pietracaprina, and Geppino Pucci. 2018. Fast Coreset- based Diversity Maximization under Matroid Constraints. InProceedings of the Eleventh ACM International Conference on Web Search and Data Mining(Marina Del Rey, CA, USA)(WSDM ’18). Association for ...

2018
[13]

Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth Vishnoi. 2018. Fair and diverse DPP-based data summarization. In International conference on machine learning. PMLR, 716–725

2018
[14]

L Elisa Celis, Damian Straszak, and Nisheeth K Vishnoi. 2017. Ranking with fairness constraints.arXiv preprint arXiv:1704.06840(2017)

2017 arXiv
[15]

Alfonso Cevallos, Friedrich Eisenbrand, and Rico Zenklusen. 2017. Local search for max-sum diversification. InProceedings of the Twenty-Eighth Annual ACM- SIAM Symposium on Discrete Algorithms. SIAM, 130–142

2017
[16]

Barun Chandra and Magnús M Halldórsson. 2001. Approximation Algorithms for Dispersion Problems.Journal of Algorithms38, 2 (2001), 438–465. https: //doi.org/10.1006/jagm.2000.1145

2001
[17]

Marina Drosou and Evaggelia Pitoura. 2013. Diverse set selection over dynamic data.IEEE Transactions on Knowledge and Data Engineering26, 5 (2013), 1102– 1116

2013
[18]

Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub M Tarnawski. 2020. Fairness in streaming submodular maximization: Algorithms and hardness.Advances in Neural Information Processing Systems33 (2020), 13609–13622

2020
[19]

Erhan Erkut. 1990. The discrete p-dispersion problem.European Journal of Operational Research46, 1 (1990), 48–60

1990
[20]

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. 2004. A tight bound on approximating arbitrary metrics by tree metrics.J. Comput. System Sci.69, 3 (2004), 485–497. https://doi.org/10.1016/j.jcss.2004.04.011 Special Issue on STOC 2003

2004 doi
[21]

Michael R Fellows. 1990. Transversals of vertex partitions in graphs.SIAM Journal on Discrete Mathematics3, 2 (1990), 206–215

1990
[22]

Teofilo F Gonzalez. 1985. Clustering to minimize the maximum intercluster distance.Theoretical computer science38 (1985), 293–306

1985
[23]

Sariel Har-Peled and Saladi Rahul. 2018. Two (known) results about graphs with no short odd cycles.arXiv preprint arXiv:1810.01832(2018)

2018 arXiv
[24]

Penny Haxell. 2011. On forming committees.The American Mathematical Monthly 118, 9 (2011), 777–788

2011
[25]

Marius Kaminskas and Derek Bridge. 2016. Diversity, serendipity, novelty, and coverage: a survey and empirical analysis of beyond-accuracy objectives in recommender systems.ACM Transactions on Interactive Intelligent Systems (TiiS) 7, 1 (2016), 1–42

2016
[26]

Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. 2019. Fair k- center clustering for data summarization. InInternational Conference on Machine Learning. PMLR, 3448–3457

2019
[27]

Michael J Kuby. 1987. Programming models for facility dispersion: The p- dispersion and maxisum dispersion problems.Geographical Analysis19, 4 (1987), 315–329

1987
[28]

Iiro Kumpulainen, Florian Adriaens, and Nikolaj Tatti. 2024. Max-Min Diver- sification with Asymmetric Distances. InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 1440–1450

2024
[29]

Yash Kurkure, Miles Shamo, Joseph Wiseman, Sainyam Galhotra, and Stavros Sin- tos. 2024. Faster Algorithms for Fair Max-Min Diversification in Rd.Proceedings of the ACM on Management of Data2, 3 (2024), 1–26

2024
[30]

Po-Shen Loh and Benny Sudakov. 2007. Independent transversals in locally sparse graphs.Journal of Combinatorial Theory, Series B97, 6 (2007), 904–918. https://doi.org/10.1016/j.jctb.2007.02.003

2007 doi
[31]

Antonis Matakos, Sijing Tu, and Aristides Gionis. 2020. Tell me something my friends do not know: Diversity maximization in social networks.Knowledge and Information Systems62 (2020), 3697–3726

2020
[32]

Manor Mendel and Assaf Naor. 2006. Ramsey partitions and proximity data structures. InProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’06). IEEE Computer Society, USA, 109–118. https: //doi.org/10.1109/FOCS.2006.65

2006 doi
[33]

Zafeiria Moumoulidou, Andrew Mcgregor, and Alexandra Meliou. 2020. Diverse Data Selection under Fairness Constraints. InInternational Conference on Database Theory. https://api.semanticscholar.org/CorpusID:224703414

2020
[34]

Lu Qin, Jeffrey Xu Yu, and Lijun Chang. 2012. Diversifying Top-k Results.Proc. VLDB Endow.5, 11 (jul 2012), 1124–1135. https://doi.org/10.14778/2350229. 2350233

2012 doi
[35]

Filip Radlinski and Susan Dumais. 2006. Improving personalized web search using result diversification. InProceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. 691–692

2006
[36]

Sekharipuram S Ravi, Daniel J Rosenkrantz, and Giri Kumar Tayi. 1994. Heuristic and special case algorithms for dispersion problems.Operations Research42, 2 (1994), 299–310

1994
[37]

Arie Tamir. 1991. Obnoxious facility location on graphs.SIAM Journal on Discrete Mathematics4, 4 (1991), 550–567

1991
[38]

Jan Van Den Brand, Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximil- ian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. 2023. A deterministic almost-linear time algorithm for minimum-cost flow. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science...

2023
[39]

Da-Wei Wang and Yue-Sun Kuo. 1988. A study on two geometric location problems.Information processing letters28, 6 (1988), 281–286

1988
[40]

Yanhao Wang, Francesco Fabbri, and Michael Mathioudakis. 2022. Streaming algorithms for diversity maximization with fairness constraints. In2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 41–53

2022
[41]

Yanhao Wang, Francesco Fabbri, Michael Mathioudakis, and Jia Li. 2023. Fair max– min diversity maximization in streaming and sliding-window models.Entropy 25, 7 (2023), 1066

2023
[42]

Yanhao Wang, Michael Mathioudakis, Jia Li, and Francesco Fabbri. 2023. Max-min diversification with fairness constraints: Exact and approximation algorithms. InProceedings of the 2023 SIAM International Conference on Data Mining (SDM). SIAM, 91–99

2023
[43]

Dong Xin, Hong Cheng, Xifeng Yan, and Jiawei Han. 2006. Extracting redundancy- aware top-k patterns. InProceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 444–453

2006
[44]

Sepehr Zadeh, Mehrdad Ghadiri, Vahab Mirrokni, and Morteza Zadimoghad- dam. 2017. Scalable feature selection via distributed diversity maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 31

2017
[45]

Kaiping Zheng, Hongzhi Wang, Zhixin Qi, Jianzhong Li, and Hong Gao. 2017. A survey of query result diversification.Knowledge and Information Systems51 (2017), 1–36

2017

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Zeinab Abbassi, Vahab S Mirrokni, and Mayur Thakur. 2013. Diversity max- imization under matroid constraints. InProceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 32–40

work page 2013

[2] [2]

Dimitris Achlioptas. 2001. Database-friendly random projections. InProceed- ings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 274–281

work page 2001

[3] [3]

Raghavendra Addanki, Andrew McGregor, Alexandra Meliou, and Zafeiria Moumoulidou. 2022. Improved Approximation and Scalability for Fair Max- Min Diversification. In25th International Conference on Database Theory, ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference) (LIPIcs, Vol. 220). Schloss Dagstuhl - Leibniz-Zentrum für Informatik,...

work page doi:10.4230/lipics.icdt.2022.7 2022

[4] [4]

Noga Alon. 1988. The linear arboricity of graphs.Israel Journal of Mathematics 62, 3 (1988), 311–325

work page 1988

[5] [5]

Daichi Amagata. 2023. Diversity maximization in the presence of outliers. In Proceedings of the AAAI conference on artificial intelligence, Vol. 37. 12338–12345

work page 2023

[6] [6]

Daichi Amagata and Takahiro Hara. 2016. Diversified set monitoring over distributed data streams. InProceedings of the 10th ACM International Con- ference on Distributed and Event-Based Systems(Irvine, California)(DEBS ’16). Association for Computing Machinery, New York, NY, USA, 1–12. https: //doi.org/10.1145/2933267.2933298

work page arXiv 2016

[7] [7]

Aditya Bhaskara, Mehrdad Ghadiri, Vahab Mirrokni, and Ola Svensson. 2016. Lin- ear relaxations for finding diverse elements in metric spaces. InProceedings of the 30th International Conference on Neural Information Processing Systems(Barcelona, Spain)(NIPS’16). Curran Associates Inc., Red Hook, NY, USA, 4105–4113

work page 2016

[8] [8]

Sayan Bhattacharya, Sreenivas Gollapudi, and Kamesh Munagala. 2011. Consid- eration set generation in commerce search. InProceedings of the 20th international conference on World wide web. 317–326

work page 2011