Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case

DOI10.1007/s00453-019-00550-3zbMath1425.91345arXiv1809.08453OpenAlexW2890099492MaRDI QIDQ2415359

Olivier Spanjaard, Hugo Gilbert

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.08453

zbMATH Keywords

complexityfairnessstable marriage problemgeneralized Gini index

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Statistical methods; economic indices and measures (91B82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial optimization problems with uncertain costs and the OWA criterion
• Sex-equal stable matchings: complexity and exact algorithms
• Complexity of the sex-equal stable marriage problem
• Linear programming brings marital bliss
• Generalized Gini inequality indices
• Network flow and 2-satisfiability
• The fair OWA one-to-one assignment problem: NP-hardness and polynomial time special cases
• On solving linear programs with the ordered weighted averaging objective.
• Understanding the generalized median stable matchings
• Random matching under priorities: stability and no envy concepts
• On the complexity of achieving proportional representation
• The Geometry of Fractional Stable Matchings and Its Applications
• OWA-Based Extensions of the Chamberlin–Courant Rule
• Fairness and Rank-Weighted Utilitarianism in Resource Allocation
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• On ordered weighted averaging aggregation operators in multicriteria decisionmaking
• The Minimum Satisfiability Problem
• Algorithmics of Matching Under Preferences
• College Admissions and the Stability of Marriage

This page was built for publication: Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case