Unavailability of appropriate diagnostic capability is a major constraint in scaling up HIV early infant diagnosis (EID) programs in resource-limited countries. Due to the complexity of the existing diagnostic technology, most EID networks are highly centralized with a few laboratories serving a large number of health facilities. This leads to long diagnostic delays and consequent failure of patients to collect results in a timely manner. Several point-of-care (POC) devices that provide rapid diagnosis within the health facilities are being developed to mitigate these drawbacks of the centralized EID networks. We argue that the decision of which facilities should receive the POC device (the placement plan) is critical to maximizing their public health impact in the presence of tight budget constraints. To formalize this argument, we develop an operational queueing network submodel that quantifies the impact of POC placement decision on the diagnostic delay and link it to a patient behavior submodel that quantifies the impact of diagnostic delay on the likelihood of result collection. We embed these two submodels within an optimization model that maximizes the number of patients receiving results, which has the structure of a nonlinear, nonseparable knapsack problem and is not amenable to exact analysis. Hence, we adopt a two-pronged solution approach. First, we approximate the patient behavior submodel with a piecewise linear relationship between the average diagnostic delay at a health facility and the fraction of results collected at that facility. We also approximate the operational dynamics using extant results on queueing networks with batched service and superposition of arrival streams. In addition, we use auxiliary variables and constraints to linearize the approximate formulation and use it to derive an ``optimal'' placement solution. Second, we develop a computational model by combining a detailed discrete event simulation of the exact operational dynamics with a Monte Carlo simulation of the exact patient behavior. We calibrate the computational model with data from the EID program in an East African country and evaluate the impact of the optimal allocation described above and two thumb rules that have practical appeal. We find that the optimal allocation can result in up to 30% more patients collecting their results compared to the thumb rules. A thumb rule that allocates POC devices to highest volume health facilities performs well if the accuracy of the POC device is sufficiently high and if patients are not very sensitive to delay. In contrast, a thumb rule of allocating POC devices to minimize average diagnostic delay in the network performs well if patients are very sensitive to delay. Finally, we show that the effectiveness of POC devices is much higher than other conventional interventions such as increased laboratory capacity, reduced transportation delay, and more regularized transport that are aimed at improving the laboratory network operations.