| dc.identifier.uri | http://hdl.handle.net/11401/77252 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Thesis | |
| dcterms.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. | |
| dcterms.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. | |
| dcterms.available | 2017-09-20T16:52:17Z | |
| dcterms.contributor | Gao, Jie | en_US |
| dcterms.contributor | Chen, Jing | en_US |
| dcterms.contributor | Gu, Xianfeng David. | en_US |
| dcterms.creator | Srinivasan, Gowtham | |
| dcterms.dateAccepted | 2017-09-20T16:52:17Z | |
| dcterms.dateSubmitted | 2017-09-20T16:52:17Z | |
| dcterms.description | Department of Computer Science | en_US |
| dcterms.extent | 19 pg. | en_US |
| dcterms.format | Application/PDF | en_US |
| dcterms.format | Monograph | |
| dcterms.identifier | http://hdl.handle.net/11401/77252 | |
| dcterms.issued | 2016-12-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2017-09-20T16:52:17Z (GMT). No. of bitstreams: 1
Srinivasan_grad.sunysb_0771M_12876.pdf: 217572 bytes, checksum: f392536c11b12851ddd71341ea1f0acb (MD5)
Previous issue date: 1 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | NP hard in the strong sense, Provision after wait, Provision after wait in health care, pseudo polynomial time, strong NP hardness, vertex cover | |
| dcterms.subject | Computer science | |
| dcterms.title | The Computational Complexity of the Provision-after-Wait Problem in Healthcare | |
| dcterms.type | Thesis | |
