TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 28.11.2019


Page Content

to Navigation

Reachable Object in Paths and Cycles or "Good Things Come to Those Who Swap on Tour"

Matthias Bentert (TU Berlin)


We study a simple exchange market, introduced by Gourvès, Lesca and Wilczynski (IJCAI'17), where every agent initially holds a single object. The agents have preferences over the objects, and two agents may swap their objects if they both prefer the object of the other agent. The agents live in an underlying social network that governs the structure of the swaps: Two agents can only swap their objects if they are adjacent.
We investigate the Reachable Object problem, which asks whether a given starting situation can ever lead, by means of a sequence of swaps, to a situation where a given agent obtains a given object. This problem is known to be NP-complete even if the network is restricted to trees. This talk will present a polynomial-time algorithm for Reachable Object on Paths and Cycles.


Matthias Bentert
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe