On Fair Epsilon Net and Geometric Hitting Set

Summary: Introduces demographic-parity and custom-ratio fairness for ε-nets, ε-samples, and geometric hitting sets via sampling and discrepancy methods. Fair ε-nets incur only a log k size overhead and yield O(log OPT·log k) hitting-set approximations, while some fair samples are infeasible. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h9e1b24d3a5182420
Venue: VLDB
Year: 2026
Pagerank: 4.9769913e-05
Overall Rank: 10,706 | 28.05%
DOI: 10.14778/3796195.3796213
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Mohsen Dehghankar (University of Illinois Chicago)
2. Stavros Sintos (University of Illinois Chicago)
3. Abolfazl Asudeh (University of Illinois Chicago)

BibTeX Citation

@article{dehghankar_vldb26,
        title = {{On Fair Epsilon Net and Geometric Hitting Set}},
        author = {Dehghankar, Mohsen and Sintos, Stavros and Asudeh, Abolfazl},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {5},
        pages = {1032--1045},
        doi = {10.14778/3796195.3796213},
        url = {https://doi.org/10.14778/3796195.3796213},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,464	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051292389
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.0001409096
804	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013830311
1,087	Regret-Minimizing Representative Databases	2010	VLDB	0.00012092041
1,162	Responsible Data Management	2020	VLDB	0.00011747599
1,379	Designing Fair Ranking Schemes	2019	SIGMOD	0.00010859038
4,031	Slice Tuner: A Selective Data Acquisition Framework for Accurate and Fair Machine Learning Models	2021	SIGMOD	6.8374909e-05
4,327	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	6.6600895e-05
5,610	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.0660772e-05
5,624	Through the Fairness Lens: Experimental Analysis and Evaluation of Entity Matching	2023	VLDB	6.0583019e-05
6,142	iFlipper: Label Flipping for Individual Fairness	2023	SIGMOD	5.8706702e-05
6,202	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8494367e-05
6,525	PreFair: Privately Generating Justifiably Fair Synthetic Data	2023	VLDB	5.7542422e-05
6,721	RRR: Rank-Regret Representative	2019	SIGMOD	5.6966108e-05
6,877	Consistent Range Approximation for Fair Predictive Modeling	2023	VLDB	5.6564538e-05
8,023	Fairness in Preference Queries: Social Choice Theories Meet Data Management	2024	VLDB	5.4035905e-05
9,580	Chameleon: Foundation Models for Fairness-aware Multi-modal Data Augmentation to Enhance Coverage of Minorities	2024	VLDB	5.154741e-05
9,584	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	5.154741e-05
10,464	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD	4.9769913e-05
11,239	Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups	2025	VLDB	4.9769913e-05
11,525	FairHash: A Fair and Memory/Time-efficient Hashmap	2024	SIGMOD	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,692	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS
2	10,464	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD
3	10,805	Measuring Database Unfairness via Dependency Quantification Under Differential Privacy	2026	VLDB
4	5,624	Through the Fairness Lens: Experimental Analysis and Evaluation of Entity Matching	2023	VLDB
5	7,659	Models and Mechanisms for Spatial Data Fairness	2023	VLDB
6	5,739	Tailoring Data Source Distributions for Fairness-aware Data Integration	2021	VLDB
7	11,526	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD
8	11,525	FairHash: A Fair and Memory/Time-efficient Hashmap	2024	SIGMOD
9	9,584	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB
10	10,821	Unbiased Binning for Fairness-aware Attribute Representation	2026	VLDB