Computational aspects of assigning agents to a line

Aziz, Haris;Hougaard, Jens Leth;Moreno-Ternero, Juan de Dios;Osterdal, Lars Peter
(2016) , 21 pages

Files

coredp2016_54web.pdf
  • Open Access
  • Adobe PDF
  • 401.1 KB
Download

Details

Authors
  • Aziz, HarisUniversity of New South Wales
    Author
  • Hougaard, Jens LethUniversity of Copenhagen
    Author
  • Moreno-Ternero, Juan de DiosUniversidad Pablo de Olavide and CORE, UCL
    Author
  • Osterdal, Lars PeterUniversity of Copenhagen
    Author
Abstract
We consider the problem of assigning agents to slots on a line, where only one agent can be served at a slot and each agent prefers to be served as close as possible to his target. We introduce a general approach to compute aggregate gap-minimizing assignments, as well as gap-egalitarian assignments. The approach relies on an algorithm which is shown to be faster than general purpose algorithms for the assignment problem. We also extend the approach to probabilistic assignments and explore the computational features of existing, as well as new, methods for this setting.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Aziz, H., Hougaard, J. L., Moreno-Ternero, J. d. D., & Osterdal, L. P. (2016). Computational aspects of assigning agents to a line (CORE Discussion Papers 2016/54). https://hdl.handle.net/2078.5/182272