Processing math: 100%

Jiehua Chen

Paper appeared at ESA 2022 (Track A): Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space

Posted on by Jiehua Chen

Summary
We investigate the Euclidean 𝖽-Dimensional Stable Roommates problem, which asks whether a given set V of 𝖽n points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets Π=$V1,,Vn$with V_i = 𝖽foreachV_i \in \Pisuchthat\Pi$$ is {stable}.
Here, stability means that no point subset WV is blocking Π, and W is said to be blocking Π if $$ W = 𝖽suchthat\Sigma_{w’ \in W} \delta(w,w’) < \Sigma_{v \in \Pi(w)}\delta(w,v)holdsforeachpointw \in W,where\Pi(w)denotesthesubsetV_i \in \Piwhichcontainswand\delta(a,b)denotestheEuclideandistancebetweenpointsaandb.Complementingtheexistingknownpolynomialtimeresultfor𝖽 = 2,weshowthatsuchpolynomialtimealgorithmscannotexistforanyfixednumber𝖽 \ge 3unlessP=NP.Ourresultfor𝖽 = 3$$ answers a decade-long open question in the theory of Stable Matching and Hedonic Games [Iwama et al., 2007; Arkin et al., 2009; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; David F. Manlove, 2013].

====================================

The conference version and the long version of the paper can be found at ESA22 and on arXiv.