Problemet med stabila äktenskap (SM) har en mängd olika praktiska tillämpningar, allt från matchande inhemska läkare till sjukhus, matchning av elever till skolor eller, mer allmänt, till en dubbelsidig marknad. I den klassiska formuleringen, n män och n kvinnor uttrycka sina preferenser (via en strikt total ordning) över medlemmarna av det andra könet. Att lösa ett SM-problem innebär att hitta ett stabilt äktenskap där stabilitet är en avundsfri föreställning: ingen man och kvinna som inte är gifta med varandra skulle båda föredra varandra framför sin partner eller att vara ogift. Vi anser att både det klassiska stabila äktenskapsproblemet och en av dess användbara variationer (betecknade SMTI (Stable Marriage with Ties och Ofullständiga listor)) där män och kvinnor uttrycker sina preferenser i form av en ofullständig preferenslista med band över en delmängd av medlemmarna av det andra könet. Matchningar är tillåtna endast med personer som visas i dessa preferenslistor, och vi försöker hitta en stabil matchning som gifter sig så många människor som möjligt. Medan SM problemet är polynom för att lösa, SMTI problemet är NP-hård. Vi föreslår att man tar itu med båda problemen genom en lokal sökstrategi, som utnyttjar problemens egenskaper för att minska grannskapets storlek och för att göra lokala rörelser effektivt. Vi utvärderar empiriskt vår algoritm för SM-problem genom att mäta dess beteende under drift och dess förmåga att provsmaka lattice för alla möjliga stabila äktenskap. Vi utvärderar vår algoritm för SMTI-problem både vad gäller dess beteende under drift och dess förmåga att hitta en maximal kardinalitet stabil äktenskap. Experimentella resultat tyder på att för SM problem, antalet steg i vår algoritm växer endast som O(n log(n)), och att det prover mycket väl uppsättningen av alla stabila äktenskap. Det är således ett rättvist och effektivt tillvägagångssätt för att skapa stabila äktenskap. Dessutom kan vår algoritm 2013, 6 592 strategi för SMTI-problem lösa stora problem, snabbt returnera stabila matchningar av stor och ofta optimal storlek, trots NP-hårdheten i detta problem.
I REF introducerar författarna en lokal sökstrategi som utnyttjar egenskaperna hos problemen för att minska storleken på en statlig stadsdel.
Local Search Approaches in Stable Matching Problems
{'venue': 'Algorithms', 'journal': 'Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}