Pith. sign in

REVIEW 4 major objections 4 minor 55 references

On Fair Epsilon Net and Geometric Hitting Set

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper shows that epsilon-nets and geometric hitting sets can be made fair by preserving exact demographic group ratios, with only a logarithmic increase in output size for nets, and it introduces a reduction that yields an $O(\log…

desk verdict First fair-epsilon-net paper with a genuinely new formulation and a nice fair-matching construction, but the main Monte Carlo theorem breaks on unstated integrality/supply conditions and the weighted variant enforces the wrong fairness ratios. read the letter →

arxiv 2507.08758 v1 pith:5U6R6XEZ submitted 2025-07-11 cs.DS

Mohsen Dehghankar , Stavros Sintos , Abolfazl Asudeh This is my paper
classification cs.DS
keywords fairepsilon-netgeometrichittingsetdemographicparitycustom-ratiofairnessdiscrepancymethodVCdimensionrandomsamplinglinearprogrammingrounding
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

This paper asks whether the standard geometric approximation tools used to summarize large datasets can be made fair, meaning the compact subset they return is forced to preserve the demographic proportions of the original data. The answer, for $\varepsilon$-nets and geometric hitting sets, is yes: a randomized sampling algorithm produces a fair $\varepsilon$-net in linear time whose size exceeds the unfair optimum by only a factor logarithmic in the number of groups, while a deterministic discrepancy-based algorithm removes the randomness with no added asymptotic size. A reduction through linear programming gives a fair geometric hitting set within an $O(\log \mathsf{OPT} \cdot \log k)$ factor of optimum, and the paper also shows a limit: once ranges can separate a demographic group, arbitrary custom target ratios become impossible for $\varepsilon$-samples, so demographic parity is the safer notion for sampling-based summaries.

What carries the argument

The two load-bearing mechanisms are the top-up sample and the fair matching. The top-up sample draws $\lambda$ points uniformly at random, using the classical size that guarantees an unfair $\varepsilon$-net, then for each color $c$ adds enough extra points of that color to reach the target count $(1+v)(|X_c|/|X|)\lambda$ with $v = 2\ln(k/\varphi)$. A Chernoff bound guarantees that no color overshoots its quota with probability at least $1-\varphi/2$, so the output is exactly proportional and has size $(1+v)\lambda$. The fair matching is the discrepancy-method analogue: at each halving step, points are paired only within the same demographic group, so keeping one point from each pair halves every group's count and preserves ratios exactly; repeated halving yields an $\varepsilon$-net by the standard discrepancy argument. The reduction from custom-ratio fairness to the weighted fair $\varepsilon$-net runs through a linear program whose variables are point weights; the LP's optimal value supplies the $\varepsilon$ and the group-total weights supply the demographic-parity constraint, turning the hitting set into a weighted fair $\varepsilon$-net instance that the sampling algorithm rounds.

What would settle it

Build a range space with two colors where one color has a single point, choose a target ratio $\tau$ and $\varepsilon$ such that $(1+v)\tau\lambda$ exceeds that group's size, and run the fair Monte-Carlo algorithm: the top-up step cannot add the demanded number of minority points, so the output either misses the exact ratio or has size larger than the theorem allows.

Watch

Extended reading notes

Core claim

The central claim is that fairness constraints can be layered onto classical geometric approximation problems without losing their guarantees. For a range space of VC dimension $d$ over $n$ points partitioned into $k$ demographic groups, a uniformly random sample of size $\lambda = O\!\big((1/\varepsilon)\max\{\log(1/\varphi), d\log(1/\varepsilon)\}\big)$, topped up with the right number of extra points from each under-represented group, is an $\varepsilon$-net that exactly matches the input group ratios with probability at least $1-\varphi$, running in $O(n)$ time and producing size $O(\lambda \log(k/\varphi))$. The same top-up trick extends to weighted points. When randomness is undesirable, the discrepancy method can be adapted by pairing points of the same demographic group at every halving step, which preserves group ratios exactly and gives a deterministic fair $\varepsilon$-net of size $O\!\big((d/\varepsilon)\log(d/\varepsilon)\big)$. The paper further shows that fair geometric hitting set with arbitrary target ratios reduces to a weighted fair $\varepsilon$-net instance whose LP relaxation is rounded by the fair sampling algorithm, yielding an $O\!\big(\max\{\log(1/\varphi), d\log \mathsf{OPT}\} \cdot \log(k/\varphi)\big)$-approximation. Finally, fair $\varepsilon$-samples under arbitrary custom ratios are shown to be infeasible in general, because a range that isolates one group pins that group's sample share within an $\varepsilon$ window of its input share.

Load-bearing premise

The algorithms assume that the target number of points of each group, after the top-up step or after each halving, is a whole number that can actually be taken from the data; for the deterministic halving, this also requires every group's size to be a power of two, and if a group has too few points or the counts do not come out integral, the exact-ratio guarantee and the stated size bound cannot both hold.

Editorial extensions

If this is right

  • A data curator can build a fair summary of a large table for approximate range-query answering in $O(n)$ time, with zero measured group-ratio distortion and only a $\log k$ increase in summary size.
  • The deterministic discrepancy-based variant gives the same exact-ratio guarantee without randomization, at the cost of $O(n m \log n)$ time when all ranges are materialized.
  • Fair geometric hitting sets (and, by geometric duality, fair set covers) admit approximation factors that depend on $\log \mathsf{OPT}$ and $\log k$ rather than $\log n$, which is sharper than generic fair set cover.
  • When a custom-ratio target is feasible, the reduction to weighted fair $\varepsilon$-nets shows that the target can be met as long as the linear program and the per-color count conditions hold.
  • Fair $\varepsilon$-samples with arbitrary target ratios are not always possible, so any sampling-based fairness requirement must be checked against the geometry before deployment.

Reading between the lines

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

  • This suggests the top-up formula could be made robust to non-integral target counts by allowing a one-point slack per color, at a negligible size cost, which would widen applicability beyond the exact-ratio setting.
  • The fair-matching halving hints at a general template: enforce fairness at every node of a divide-and-conquer hierarchy, which could be inserted into other hierarchical geometric constructions such as partition trees or coresets.
  • The LP-to-sampling rounding could generalize to other covering LPs with color constraints, potentially offering a unified scheme for fair covering problems where randomized rounding is already used.
  • The infeasibility result for $\varepsilon$-samples implies that for sampling-based fairness the safer target is demographic parity, and any custom-ratio requirement must be validated against the dataset's geometry before a sampling-based summary is used.
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.

Referee Report

4 major / 4 minor

Summary. The paper introduces fair versions of epsilon-nets, epsilon-samples, and geometric hitting set under demographic parity (DP) and custom-ratio (CR) constraints. It proposes a Monte-Carlo sampling algorithm (Section 4.1), a deterministic discrepancy-based algorithm (Section 4.2), and a sketch-and-merge variant (Section 4.2.2) for fair epsilon-nets; a reduction from CR fair epsilon-nets to fair geometric hitting set (Section 4.3); a negative result for fair epsilon-samples with CR constraints (Section 4.4, Appendix A); and an LP-based reduction of FGHS to weighted fair epsilon-nets (Section 5). The main theoretical claims are an O(log(k/phi)) size overhead over standard epsilon-nets for the Monte-Carlo algorithm (Theorem 6), a deterministic fair epsilon-net of size O(d/epsilon log(d/epsilon)) (Theorems 13 and 17), and an O(max{log 1/phi, d log OPT_FGHS} log(k/phi)) approximation for FGHS (Theorem 22). Experiments on real and synthetic data report near-zero unfairness with modest size increases.

Significance. The paper addresses a timely and natural question: how to make geometric approximation constructions group-fair. The high-level approach—combining Chernoff-based top-up sampling, discrepancy-based halving with fair matchings, and LP rounding—is sensible, and the reduction of fair geometric hitting set to weighted fair epsilon-nets is elegant. The paper uses classical external tools (Chernoff bounds, Haussler-Welzl theorem, discrepancy lemmas) with no fitted parameters, and the Appendix A infeasibility result is a useful limitation statement. However, the correctness of the central theorems rests on several conditions that are not stated in the manuscript: exact integrality and per-color supply for the Monte-Carlo top-up, a mismatch between the sampling distribution and the top-up ratios in the weighted variant, and missing per-color size conditions for the deterministic halving procedures. These are load-bearing gaps, not mere presentation issues. The experimental validation is helpful but cannot substitute for the missing hypotheses. If the stated conditions and fixes are supplied, the paper would be a solid contribution to fair geometric data summarization.

major comments (4)
  1. [§4.1, Algorithm 1, Lemma 4] The proof of Lemma 4 requires that for every color c the target count (1+v)τ_c λ is an integer and does not exceed |X_c|, because Algorithm 1 adds exactly (1+v)τ_c λ − |N_c| points of color c; neither condition is stated or guaranteed. For DP, τ_c = |X_c|/|X|, and with v = 2 ln(2k/phi) generally irrational, (1+v)τ_c λ is typically non-integral; for example, with epsilon=1, phi=0.1, k=2, n=256, and 128 points per color, lambda=23 (from Theorem 1) gives a per-color target of (1+2 ln 40)·23/2 ≈ 96.34 points. Algorithm 1 cannot add a fractional number of points, so the exact-ratio condition |S_c|/|S| = τ_c in Definition 4 is not achieved and Theorem 6 does not follow as stated.
  2. [§4.1.1] In the weighted fair Monte-Carlo algorithm, the initial sample N is drawn with probabilities proportional to the point weights w_i, so the expected count for color c is lambda W_c, where W_c = Σ_{p_i in X_c} w_i. The top-up step, however, adds (1+v)|X_c|/|X| lambda − |N_c| points, using the unweighted input proportions rather than the weighted DP ratios τ_c = W_c that the section defines. The Chernoff bound stated in that subsection likewise uses |X_c|/|X| as the mean, which is inconsistent with the sampling distribution. As a result, the output enforces unweighted ratios rather than the required weighted ratios, and Theorem 7 is not proven.
  3. [§5, Theorem 22] The FGHS algorithm in Section 5 constructs weights w_i from the LP (3) and then runs the algorithm from Theorem 7 on (X,R) with those weights and with DP constraints T. Since Theorem 7 is not established (see the two preceding comments), the size guarantee O(max{log 1/phi, d log OPT_FGHS} · log(k/phi) · OPT_FGHS) in Theorem 22 does not follow. The same applies to the CR fair epsilon-net bound in Theorem 19, which depends on Theorem 22.
  4. [§4.2 and §4.2.2] The discrepancy-based algorithms construct fair matchings that pair only points of the same color at every halving level. For the algorithm of Section 4.2, this requires each color count to be even at each of the U = log(n/(c0 d/epsilon log(d/epsilon))) iterations; the assumption |X_c| = 2^{xi_c} alone does not imply U ≤ xi_c, so a color may be left with one point before the process terminates, making the fair matching impossible. In the sketch-and-merge algorithm of Section 4.2.2, the initial partition requires every color to have size divisible by 2^p and p ≤ xi_c, which is not stated. The proofs of Lemmas 10, 14, and 16, and hence Theorems 13 and 17, need explicit sufficient conditions on the group sizes.
minor comments (4)
  1. [Definition 1] In Definition 1, the condition '|N ∩ R| ≥ 0' is trivially true; it should be '|N ∩ R| ≥ 1' (i.e., the net must intersect every heavy range), otherwise the definition does not characterize an epsilon-net.
  2. [§4.1] The text says 'Draw a set N of lambda ... uniform random samples (with replacement)', but Algorithm 1 states 'N ← a random subset of size lambda'; with replacement sampling produces a multiset, which is inconsistent with the later set operations and with the definition of a subset. Please clarify.
  3. [Lemma 3] The derivation of the probability bound uses the inequality exp(−v²/(2+v)) ≤ exp(−ln(k/(phi/2))), which holds only when ln(2k/phi) ≥ 1; for small values of 2k/phi (e.g., k=1 and phi close to 1) the claimed bound is off by a constant. The proof should use a Chernoff variant that is valid for all parameter ranges or adjust the constant v.
  4. [Section 7] The statement 'The code and other artifacts are publicly available' is followed only by the footnote 'Github repository' with no URL; please provide the actual link for reproducibility.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation; only a minor non-load-bearing self-citation.

full rationale

We walked the claimed derivation chain and found no step in which a stated prediction or first-principles result is equivalent, by the paper's own equations, to its inputs. The Monte-Carlo fair eps-net size bound (Theorem 6) combines the external Haussler-Welzl sampling theorem with a standard Chernoff tail bound; the fairness conclusion is enforced by the top-up step, i.e., the algorithm intentionally adds the exact number of points of each color, so fairness is the definitional goal of the construction rather than a prediction derived from a fitted parameter. The discrepancy-based theorems (Theorems 13 and 17) import Chazelle's halving and range-approximation arguments from the external reference [16]; the same-color fair matching is an algorithmic device, not an imported uniqueness theorem or ansatz that is doing the work by self-citation. The custom-ratio results (Theorems 19 and 22) are obtained by LP relaxation followed by a reduction to the in-paper weighted fair eps-net of Theorem 7, and the key inequality 1/eps <= OPT_FGHS is the standard LP-relaxation lower bound, not a definitional identity. The only self-citation is [20] in Section 4.3, where the authors' prior fair set cover algorithm is used to give a preliminary O(log n) bound; the main CR fair eps-net theorem is then explicitly obtained through Theorem 22, so [20] is not load-bearing. We therefore report no circular step. For completeness, we note separately as correctness risks rather than circularity that Lemma 4's equality |S|=(1+v)lambda presupposes integrality and sufficient supply of each color for the top-up targets (1+v)tau_c lambda, and that the weighted variant in Section 4.1.1 tops up with |X_c|/|X| rather than W_c; these are gaps in the stated proofs, but they are not reductions of the claimed results to their own inputs.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The algorithms introduce no new physical or mathematical entities, and the main theoretical claims rely on standard background theorems plus explicit domain assumptions. The only hand-chosen algorithmic parameter is the leaf size 2^p in sketch-and-merge, which is never concretely set. The most fragile input is the unstated integrality and supply condition for the top-up step.

free parameters (1)
  • leaf partition size 2^p in Fair Sketch-and-Merge
    The paper says 'p is a small parameter value that is set later' (Section 4.2.2) but never gives a concrete value or selection rule, and the stated runtime bound depends on the choice.
assumptions (6)
  • standard math Haussler-Welzl random sampling theorem: a sample of size lambda = O((d/eps) log(1/eps) + (1/eps) log(1/phi)) is an epsilon-net with probability 1-phi.
    Used as the black-box basis for the fair Monte-Carlo and weighted Monte-Carlo algorithms; cited as Theorem 1 from [30].
  • domain assumption The range space (X,R) has finite VC dimension d.
    All size and approximation bounds depend on d; introduced in Section 2.2 and used throughout Sections 4 and 5.
  • domain assumption n and every |X_c| are powers of two.
    Stated in Section 3 Assumptions; needed for the same-color fair matchings in the discrepancy-based algorithm (Lemma 10).
  • domain assumption tau_l * lambda >= 1 for every color l.
    Stated in Section 3 to keep the fair net size comparable to the unfair net; the paper notes the approximation factor can degrade by 1/(lambda * min_l tau_l) if it fails.
  • domain assumption Access to all ranges R is available for deterministic and LP-based algorithms.
    Assumed in Sections 4.2, 4.3 and 5; the deterministic Halving and the LP construction require the explicit list of ranges.
  • ad hoc to paper The target counts (1+v)*tau_l*lambda are integers and never exceed |X_c|.
    Not stated in the paper, but Algorithm 1's topping-up step requires an integer number of points and a sufficient supply of points per color; this is a load-bearing unstated premise.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Fair Epsilon Net and Geometric Hitting Set." pith.science (2026). https://pith.science/paper/5U6R6XEZ

@misc{pith2026250708758,
  author       = {Pith},
  title        = {Pith review of: On Fair Epsilon Net and Geometric Hitting Set},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5U6R6XEZ}},
  note         = {Machine review of arXiv:2507.08758}
}
abstract

Fairness has emerged as a formidable challenge in data-driven decisions. Many of the data problems, such as creating compact data summaries for approximate query processing, can be effectively tackled using concepts from computational geometry, such as $\varepsilon$-nets. However, these powerful tools have yet to be examined from the perspective of fairness. To fill this research gap, we add fairness to classical geometric approximation problems of $\varepsilon$-net, $\varepsilon$-sample, and geometric hitting set. We introduce and address two notions of group fairness: demographic parity, which requires preserving group proportions from the input distribution, and custom-ratios fairness, which demands satisfying arbitrary target ratios. We develop two algorithms to enforce fairness: one based on sampling and another on discrepancy theory. The sampling-based algorithm is faster and computes a fair $\varepsilon$-net of size which is only larger by a $\log(k)$ factor compared to the standard (unfair) $\varepsilon$-net, where $k$ is the number of demographic groups. The discrepancy-based algorithm is slightly slower (for bounded VC dimension), but it computes a smaller fair $\varepsilon$-net. Notably, we reduce the fair geometric hitting set problem to finding fair $\varepsilon$-nets. This results in a $O(\log \mathsf{OPT} \times \log k)$ approximation of a fair geometric hitting set. Additionally, we show that under certain input distributions, constructing fair $\varepsilon$-samples can be infeasible, highlighting limitations in fair sampling. Beyond the theoretical guarantees, our experimental results validate the practical effectiveness of the proposed algorithms. In particular, we achieve zero unfairness with only a modest increase in output size compared to the unfair setting.

Figures

Figures reproduced from arXiv: 2507.08758 by the authors.

Figure 1
Figure 1. Illustration of an unfair 𝜀-net, highlighted with green circles rectangles. For example, 𝑟1 in [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Sketch-and-Merge approach on a partition tree. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Measuring the fairness of the output of Fair Monte-Carlo (FMC) and standard sampling for dataset summarization. The fairness [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: The fairness of FMC algorithm vs. standard sampling on the PopSim dataset vs. the value of 𝜀. The fairness constraint is DP. = 0.2 = 0.4 = 0.63 = 0.65 = 0.66 Value of 200 400 600 800 1000 Average Size ×0.67 ×0.67 ×0.67 ×0.67 ×0.67 Average -net Size Sampling FMC [PITH_…
Figure 7
Figure 7. Figure 7: Comparing the average size of 𝜀-net produced by standard and fair algorithms for dataset summarization task. Dataset Sampling Time (s) FMC Time (s) Adults 2.1244 2.2044 (1.03×) COMPAS 2.4343 2.5470 (1.05×) Admissions 0.0032 0.0038 (1.19×) [PITH_FULL_IMAGE:figures/full…
Figure 8
Figure 8. Figure 8: The running time of the standard methods and their fair variants. The time is averaged between different runs in the syn￾thetic rectangle range space in 2D. 2 1 2 2 2 3 2 4 2 5 k 600 700 800 900 1000 1100 1200 Average Size Average Size vs. k FMC Bounds: [c1log(k), c2lo…
Figure 11
Figure 11. Figure 11: Fairness of output Rank Regret Representatives. [PITH_FULL_IMAGE:figures/full_fig_p013_11.png]
Figure 12
Figure 12. Figure 12: Application use case based on Example 1: interactive map [PITH_FULL_IMAGE:figures/full_fig_p015_12.png]
Figure 14
Figure 14. Figure 14: Running time comparison of Fair Monte-Carlo (FMC) [PITH_FULL_IMAGE:figures/full_fig_p017_14.png]
Figure 16
Figure 16. Figure 16: Measuring the fairness (F∞) of the output 𝜀-net across different values of 𝜀 across three datasets on Representative Database Sampling task. Here, we compare the unfair Sampling and Fair Monte-Carlo sampling methods. Here, the fairness constraint is DP. 0.20 0.25 0.30…
Figure 17
Figure 17. Figure 17: The comparison between the standard algorithms for building [PITH_FULL_IMAGE:figures/full_fig_p017_17.png]
Figure 18
Figure 18. Figure 18: The result of applying fair algorithms in finding the fair Rank Regret Representatives on the three datasets. [PITH_FULL_IMAGE:figures/full_fig_p017_18.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

55 extracted references · 51 canonical work pages

  1. [1]

    Vladimir Agafonkin. 2016. Clustering millions of points on a map with Supercluster. Mapbox. https://blog.mapbox.com/clustering-millions-of-points-on-a-map- with-supercluster-272046ec5c97 Accessed: 2025-07-06

    work page 2016

  2. [2]

    Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016. Machine Bias – ProPublica. https://www.propublica.org/article/machine-bias-risk-assessments- in-criminal-sentencing. Accessed: 2025-04-16

    work page 2016

  3. [3]

    Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The multiplicative weights update method: a meta-algorithm and applications. Theory of computing 8, 1 (2012), 121–164

    work page 2012

  4. [4]

    Abolfazl Asudeh, Tanya Berger-Wolf, Bhaskar DasGupta, and Anastasios Sidiropoulos. 2023. Maximizing coverage while ensuring fairness: A tale of conflicting objectives. Algorithmica 85, 5 (2023), 1287–1331

    work page 2023

  5. [5]

    Abolfazl Asudeh, Gautam Das, HV Jagadish, Shangqi Lu, Azade Nazi, Yufei Tao, Nan Zhang, and Jianwen Zhao. 2022. On finding rank regret representatives. ACM Transactions on Database Systems (TODS) 47, 3 (2022), 1–37

    work page 2022

  6. [6]

    Abolfazl Asudeh, HV Jagadish, Julia Stoyanovich, and Gautam Das. 2019. De- signing fair ranking schemes. In Proceedings of the 2019 international conference on management of data . 1259–1276

    work page 2019

  7. [7]

    Abolfazl Asudeh, Azade Nazi, Nan Zhang, Gautam Das, and HV Jagadish. 2019. RRR: Rank-regret representative. In Proceedings of the 2019 International Confer- ence on Management of Data . 263–280

    work page 2019

  8. [8]

    Martin Aumuller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, and Francesco Silvestri. 2021. Fair near neighbor search via sampling. ACM SIGMOD Record 50, 1 (2021), 42–49

    work page 2021

Show all 55 references
  1. [9]

    Maria-Florina Balcan and Phil Long. 2013. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory . PMLR, 288–316

    2013

  2. [10]

    Sayan Bandyapadhyay, Aritra Banik, and Sujoy Bhore. 2021. On fair covering and hitting problems. In Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers 47. Springer, 39–51

    2021

  3. [11]

    Solon Barocas, Moritz Hardt, and Arvind Narayanan. 2023. Fairness and machine learning: Limitations and opportunities . MIT Press

    2023

  4. [12]

    Sujoy Bhore, Devdan Dey, and Satyam Singh. 2024. Online Epsilon Net and Piercing Set for Geometric Concepts. arXiv preprint arXiv:2410.07059 (2024)

    2024 arXiv

  5. [13]

    Hervé Brönnimann and Michael T Goodrich. 1994. Almost optimal set covers in finite VC-dimension: (preliminary version). In Proceedings of the tenth annual symposium on Computational geometry . 293–302

    1994

  6. [14]

    Timothy M Chan and Sariel Har-Peled. 2009. Approximation algorithms for maximum independent set of pseudo-disks. In Proceedings of the twenty-fifth annual symposium on Computational geometry . 333–340

    2009

  7. [15]

    Eswar Chand. 2020. Admission Dataset. https://www.kaggle.com/datasets/ eswarchandt/admission. Accessed: 2025-04-16

    2020

  8. [16]

    Chazelle

    B. Chazelle. 2000. The Discrepancy Method: Randomness and Complexity . Cam- bridge University Press. https://books.google.com/books?id=dmOPmEh6LdYC

    2000

  9. [17]

    Bernard Chazelle and Jiřı Matoušek. 1996. On linear-time deterministic algo- rithms for optimization problems in fixed dimension. Journal of Algorithms 21, 3 (1996), 579–597

    1996

  10. [18]

    Chandra Chekuri, Kenneth L Clarkson, and Sariel Har-Peled. 2012. On the set multicover problem in geometric settings. ACM Transactions on Algorithms (TALG) 9, 1 (2012), 1–17

    2012

  11. [19]

    Valery Chupurnoff. 2024. Displaying a large number of objects on a map. Online blog post. https://mappable.world/blog/displaying-a-large-number-of-objects- on-a-map Accessed July 6, 2025

    2024

  12. [20]

    Mohsen Dehghankar, Rahul Raychaudhury, Stavros Sintos, and Abolfazl Asudeh

  13. [21]

    Subramaniam Dhanabal and SJIJCA Chandramathi. 2011. A review of various k- nearest neighbor query processing techniques. International Journal of Computer Applications 31, 7 (2011), 14–22

    2011

  14. [22]

    Dheeru Dua and Casey Graff. 2019. UCI Machine Learning Repository: Adult Data Set. https://archive.ics.uci.edu/ml/datasets/adult. Accessed: 2025-04-16

    2019

  15. [23]

    Seyed Esmaeili, Sharmila Duppala, Davidson Cheng, Vedant Nanda, Aravind Srinivasan, and John P Dickerson. 2023. Rawlsian fairness in online bipartite matching: Two-sided, group, and individual. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 5624–5632

    2023

  16. [24]

    Dan Feldman and Michael Langberg. 2011. A unified framework for approximat- ing and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing . 569–578. , , Mohsen Dehghankar, Stavros Sintos, and Abolfazl Asudeh

    2011

  17. [25]

    Yoav Freund and Robert E Schapire. 1997. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences 55, 1 (1997), 119–139

    1997

  18. [26]

    David García-Soriano and Francesco Bonchi. 2020. Fair-by-design matching. Data Mining and Knowledge Discovery 34 (2020), 1291–1335

    2020

  19. [27]

    Sariel Har-Peled. 2011. Geometric approximation algorithms. Number 173. Ameri- can Mathematical Soc

    2011

  20. [28]

    Sariel Har-Peled, Mitchell Jones, and Saladi Rahul. 2021. Active-learning a convex body in low dimensions. Algorithmica 83 (2021), 1885–1917

    2021

  21. [29]

    Sariel Har-Peled and Soham Mazumdar. 2004. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. 291–300

    2004

  22. [30]

    David Haussler and Emo Welzl. 1986. Epsilon-nets and simplex range queries. In Proceedings of the second annual symposium on Computational geometry . 61–71

    1986

  23. [31]

    Zakria Hussain, Sandor Szedmak, and John Shawe-Taylor. 2004. The linear programming set covering machine. Pattern Analysis, Statistical Modelling and Computational Learning (2004)

    2004

  24. [32]

    Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, and Saket Saurabh. 2023. Fixed-Parameter Algorithms for Fair Hitting Set Problems. In 48th International Symposium on Mathematical Foundations of Computer Science

    2023

  25. [33]

    Christopher Jung, Sampath Kannan, and Neil Lutz. 2019. A center in your neighborhood: Fairness in facility location.arXiv preprint arXiv:1908.09041 (2019)

    2019 arXiv

  26. [34]

    Nick Littlestone. 1988. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning 2 (1988), 285–318

    1988

  27. [35]

    Philip M Long. 2001. Using the pseudo-dimension to analyze approximation algo- rithms for integer programming. In Workshop on Algorithms and Data Structures . Springer, 26–37

    2001

  28. [36]

    Yury Makarychev and Ali Vakilian. 2021. Approximation algorithms for socially fair clustering. In Conference on Learning Theory . PMLR, 3246–3264

    2021

  29. [37]

    Mario Marchand, Mohak Shah, John Shawe-Taylor, and Marina Sokolova. 2003. The set covering machine with data-dependent half-spaces. In Proceedings of the 20th International Conference on Machine Learning (ICML-03) . 520–527

    2003

  30. [38]

    Tasfia Mashiat, Xavier Gitiaux, Huzefa Rangwala, Patrick Fowler, and Sanmay Das. 2022. Trade-offs between group fairness metrics in societal resource alloca- tion. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency. 1095–1105

    2022

  31. [39]

    Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021. A survey on bias and fairness in machine learning. ACM com- puting surveys (CSUR) 54, 6 (2021), 1–35

    2021

  32. [40]

    Nabil H Mustafa and Kasturi Varadarajan. 2017. Epsilon-approximations & epsilon-nets. In Handbook of Discrete and Computational Geometry . Chapman and Hall/CRC, 1241–1267

    2017

  33. [41]

    Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J Lipton, and Jun Xu. 2010. Regret-minimizing representative databases. Proceedings of the VLDB Endowment 3, 1-2 (2010), 1114–1124

    2010

  34. [42]

    Rostislav Netek, Jan Brus, and Ondrej Tomecka. 2019. Performance testing on marker clustering and heatmap visualization techniques: a comparative study on javascript mapping libraries. ISPRS international journal of geo-information 8, 8 (2019), 348

    2019

  35. [43]

    Khanh Duy Nguyen, Nima Shahbazi, and Abolfazl Asudeh. 2023. PopSim: An Individual-level Population Simulator for Equitable Allocation of City Resources. arXiv preprint arXiv:2305.02204 (2023)

    2023 arXiv

  36. [44]

    Nick Roussopoulos, Stephen Kelley, and Frederic Vincent. 1995. Nearest neighbor queries. In Proceedings of the 1995 ACM SIGMOD international conference on Management of data. 71–79

    1995

  37. [45]

    Nima Shahbazi, Stavros Sintos, and Abolfazl Asudeh. 2024. Fairhash: A fair and memory/time-efficient hashmap. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–29

    2024

  38. [46]

    Seiji Shaw, Aidan Curtis, Leslie Pack Kaelbling, Tomás Lozano-Pérez, and Nicholas Roy. 2024. Towards practical finite sample bounds for motion planning in TAMP. arXiv preprint arXiv:2407.17394 (2024)

    2024 arXiv

  39. [47]

    Suhas Thejaswi, Bruno Ordozgoiti, and Aristides Gionis. 2021. Diversity-aware k-median: Clustering with fair center representation. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 20...

    2021

  40. [48]

    Vapnik and Alexey Ya

    Vladimir N. Vapnik and Alexey Ya. Chervonenkis. 1971. On the uniform conver- gence of relative frequencies of events to their probabilities.Theory of Probability and its Applications 16, 2 (1971), 264–280. doi:10.1137/1116025

    1971 doi

  41. [49]

    Volodymyr Agafonkin and contributors. 2025. Leaflet – a JavaScript library for interactive maps. https://leafletjs.com/. Accessed July 6, 2025

    2025

  42. [50]

    Yanhao Wang, Yuchen Li, Francesco Bonchi, and Ying Wang. 2022. Balancing Utility and Fairness in Submodular Maximization (Technical Report). arXiv preprint arXiv:2211.00980 (2022)

    2022 arXiv

  43. [51]

    Weili Wu, Zhao Zhang, Wonjun Lee, Dingzhu Du, et al. 2020. Optimal coverage in wireless sensor networks. (2020)

    2020

  44. [52]

    Bin Yao, Feifei Li, and Piyush Kumar. 2010. K nearest neighbor queries and knn- joins in large relational databases (almost) for free. In2010 IEEE 26th International Conference on Data Engineering (ICDE 2010) . IEEE, 4–15

    2010

  45. [53]

    Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Mega- hed, and Ricardo Baeza-Yates. 2017. Fa* ir: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Man- agement. 1569–1578

    2017

  46. [54]

    Haoran Zhang, Quaid Morris, Berk Ustun, and Marzyeh Ghassemi. 2021. Learning optimal predictive checklists. Advances in neural information processing systems 34 (2021), 1215–1229. On Fair Epsilon Net and Geometric Hitting Set , , Appendix Figure 12: Application use case based ...

    2021

  47. [2025]

    In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1 (Toronto ON, Canada) (KDD ’25)

    Fair Set Cover. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1 (Toronto ON, Canada) (KDD ’25) . Association for Computing Machinery, New York, NY, USA, 189–200. doi:10. 1145/3690624.3709184

Pith tools

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