Happiness Maximizing Sets under Group Fairness Constraints

Summary: Introduces FairHMS: select a small subset maximizing the minimum happiness ratio across all nonnegative linear utilities while enforcing per-group lower/upper cardinality bounds for representation. Proves NP-hardness for ≥3 dims, gives exact 2D IntCov, a bicriteria BiGreedy via submodular maximization under a matroid with adaptive sampling, and empirically validates efficiency and effectiveness. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13320
Venue: VLDB
Year: 2023
Pagerank: 5.2755515e-05
Overall Rank: 9,393 | 35.56%
DOI: 10.14778/3565816.3565830

Incoming Non-self Citations Over Time

Authors

1. Jiping Zheng (Nanjing University; State Key Laboratory for Novel Software Technology)
2. Yuan Ma (Nanjing University)
3. Wei Ma (Nanjing University)
4. Yanhao Wang (East China Normal University)
5. Xiaoyang Wang (University of New South Wales)

BibTeX Citation

@article{zheng_vldb23,
        title = {{Happiness Maximizing Sets under Group Fairness Constraints}},
        author = {Zheng, Jiping and Ma, Yuan and Ma, Wei and Wang, Yanhao and Wang, Xiaoyang},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {2},
        pages = {291--303},
        doi = {10.14778/3565816.3565830},
        url = {https://doi.org/10.14778/3565816.3565830},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,511	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
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
2,063	Computing k-Regret Minimizing Sets	2014	VLDB	9.2399169e-05
2,491	Interactive Regret Minimization	2012	SIGMOD	8.5086491e-05
4,727	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.5362946e-05
4,939	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	6.4336325e-05
5,654	k-Regret Queries with Nonlinear Utilities	2015	VLDB	6.1330869e-05
6,592	RRR: Rank-Regret Representative	2019	SIGMOD	5.830041e-05
6,786	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB	5.7740702e-05
7,305	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	5.6501646e-05
9,899	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	5.1997534e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,305	Weighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation	2026	SIGMOD
2	5,631	Tailoring Data Source Distributions for Fairness-aware Data Integration	2021	VLDB
3	7,449	Rank Aggregation with Proportionate Fairness	2022	SIGMOD
4	9,848	Maximizing Fair Content Spread via Edge Suggestion in Social Networks	2022	VLDB
5	1,597	Designing Fair Ranking Schemes	2019	SIGMOD
6	12,544	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB
7	11,174	FairHash: A Fair and Memory/Time-efficient Hashmap	2024	SIGMOD
8	10,511	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB
9	11,175	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD
10	9,220	Satisfying Complex Top-k Fairness Constraints by Preference Substitutions	2023	VLDB