Stable matching: an integer programming approach
This paper develops an integer programming approach to two-sided many-to-one matching by investigating stable integral matchings of a fictitious market where each worker is divisible. We show that stable matchings exist in a discrete matching market when firms' preference profile satisfies a total unimodularity condition that is compatible with various forms of complementarities. We provide a class of firms' preference profiles that satisfy this condition.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment
We present a convex mixed-integer programming formulation for non-rigid shape matching. To this end, we propose a novel shape deformation model based on an efficient low-dimensional discrete model, so that finding a glob…
CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
Bridging logical and algorithmic reasoning with modern machine learning techniques is a fundamental challenge with potentially transformative impact. On the algorithmic side, many NP-hard problems can be expressed as int…
An Integer Linear Programming Approach to Geometrically Consistent Partial-Partial Shape Matching
The task of establishing correspondences between two 3D shapes is a long-standing challenge in computer vision. While numerous studies address full-full and partial-full 3D shape matching, only a limited number of works …
Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods
We study a variation of the Stable Marriage problem, where every man and every woman express their preferences as preference lists which may be incomplete and contain ties. This problem is called the Stable Marriage prob…
User Association Optimization for IRS-aided Terahertz Networks: A Matching Theory Approach
Terahertz (THz) communication is a promising technology for future wireless communications, offering data rates of up to several terabits-per-second (Tbps). However, the range of THz band communications is often limited …