{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T23:35:58Z","timestamp":1761176158004,"version":"build-2065373602"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"value":"9781643686318","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T00:00:00Z","timestamp":1761004800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,10,21]]},"abstract":"<jats:p>We consider the k-facility location problems with capacity constraints in bounded location space from the mechanism design perspective. In this problem, we seek to locate k capacity constrained facilities in a bounded interval (i.e., B=[bl,br]) to serve agents, who have preferences on the ideal locations of the facilities in the interval. Our goal is to design strategyproof mechanisms to elicit agents\u2019 true ideal locations and locate facilities that minimize the social cost and maximum cost, which are defined to be the sum and the maximum of the agents\u2019 costs (i.e., agents\u2019 distances to their facilities), respectively. For the equal capacity setting without spare capacity (i.e., all the agents can be served exactly), we provide a deterministic strategyproof mechanism. For any bounded interval (i.e., bl, br\u2208R), our mechanism has approximation ratios of n-1 for the social cost and 4 for the maximum cost with k\u22653 facilities and n\u22653 agents. We also establish lower bounds of n\/2 for the social cost by a common class of deterministic mechanisms that order agents from left to right, and 2 for the maximum cost by any deterministic mechanism. Our mechanism also achieves tight bounds for both costs with k&lt;3 facilities. We then consider the equal capacity setting with spare capacity and the arbitrary capacity setting without spare capacity. For these two settings and any bounded interval, we provide randomized strategyproof mechanisms with approximation ratios of n\/2 for the social cost and 2 for the maximum cost with any number of facilities. We complement this result by establishing lower bounds of 5\/3 for the social cost and 3\/2 for the maximum cost.<\/jats:p>","DOI":"10.3233\/faia250954","type":"book-chapter","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T09:46:57Z","timestamp":1761126417000},"source":"Crossref","is-referenced-by-count":0,"title":["Mechanism Design for Facility Location Problems with Capacity Constraints in Bounded Location Space"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0437-896X","authenticated-orcid":false,"given":"Xingchen","family":"Sha","sequence":"first","affiliation":[{"name":"Department of Computer Science, Northwestern University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2461-9727","authenticated-orcid":false,"given":"Hau","family":"Chan","sequence":"additional","affiliation":[{"name":"School of Computing, University of Nebraska-Lincoln, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3362-2063","authenticated-orcid":false,"given":"Vincent","family":"Chau","sequence":"additional","affiliation":[{"name":"Laboratoire IBISC, Univ-\u00c9vry, Universit\u00e9 Paris-Saclay, \u00c9vry, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7539-441X","authenticated-orcid":false,"given":"Ken C.K.","family":"Fong","sequence":"additional","affiliation":[{"name":"Department of Data Science & Artificial Intelligence, The Hong Kong Polytechnic University, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7370-6237","authenticated-orcid":false,"given":"Minming","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8954-7023","authenticated-orcid":false,"given":"Wai Lun","family":"Lo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Hong Kong Chu Hai College, Hong Kong"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2025"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA250954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T09:46:57Z","timestamp":1761126417000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA250954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,21]]},"ISBN":["9781643686318"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia250954","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,21]]}}}