Preprint
Metric Facility Assignment with Partial Information
ArXiv.org
04 Jun 2026
Abstract
We study an assignment problem where a set of agents and a set of facilities lie on a line metric. The goal is to compute an assignment of agents to facilities to approximately minimize the social cost (the total distance of agents from their assigned facilities) given only partial information regarding the metric. Unlike previous work which focused solely on algorithms with access to the ordinal preferences of the agents over the facilities (ORD), we also consider the value of information regarding approval preferences (APP), and inter-facility distances (DIST). For different combinations of these three information types, we establish tight bounds on the distortion of deterministic algorithms, showing that it is possible to improve over the optimal bound of3that can be achieved using only ORD information. Among other results, we show a tight bound of1+√2̅for APP+DIST which holds even for general metrics, and a tight bound of2for ORD+APP+DIST.
Metrics
1 Record Views
Details
- Title
- Metric Facility Assignment with Partial Information
- Creators
- Vasilis Gkatzelis - Drexel UniversityHasti Karimi - University of British ColumbiaEmma Rewinski - Drexel UniversityMaziar Shamsipour - University of TehranAlexandros A Voudouris - University of Essex
- Publication Details
- ArXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Economics (School of Economics); Computer Science
- Other Identifier
- 991022190262004721