On Fair Epsilon Net and Geometric Hitting Set Conference: ; ;

Mohsen Dehghankar, Stavros Sintos, Abolfazl Asudeh · 2025

Read On Fair Epsilon Net and Geometric Hitting Set Conference: ; ; by Mohsen Dehghankar, Stavros Sintos, Abolfazl Asudeh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08758.txt.

Description

Mohsen Dehghankar, Stavros Sintos, and Abolfazl Asudeh add fairness constraints to classic geometry tools for summarizing data, in a 2025 paper. Epsilon-nets compress point sets while preserving answers to range queries, and hitting sets cover shapes with few points. Neither had been examined for fairness across demographic groups.

The authors define two fairness notions: keeping group shares as in the input, or hitting arbitrary target ratios. They give a fast sampling algorithm whose fair nets grow only slightly with the number of groups, and a slower discrepancy-based one that outputs smaller nets. Fair hitting set reduces to fair nets, yielding a solid approximation. Under some input distributions, they also prove fair samples cannot exist at all, a useful warning. Experiments confirmed zero unfairness at modest size cost. The work opens computational geometry to fairness-aware data systems.

Catalog record

CREATORMohsen Dehghankar, Stavros Sintos, Abolfazl Asudeh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-08758

Browse the full library · About the Tower of Babel