Vi introducerar en ny metod för att definiera geografiska områden i vägnät med hjälp av stabil matchning. I detta tillvägagångssätt, varje geografiskt område definieras i termer av ett centrum, som identifierar en plats av intresse, såsom ett postkontor eller vallokal, och alla andra nätverk hörn måste märkas med det centrum till vilket de är associerade. Vi fokuserar på att definiera geografiska områden som är rättvisa, genom att varje distrikt har samma antal hörn och uppdraget är stabilt när det gäller geografiskt avstånd. Det vill säga, det finns inget otilldelat vertex-center par så att båda skulle föredra varandra framför deras nuvarande uppdrag. Vi löser detta problem med hjälp av en version av den klassiska stabila matchningsproblem, kallas symmetrisk stabil matchning, där preferenser för elementen i båda uppsättningar lyda en viss symmetri. Vi visar att för en planar graf eller vägnätverk med n noder och k centra, problemet kan lösas i O (n ε n log n) tid, vilket förbättrar på O (nk) körtiden att använda den klassiska Gale-Shapley stabila matchande algoritm när k är stor. Slutligen ger vi experimentella resultat på vägnät för dessa algoritmer och en heuristisk algoritm som presterar bättre än Gale-Shapley algoritm för alla typer av värden av k.
Senare, Eppstein et al. Ref övervägde ett relaterat problem med stabil matchning inom ramen för plandiagram och vägnät.
Defining Equitable Geographic Districts in Road Networks via Stable Matching
{'venue': "SIGSPATIAL'17", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}