An official website of the United States government
We develop recursions for computing the mean and variance of the number of pooled tests needed by the halving scheme to determine the disease positive members of a population. It is assumed that each population member is independently positive with probability p, that the individual blood samples can be pooled to test whether or not at least one member of that pooled group is positive, and that a positive tested group is then split in half and the process continued.
more »
« less
New Algorithms and Bounds for Halving Pseudolines
LetPbe a set of points in general position in the plane. Ahalving lineofPis a line passing through two points ofPand cuttingthe remainingn−2 points in a half (almost half ifnis odd). Gener-alized configurations of points and their representations using allowablesequences are useful for bounding the number of halving lines.We study a problem of finding generalized configurations of pointsmaximizing the number of halving pseudolines. We develop algorithmsfor optimizing generalized configurations of points using the new notionofpartial allowable sequenceand the problem of computing a partialallowable sequence maximizing the number ofk-transpositions. It canbe viewed as a sorting problem using transpositions of adjacent elementsand maximizing the number of transpositions at positionk.We show that this problem can be solved inO(nkn) time for anyk>2, and inO(nk)timefork=1,2. We develop an approach for opti-mizing allowable sequences. Using this approach, we find new bounds forhalving pseudolines for evenn,n≤100.
more »
« less
- Award ID(s):
- 1718994
- PAR ID:
- 10196126
- Date Published:
- Journal Name:
- LNCS
- Volume:
- 12016
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We prove that among all 1-periodic configurations $$\Gamma $$ of points on the real line $$\mathbb{R}$$ the quantities $$\min _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$$ and $$\max _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$$ are maximized and minimized, respectively, if and only if the points are equispaced and whenever the number of points $$n$$ per period is sufficiently large (depending on $$\alpha $$). This solves the polarization problem for periodic configurations with a Gaussian weight on $$\mathbb{R}$$ for large $$n$$. The first result is shown using Fourier series. The second result follows from the work of Cohn and Kumar on universal optimality and holds for all $$n$$ (independent of $$\alpha $$).more » « less
-
Lossy compression has been employed to reduce the unprecedented amount of data produced by today's large-scale scientific simulations and high-resolution instruments. To avoid loss of critical information, state-of-the-art scientific lossy compressors provide error controls on relatively simple metrics such as absolute error bound. However, preserving these metrics does not translate to the preservation of topological features, such as critical points in vector fields. To address this problem, we investigate how to effectively preserve the sign of determinant in error-controlled lossy compression, as it is an important quantity of interest used for the robust detection of many topological features. Our contribution is three-fold. (1) We develop a generic theory to derive the allowable perturbation for one row of a matrix while preserving its sign of the determinant. As a practical use-case, we apply this theory to preserve critical points in vector fields because critical point detection can be reduced to the result of the point-in-simplex test that purely relies on the sign of determinants. (2) We optimize this algorithm with a speculative compression scheme to allow for high compression ratios and efficiently parallelize it in distributed environments. (3) We perform solid experiments with real-world datasets, demonstrating that our method achieves up to 440% improvements in compression ratios over state-of-the-art lossy compressors when all critical points need to be preserved. Using the parallelization strategies, our method delivers up to 1.25X and 4.38X performance speedup in data writing and reading compared with the vanilla approach without compression.more » « less
-
In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the $$\ell_2$$-metric space and the goal is to find the minimum-cost tree connecting them. Additional points (called Steiner points) from the space can be introduced as nodes in the solution. The seminal works of Arora [JACM'98] and Mitchell [SICOMP'99] provide a Polynomial Time Approximation Scheme (PTAS) for solving the Euclidean Steiner Tree problem in fixed dimensions. However, the problem remains poorly understood in higher dimensions (such as when the dimension is logarithmic in the number of terminals) and ruling out a PTAS for the problem in high dimensions is a notoriously long standing open problem (for example, see Trevisan [SICOMP'00]). Moreover, the explicit construction of optimal Steiner trees remains unknown for almost all well-studied high-dimensional point configurations. Furthermore, a vast majority the state-of-the-art structural results on (high-dimensional) Euclidean Steiner trees were established in the 1960s, with no noteworthy update in over half a century. In this paper, we revisit high-dimensional Euclidean Steiner trees, proving new structural results. We also establish a link between the computational hardness of the Euclidean Steiner Tree problem and understanding the optimal Steiner trees of regular simplices (and simplicial complexes), proposing several conjectures and showing that some of them suffice to resolve the status of the inapproximability of the Euclidean Steiner Tree problem. Motivated by this connection, we investigate optimal Steiner trees of regular simplices, proving new structural properties of their optimal Steiner trees, revisiting an old conjecture of Smith [Algorithmica'92] about their optimal topology, and providing the first explicit, general construction of candidate optimal Steiner trees for that topology.more » « less
-
Vallan, Alberto (Ed.)Concentric ring electrodes are noninvasive and wearable sensors for electrophysiological measurement capable of estimating the surface Laplacian (second spatial derivative of surface potential) at each electrode. Previously, progress was made toward optimization of inter-ring distances (distances between the recording surfaces of a concentric ring electrode), maximizing the accuracy of the surface Laplacian estimate based on the negligible dimensions model of the electrode. However, this progress was limited to tripolar (number of concentric rings n equal to 2) and quadripolar (n = 3) electrode configurations only. In this study, the inter-ring distances optimization problem is solved for pentapolar (n = 4) and sextopolar (n = 5) concentric ring electrode configurations using a wide range of truncation error percentiles ranging from 1st to 25th. Obtained results also suggest consistency between all the considered concentric ring electrode configurations corresponding to n ranging from 2 to 5 that may allow estimation of optimal ranges of inter-ring distances for electrode configurations with n ≥ 6. Therefore, this study may inform future concentric ring electrode design for n ≥ 4 which is important since the accuracy of surface Laplacian estimation has been shown to increase with an increase in n.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-39219-2_37
