Krzysztof Rogowski

Improved Approximation Ratio for Strategyproof Facility Location on a Cycle

We study the problem of design of strategy-proof in expectation (SP) mechanisms for facility location on a cycle, with the objective of minimizing the sum of costs of n agents. We show that there exists an SP mechanism that attains an approximation ratio of 7/4 with respect to the sum of costs of th