@inproceedings{d3772fbde85544be8cee83050f57fb0a,
title = "Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio",
abstract = "In this paper, we study the two-facility location game with optional preference where the acceptable set of facilities for each agent could be different and an agent's cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. For general metrics, we design a deterministic strategyproof mechanism for the problem with approximation ratio of 1 + 2a, where a is the approximation ratio of the offline optimization version. In particular, for the setting on a line, we improve the earlier best ratio of n/2 + 1 [Yuan et al., 2016] to a ratio of 2.75.",
author = "Minming Li and Pinyan Lu and Yuhao Yao and Jialin Zhang",
note = "Publisher Copyright: {\textcopyright} 2020 Inst. Sci. inf., Univ. Defence in Belgrade. All rights reserved.; 29th International Joint Conference on Artificial Intelligence, IJCAI 2020 ; Conference date: 01-01-2021",
year = "2020",
language = "英语",
series = "IJCAI International Joint Conference on Artificial Intelligence",
publisher = "International Joint Conferences on Artificial Intelligence",
pages = "238--245",
editor = "Christian Bessiere",
booktitle = "Proceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020",
address = "美国",
}