Exact and Approximate Heuristics for the Multi-modal Stable Matching with Applications in Industry Chains
摘要
In this paper, we tackle the multi-modal globally stable matching problem (MGBSM), a challenge crucial for optimizing industry chain partnerships where agents generate preferences based on various criteria. The goal is to achieve a perfect matching where every agent is paired with a partner, and no unmatched pair prefers each other over their current partners across all criteria. Given the NP-hard nature of this problem, the only exact solution method to date requires exhaustive enumeration of all stable matchings. Our key contribution is the development of efficient algorithms to solve MGBSM, beginning with its transformation into a clique problem in graph theory. By harnessing the properties of both stable matchings and cliques, we design an exact algorithm that efficiently determines the existence of a multi-modal globally stable matching and provides a solution when one exists. Recognizing the limitations of perfect matching, especially in practical industry chain scenarios, we introduce the concept of multi-modal group stable matching (MGSM), which relaxes the perfect matching requirement. We focus on identifying the maximum cardinality MGSM (MaxMGSM) and develop a polynomial-time, approximation-preserving reduction from MaxMGSM to the maximum clique problem. This is followed by a fast polynomial-time approximation algorithm with a provable performance guarantee, offering a practical solution for complex industry chain networks.