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

doi:10.1016/j.ejor.2019.07.047

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

2021-03-01

0

PRE

AI

DOI：10.1016/j.ejor.2019.07.047

原文链接

原文求助

摘要

En 中文

Braverman et al. [Math. Oper. Res. 41(1), (2016), pp. 352-376], introduce the problem Provision-after-Wait which is to find a stable (envy 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 + epsilon times. We also present polynomial algorithms for the cases of Ordered Knapsack, in which the number of distinct input parameters is fixed. (C) 2019 Elsevier B.V. All rights reserved.

Keyword:

Scheduling

Resource allocation

Healthcare

Knapsack problem

FPTAS

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

摘要

AI总结

期刊

机构

引用论文