.png){kind=icon}
.png){kind=icon}
Return
Provision-after-wait with preferences ordered by difference: Tighter complexity and better approximation
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2019.07.047.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Scheduling
Resource allocation
Healthcare
Knapsack problem
FPTAS
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
View more organizations