Research map / Graph learning / Graph algorithms and clustering
Exploring Algorithmic Fairness in Robust Graph Covering Problems
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, Milind Tambe
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add maximin group fairness constraints to robust graph covering | greedy robust covering · SPY3 network, Hispanic coverage | worst-case coverage of worst-off group (%): 33 -> 44 | Improved |
| add maximin group fairness constraints to robust graph covering | greedy robust covering · MFP1 network, Other group | worst-case coverage of worst-off group (%): 28 -> 64 | Improved |
| add fairness constraints | robust graph covering · 5 networks, I=N/3 | overall worst-case coverage (price of fairness): PoF 1.0%-4.2% | Hurt |
| increase K-adaptability from K=1 to K=2,3 (ablation) | fair robust covering · 5 networks, I=N/3, J=3 | coverage and fairness | Improved |
| add symmetry-breaking constraints to Benders' decomposition (ablation) | fair robust covering MILP · 5 networks, K=2,3 | solver speed / master problem solution | Improved |
| increase uncertainty level J (more monitor failures) | fair robust covering · 5 networks, I=N/3 | improvement in min percentage covered: 16.6 -> 10.0 (J=0 to 5) | Mixed |
| increase uncertainty level J | fair robust covering · 5 networks, I=N/3 | price of fairness (%): 0.3 -> 4.0 (J=0 to 5) | Hurt |
Closest papers by meaning
- Robust Optimization for Fairness with Noisy Protected Groups (NeurIPS 2020 · similarity 0.87)
- Balanced and Fair Partitioning of Friends (AAAI 2025 · similarity 0.86)
- FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning (AAAI 2025 · similarity 0.85)
- Fairness Shields: Safeguarding against Biased Decision Makers (AAAI 2025 · similarity 0.85)
- Individual Fairness in Graph Decomposition (ICML 2024 · similarity 0.85)
- Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
