Type
Text
Type
Thesis
Advisor
Chen, Jing | Gao, Jie | Gu, Xianfeng David.
Date
2016-12-01
Keywords
Computer science | NP hard in the strong sense, Provision after wait, Provision after wait in health care, pseudo polynomial time, strong NP hardness, vertex cover
Department
Department of Computer Science
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/77252
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
In Provision-after-Wait in Healthcare (PaW), a social planner operating on a constrained budget is required to sponsor medical treatments to a population of patients. Specifically, each patient is allocated to any of the k hospitals to receive a single unit of medical treatment. The cost of treatment depends upon the hospital and is paid for by the planner. Associated with every patient is a set of k non-negative numbers which denote the patients’ preference or intrinsic value towards getting treated in each of the k hospitals. Since the patients do not pay for the treatment and the planner cannot afford to send each patient to their most preferred hospital, waiting times are used to ration access to over-demanded hospitals. The social planner is responsible for assigning patients and computing the waiting time of each hospital, so that the social welfare is maximized under budget constraints. It has already been proved that finding optimal equilibrium assignments that maximize social welfare is NP-hard. Besides that, little is known about the complexity of PaW. For instance, it is not clear whether it permits an FPTAS or is fixed parameter tractable with respect to the number of hospitals. In this work, we study the complexity of PaW and prove it to be NP-hard even if all the values are polynomially bounded in the length of the input. Since PaW is a number problem, this proves that it is NP-hard in the strong sense and, as a consequence, there is no FPTAS for PaW unless P = NP. In addition, we explore various special cases of PaW, their complexity and related algorithms to resolve the problem. | In Provision-after-Wait in Healthcare (PaW), a social planner operating on a constrained budget is required to sponsor medical treatments to a population of patients. Specifically, each patient is allocated to any of the k hospitals to receive a single unit of medical treatment. The cost of treatment depends upon the hospital and is paid for by the planner. Associated with every patient is a set of k non-negative numbers which denote the patients’ preference or intrinsic value towards getting treated in each of the k hospitals. Since the patients do not pay for the treatment and the planner cannot afford to send each patient to their most preferred hospital, waiting times are used to ration access to over-demanded hospitals. The social planner is responsible for assigning patients and computing the waiting time of each hospital, so that the social welfare is maximized under budget constraints. It has already been proved that finding optimal equilibrium assignments that maximize social welfare is NP-hard. Besides that, little is known about the complexity of PaW. For instance, it is not clear whether it permits an FPTAS or is fixed parameter tractable with respect to the number of hospitals. In this work, we study the complexity of PaW and prove it to be NP-hard even if all the values are polynomially bounded in the length of the input. Since PaW is a number problem, this proves that it is NP-hard in the strong sense and, as a consequence, there is no FPTAS for PaW unless P = NP. In addition, we explore various special cases of PaW, their complexity and related algorithms to resolve the problem. | 19 pages
Recommended Citation
Srinivasan, Gowtham, "The Computational Complexity of the Provision-after-Wait Problem in Healthcare" (2016). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 3075.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/3075