## Provision-after-wait with preferences ordered by difference : tighter complexity and better approximation

- Braverman et al. [Math. Oper. Res. 41(1), (2016), pp. 352–376], introduce the problem Provision-after-Wait which is to find a stable (ey free) assignment of n patients to m hospitals, and their waiting times before admission, such that the social welfare is maximized, subject to a limited budget. Chan et al. [ACM Trans. Econ. Comput. 5(2), (2017), Article 12, pp. 12:1–12:36] focus on a natural case of d-ordered preferences, in which patients are ordered according to the differences of their values between consecutive hospitals. For this case, they provide a sophisticated proof of ordinary NP-hardness, reduce it to the problem called Ordered Knapsack, and develop a fully polynomial time approximation scheme for Ordered Knapsack. We present a simple proof that Ordered Knapsack is NP-hard, which implies NP-hardness of a more restrictive case of the original problem, and present an alternative fully polynomial time approximation scheme with a reduced run time by a quadratic factor of n, for a fixed m. A similar algorithm is developed to find a solution for which the social welfare is as high as for the optimal solution of Ordered Knapsack, and the budget limit can be exceeded by at most 1-ε times. We also present polynomial algorithms for the cases of Ordered Knapsack, in which the number of distinct input parameters is fixed.

Document Type: | Article |
---|---|

Language: | English |

Author: | Mikhail Y. KovalyovORCiD, Erwin PeschORCiD, Alain Quilliot |

Center: | Center for Advanced Studies in Management (CASiM) |

DOI: | https://doi.org/10.1016/j.ejor.2019.07.047 |

Parent Title (English): | European Journal of Operational Research : EJOR |

ISSN: | 0377-2217 |

Volume: | 289 |

Year of Completion: | 2021 |

First Page: | 1008 |

Last Page: | 1012 |

Tag: | Healthcare; Knapsack problem; Resource allocation; Scheduling |

Content Focus: | Academic Audience |

Peer Reviewed: | Yes |

Rankings: | AJG Ranking / 4 |

VHB Ranking / A | |

SJR Ranking / Q1 | |

Licence (German): | Urheberrechtlich geschützt |