Search

Testing provides essential information for managing infectious disease outbreaks, such as the COVID‐19 pandemic. When testing resources are scarce, an important managerial decision is who to test. This decision is compounded by the fact that potential testing subjects are heterogeneous in multiple dimensions that are important to consider, including their likelihood of being disease‐positive, and how much potential harm would be averted through testing and the subsequent interventions. To increase testing coverage, pooled testing can be utilized, but this comes at a cost of increased false‐negatives when the test is imperfect. Then, the decision problem is to partition the heterogeneous testing population into three mutually exclusive sets: those to be individually tested, those to be pool tested, and those not to be tested. Additionally, the subjects to be pool tested must be further partitioned into testing pools, potentially containing different numbers of subjects. The objectives include the minimization of harm (through detection and mitigation) or maximization of testing coverage. We develop data‐driven optimization models and algorithms to design pooled testing strategies, and show, via a COVID‐19 contact tracing case study, that the proposed testing strategies can substantially outperform the current practice used for COVID‐19 contact tracing (individually testing those contacts with symptoms). Our results demonstrate the substantial benefits of optimizing the testing design, while considering the multiple dimensions of population heterogeneity and the limited testing capacity.

Community detection is an important methodology for understanding the intrinsic structure and function of complex networks. Because overlapping community is one of the characteristics of real-world networks and should be considered for community detection, in this article, we propose an algorithm, called link-based label propagation algorithm (LinkLPA), to detect overlapping communities. Because the link partition is conceptually natural for the problem of overlapping community detection, LinkLPA first transforms node partition problem into link partition problem and employs a new label propagation algorithm with preference on links instead of nodes to detect communities due to the simplicity and efficiency of label propagation algorithm. Then the proposed LinkLPA performs a postprocessing to refine the detected overlapping communities by avoiding over-overlapping and incorrect partition of weak ties. Experimental results on a large number of real-world and synthetic networks show that the proposed method achieves high accuracy on detecting overlapping communities in networks.

Operating at different manufacturing steps, multiphase modeling and analysis of the batch process are advantageous to improving monitoring performance and understanding manufacturing processes. Although many phase partition algorithms have been proposed, they have some disadvantages and cause problems: (1) time sequence disorder, which requires elaborate post-treatments; (2) a lack of quantitative index to indicate transition patterns; and (3) tunable parameters that cannot be quantitatively determined. To effectively overcome these problems, an iterative two-step sequential phase partition algorithm is proposed in the present work. In the first step, initial phase partition results are obtained by checking changes of the control limit of squared prediction error. Sequentially, the fast search and find of density peaks clustering algorithm is employed to adjust the degradation degree and update the phase partition results. These two steps are iteratively executed until a proper degradation degree is found for the first phase. Then, the remaining phases are processed one by one using the same procedure. Moreover, a statistical index is quantitatively defined based on density and distance analysis to judge whether a process has transitions, and when the transition regions begin and end. In this way, the phases and transition patterns are quantitatively determined without ambiguity from the perspective of monitoring performance. The effectiveness of the proposed method is illustrated by a numerical example and a typical industrial case. Several typical phase partition algorithms are also employed for comprehensive comparisons with the proposed method. © 2016 American Institute of Chemical Engineers AIChE J, 62: 2358–2373, 2016

Multiplicity of phases as indicated by changes of process characteristics is an inherent nature of many batch processes for both normal and fault cases. To more efficiently perform online fault diagnosis via reconstruction for multiphase batch processes, the phase nature and the relationship between normal and fault cases within each phase should be deeply addressed. This article proposes a quality-relevant fault diagnosis strategy with concurrent phase partition and analysis of relative changes for multiphase batch processes. First, a concurrent phase partition algorithm is developed. The basic idea is to track the changes of process characteristics at normal and fault statuses jointly so that multiple sequential modeling phases are identified simultaneously for both normal and fault cases. Then, the relative changes from the normal status to each fault case are analyzed in each phase to reveal the specific fault effects more efficiently. The fault effects are decomposed in two different monitoring subspaces, principal subspace, and residual subspace, by capturing their different roles in removing out-of-control signals. The significant increases relative to the normal case are judged to be responsible for the concerned alarm monitoring statistics in each phase. The others are composed of general variations that are deemed to still follow normal rules and thus insignificant to remove alarm monitoring statistics. Those alarm-responsible fault deviations are then used to develop reconstruction models which can more efficiently recover the fault-free part for online fault diagnosis. The proposed algorithm is illustrated with a typical multiphase batch process with one normal case and three fault cases. © 2014 American Institute of Chemical Engineers AIChE J, 60: 2048–2062, 2014

In this article we study the monochromatic cycle partition problem for non-complete graphs. We consider graphs with a given independence number α(G) = α. Generalizing a classical conjecture of Erdos, Gyarfas and Pyber, we conjecture that if we r-color the edges of a graph G with α(G) = α, then the vertex set of G can be partitioned into at most αr vertex disjoint monochromatic cycles. In the direction of this conjecture we show that under these conditions the vertex set of G can be partitioned into at most 25(αr)2log(αr) vertex disjoint monochromatic cycles. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 57–64, 2010 © 2011 Wiley Periodicals, Inc.

Path restoration (PR) is one of the basic mechanisms for securing telecommunication networks against failures. In the paper, we discuss the complexity of certain variants of a multi-commodity flow network optimisation problem in directed graphs related to state-independent path restoration mechanisms. We demonstrate that most variants of the considered problem are NP-hard. Depending on the variant, we show how the problem can be reduced either from the partition problem or from the problem of finding an arc-disjoint pair of paths that connect two distinct pairs of nodes. We also demonstrate that at the same time the considered problem is difficult to approximate. The complexity results of the paper are important as they can help to devise proper algorithms for resilient network design tools. Copyright (C) 2009 John Wiley & Soils, Ltd. (Less)

The topological analysis of grids of data is used for determination of surfaces or volumes around maxima. The volumes are then related to chemical information such as atoms or bonds, and can be used for integration of local properties such as electronic population. The problem of global connectivity is reversed into the question of local connectivity yielding a linear scaling partition algorithm. Two packages are developed for a very fast analysis and partition of 2D or 3D grids of data, applications being made to C2H2, C2H4, C6H6, H2CO, and H2CS molecules using the Atoms in Molecule (AIM) or Electron Localization Function (ELF).

This paper focuses on the problem of developing a partition of n objects based on the information in a symmetric, non-negative dissimilarity matrix. The goal is to partition the objects into a set of non-overlapping subsets with the objective of minimizing the sum of the within-subset dissimilarities. Optimal solutions to this problem can be obtained using dynamic programming, branch-and-bound and other mathematical programming methods. An improved branch-and-bound algorithm is shown to be particularly efficient. The improvements include better upper bounds that are obtained via a fast exchange algorithm and, more importantly, sharper lower bounds obtained through sequential solution of submatrices. A modified version of the branch-and-bound algorithm for minimizing the diameter of a partition is also presented. Computational results for both synthetic and empirical dissimilarity matrices reveal the effectiveness of the branch-and-bound methodology.

Motivated by a problem arising in the design of telecommunications networks using the SONET standard, we consider the problem of covering all edges of a graph using subgraphs that contain at most k edges with the objective of minimizing the total number of vertices in the subgraphs. We show that the problem is -hard when k ≥ 3 and present a linear-time -approximation algorithm. For even k values, we present an approximation scheme with a reduced ratio but with increased complexity. © 2002 Wiley Periodicals, Inc.

Assume that a rectangle R is given on the Euclidean plane together with a finite set P of points that are interior to R. A rectangular partition of R is a partition of the surface of R into smaller rectangles. The length of such a partition equals the sum of the lengths for the line segments that define it. The partition is said to be feasible if no point of P is interior to a partition rectangle. The Rectangular Partitioning Problem (RPP) seeks a feasible rectangular partition of R with the least length. Computational evidence from the literature indicates that RPPs with noncorectilinear points in P, denoted NCRPPs, are the hardest to solve to proven optimality. In this paper, some structural properties of optimal feasible NCRPP partitions are presented. These properties allow substantial reductions in problem input size to be carried out. Additionally, a stronger formulation of the problem is also made possible. Based on these ingredients, a hybrid Lagrangian Relaxation—Linear Programming Relaxation exact solution algorithm is proposed. Such an algorithm has proved capable of solving NCRPP instances more than twice as large as those found in the literature. © 2002 Wiley Periodicals, Inc.

In this paper, we derive an efficient parallel algorithm to solve the single function coarsest partition problem. This algorithm runs in O(\log2n) time using O(nlogn) operations on the EREW PRAM with O(n) memory cells used. Compared with the previous PRAM algorithms that consume O(n1+) memory cells for some positive constant ${\varepsilon}\>0$, our algorithm consumes less memory cells without increasing the total number of operations.

Architectural scenes usually have some peculiar properties, like parallel surfaces, symmetry, instantiation, easy clustering, etc. These properties can be used by visualization algorithms in order to improve the solution of the hidden surface removal problem. This paper presents some practical implementation policies for the binary space partition algorithm proposed by Fuchs. They take advantage of the characteristics found in architectural scenes. These suggestions help to minimize both the time needed to build the tree and the memory space used. Five optimization techniques are presented and applied to fourteen architectural scenes.

Let R = (V, E) be a unidirectional ring network where V corresponds to the set of nodes and E corresponds to the set of directed communication links. A partition of R divides R into several disjoint chains. For each partition P, there is associated a communication cost C(P). The optimal ring partition problem is to find a partition P* of R such that C(P*) = minpC(P). In this paper, we first formulate the ring partition problem into a recurrence relation. By solving the recurrence relation, we show that the ring partition can be accomplished distributively in one pass, i.e., the message complexity of our distributed ring partition algorithm is O(|V|), which is optimal. © 1993 by John Wiley & Sons, Inc.

The Hopfield neural network is attracting attention as a high-speed solver for optimization and other problems. However, it contains a problem in that the network may not arrive at the globally optimal solution but stops at a locally optimal solution unless the initial state is selected appropriately. In other words, the selection of the initial state is important in solving a problem using the Hopfield neural network. This paper considers the real number partition problem, the problem of finding the k largest elements from a given set of real numbers, given integer k. A network to solve this problem is constructed. It is shown that the network arrives at the globally optimal solution if the initial state satisfies a certain condition. Its basin also is examined. As an application example of the network, the sorting problem is considered.

In this paper, an algorithm is developed for the subset sum problem in connection with public key cryptosystems. It is known that the subset sum problem based on a super-increasing sequence of numbers can be solved simply and in a polynomial time. It is known also that the subset sum problem based on general sequences of numbers is NP-hard, and the difficulty of the problem varies especially depending on the density. Thus, this paper proposes an algorithm using modular arithmetic for the subset sum problem based on general sequences of numbers. The basic idea of this algorithm is that “the largest number in a sequence of numbers A= (a1, …, an) is transformed to a super-increasing number by modular arithmetic.” The advantages of the algorithm are investigated by experiment, and it is shown that by the properties of problems used, this algorithm is an effective method for the subset sum problem based on general sequences of numbers, especially “the case where the density is close to 1,” where the existing method is weak.

The problem of illuminating the boundary of sets having constant width is considered and a bound for the number of directions needed is given. As a corollary, an estimate for Borsuk’s partition problem is inferred. Also, the illumination number of sufficiently symmetric strictly convex bodies is determined.

A fundamental unsolved problem in the programming area is one in which various activities have fixed charges (e.g., set-up time charges) if operating at a positive level. Properties of a general solution to this type problem are discussed in this paper. Under special circumstances it is shown that a fixed charge problem can be reduced to an ordinary linear programming problem.