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: 14445
Venue: VLDB
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,511 | 27.89%
DOI: 10.14778/3796195.3796213

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,238	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD	5.093636e-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.00052102434
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
863	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013531835
1,072	Regret-Minimizing Representative Databases	2010	VLDB	0.0001230281
1,340	Responsible Data Management	2020	VLDB	0.00011111667
1,597	Designing Fair Ranking Schemes	2019	SIGMOD	0.00010246472
4,382	Slice Tuner: A Selective Data Acquisition Framework for Accurate and Fair Machine Learning Models	2021	SIGMOD	6.7331832e-05
5,489	Through the Fairness Lens: Experimental Analysis and Evaluation of Entity Matching	2023	VLDB	6.200289e-05
5,510	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.1919207e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
6,293	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	5.9247942e-05
6,592	RRR: Rank-Regret Representative	2019	SIGMOD	5.830041e-05
6,854	iFlipper: Label Flipping for Individual Fairness	2023	SIGMOD	5.753578e-05
7,358	PreFair: Privately Generating Justifiably Fair Synthetic Data	2023	VLDB	5.6344213e-05
7,838	Consistent Range Approximation for Fair Predictive Modeling	2023	VLDB	5.5343411e-05
9,388	Chameleon: Foundation Models for Fairness-aware Multi-modal Data Augmentation to Enhance Coverage of Minorities	2024	VLDB	5.2755515e-05
9,389	Fairness in Preference Queries: Social Choice Theories Meet Data Management	2024	VLDB	5.2755515e-05
9,393	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB	5.2755515e-05
10,238	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD	5.093636e-05
10,823	Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups	2025	VLDB	5.093636e-05
11,174	FairHash: A Fair and Memory/Time-efficient Hashmap	2024	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,419	Equitable Top-k Results for Long Tail Data	2023	SIGMOD
2	9,220	Satisfying Complex Top-k Fairness Constraints by Preference Substitutions	2023	VLDB
3	3,623	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS
4	10,238	Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor	2026	SIGMOD
5	5,489	Through the Fairness Lens: Experimental Analysis and Evaluation of Entity Matching	2023	VLDB
6	7,507	Models and Mechanisms for Spatial Data Fairness	2023	VLDB
7	5,631	Tailoring Data Source Distributions for Fairness-aware Data Integration	2021	VLDB
8	11,175	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD
9	11,174	FairHash: A Fair and Memory/Time-efficient Hashmap	2024	SIGMOD
10	9,393	Happiness Maximizing Sets under Group Fairness Constraints	2023	VLDB