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

Mikhail Y. Kovalyov, Erwin Pesch and Alain Quilliot

European Journal of Operational Research, 2021, vol. 289, issue 3, 1008-1012

Abstract: 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+ε times. We also present polynomial algorithms for the cases of Ordered Knapsack, in which the number of distinct input parameters is fixed.

Keywords: Scheduling; Resource allocation; Healthcare; Knapsack problem; FPTAS (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719306265
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:3:p:1008-1012

DOI: 10.1016/j.ejor.2019.07.047

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().