Linear programming brings marital bliss
From MaRDI portal
The problem of stable marriage was investigated by many authors. \textit{D. Gale} and \textit{L. S. Shapley} [Am. Math. Mon. 69, 9-15 (1962; Zbl 0109.244)], showed that regardless of the individual preferences, a stable matching always exists. \textit{R. Irving}, \textit{P. Leather} and \textit{D. Gusfield} [J. Assoc. Comput. Mach. 34, No.3, 532-543 (1987)] gave an algorithm for finding an optimal stable matching. In this paper, the author shows how to find the optimal stable matching by means of linear programming. This characterization of the stable marriage problem extends Dantzig's remark referred to the linear programming characterization of the bipartite matching problem as the monogamy is the best of all the possible forms of marriage. The author shows that among all forms of marriage monogamous stable marriage is the best.
Recommendations
Cites work
- College Admissions and the Stability of Marriage
- Every finite distributive lattice is a set of stable matchings
- Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
- scientific article; zbMATH DE number 3148878 (Why is no real title available?)
- scientific article; zbMATH DE number 4027472 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 3558960 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Stable matching with preferences derived from a psychological model
- The Complexity of Counting Stable Marriages
Cited in
(73)- Optimizing the marriage market: an application of the linear assignment model
- Characterization of stable matchings as extreme points of a polytope
- Stable matchings and linear inequalities
- On the stable b-matching polytope.
- On a cutting plane heuristic for the stable roommates problem and its applications
- A polynomial-time algorithm for the bistable roommates problem
- Satisfied two-sided matching: a method considering elation and disappointment of agents
- Equivalence of two-sided stable matching
- The object allocation problem with random priorities
- An elementary integrality proof of Rothblum's stable matching formulation
- The stable tournament problem: matching sports schedules with preferences
- Mathematical models for stable matching problems with ties and incomplete lists
- Courtship and linear programming
- On the stable marriage polytope
- Canonical monotone decompositions of fractional stable matchings
- Stable matchings and linear programming
- Bistable versions of the marriages and roommates problems
- Existence of stable outcomes and the lattice property for a unified matching market
- Compromises and rewards: stable and non-manipulable probabilistic matching
- Improving solution times for stable matching problems through preprocessing
- Bipartite choices
- Stable fractional matchings
- The rank pricing problem with ties
- A note on the lattice structure for matching markets via linear programming
- The diameter of the stable marriage polytope: bounding from below
- A characterization of strongly stable fractional matchings
- Random matching under priorities: stability and no envy concepts
- Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
- Blockers and antiblockers of stable matchings
- Stable allocations and partially ordered sets
- Marriage market with indifferences: a linear programming approach
- A matroid approach to stable matchings with lower quotas
- A branch-and-price algorithm for stable workforce assignments with hierarchical skills
- Bargaining and Competition in Matching Markets
- Stable marriages and search frictions
- Stable Matchings, Optimal Assignments, and Linear Programming
- Task assignment with controlled and autonomous agents
- Popularity, Mixed Matchings, and Self-Duality
- Understanding popular matchings via stable matchings
- Stability Representations of Many-to-One Matching Problems: An Integer Optimization Approach
- Stable marriage with general preferences
- An extendable stable matching algorithm of a kind of bipartite graph
- Quasi-popular matchings, optimality, and extended formulations
- An algorithm for the maximum weight strongly stable matching problem
- Polyhedral aspects of stable marriage
- Equitable representation and recruitment
- A matroid approach to stable matchings with lower quotas
- Affinely representable lattices, stable matchings, and choice functions
- Maximum stable matching with one-sided ties of bounded length
- Affinely representable lattices, stable matchings, and choice functions
- Efficiency and stability of probabilistic assignments in marriage problems
- Review of the theory of stable matchings and contract systems
- Counting vertices of integral polytopes defined by facets
- Stable matching: An integer programming approach
- Online 2-stage stable matching
- On the set of stable matchings in a bipartite graph
- Maximum matchings and popularity
- On stable assignments generated by choice functions of mixed type
- Adapting stable matchings to evolving preferences
- Min-cost popular matchings
- Non-distributive lattices, stable matchings, and linear optimization
- The popular matching problem in the roommates instance remains NP-hard in bounded degree graphs
- Stable matching games
- Complexity of the sex-equal stable marriage problem
- Tâtonnement in matching markets
- Matchings, relaxed popularity, and optimality
- On the number of degenerate simplex pivots
- The investment management game: extending the scope of the notion of core
- On the number of degenerate simplex pivots
- Maximum matchings and popularity
- Stable multi-skill workforce assignments
- Characterization of super-stable matchings
- Improved approximation algorithms for two variants of the stable marriage problem with ties
This page was built for publication: Linear programming brings marital bliss
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122480)
