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: 13132
Venue: VLDB
Year: 2023
Pagerank: 4.3690661e-05
Overall Rank: 9,246 | 35.68%
DOI: 10.14778/3565816.3565830

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,223	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB	4.1945683e-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.00014270817
1,404	Responsible Data Management	2020	VLDB	0.00012174977
1,597	Designing Fair Ranking Schemes	2019	SIGMOD	0.00011209846
2,478	Computing k-Regret Minimizing Sets	2014	VLDB	8.6927744e-05
2,615	Interactive Regret Minimization	2012	SIGMOD	8.4473503e-05
5,116	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6830089e-05
5,255	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	5.6013035e-05
5,904	k-Regret Queries with Nonlinear Utilities	2015	VLDB	5.2790141e-05
6,816	RRR: Rank-Regret Representative	2019	SIGMOD	4.9173197e-05
6,834	A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems	2020	VLDB	4.9117328e-05
7,559	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	4.7107487e-05
9,772	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856106e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,596	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	6.0590268e-05
6,467	Tailoring Data Source Distributions for Fairness-aware Data Integration	2021	VLDB	5.0528156e-05
7,632	Rank Aggregation with Proportionate Fairness	2022	SIGMOD	4.6915165e-05
1,597	Designing Fair Ranking Schemes	2019	SIGMOD	0.00011209846
9,712	Maximizing Fair Content Spread via Edge Suggestion in Social Networks	2022	VLDB	4.299267e-05
12,351	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	4.1945683e-05
10,960	FairHash: A Fair and Memory/Time-efficient Hashmap	2024	SIGMOD	4.1945683e-05
10,223	On Fair Epsilon Net and Geometric Hitting Set	2026	VLDB	4.1945683e-05
10,961	Faster Algorithms for Fair Max-Min Diversification in Rd	2024	SIGMOD	4.1945683e-05
8,972	Satisfying Complex Top-k Fairness Constraints by Preference Substitutions	2023	VLDB	4.4187185e-05