Probabilistic nonadaptive group testing in the presence of errors and DNA library screening

We use the subset containment relation to construct a probabilistic nonadaptive group testing design and decoding algorithm that, in the presence of testing errors, identifies many positives in a population. We give a lower bound for the expected portion of positives identified as a function of an upper bound on the number of testing errors.The algorithms contained herein are part of The State University of New York Research Foundation invention C1230-125, Probabilistic and Combinatorial Nonadaptive and Two-Stage Group Testing and DNA Library Screening by A. Macula and K. Anne.     

The Number of Out-Pancyclic Vertices in a Strong Tournament

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it belongs to a cycle of length l for all 3 ≤ l ≤ n. We call a vertex u of T an out-pancyclic vertex of T, if each out-arc of u is pancyclic in T. Yao et al. (Discrete Appl. Math. 99, 245–249, 2000) proved that every strong tournament contains an out-pancyclic vertex. For strong tournaments with minimum out-degree 1, Yao et al. found an infinite class of strong tournaments, each of which contains exactly one out-pancyclic vertex. In this paper, we prove that every strong tournament with minimum out-degree at least 2 contains three out-pancyclic vertices. Our result is best possible since there is an infinite family of strong tournaments with minimum degree at least 2 and no more than 3 out-pancyclic vertices.     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph; the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u⁴n) and the p-partition problem can be solved in time O(p²u⁴n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width.     

Free lattice algorithms

In the late 1930s Phillip Whitman gave an algorithm for deciding for lattice terms v and u if vu in the free lattice on the variables in v and u. He also showed that each element of the free lattice has a shortest term representing it and this term is unique up to commutivity and associativity. He gave an algorithm for finding this term. Almost all the work on free lattices uses these algorithms. Building on the work of Ralph McKenzie, J. B. Nation and the author have developed very efficient algorithms for deciding if a lattice term v has a lower cover (i.e., if there is a w with w covered by v, which is denoted by w) and for finding them if it does. This paper studies the efficiency of both Whitman's algorithm and the algorithms of Freese and Nation. It is shown that although it is often quite fast, the straightforward implementation of Whitman's algorithm for testing vu is exponential in time in the worst case. A modification of Whitman's algorithm is given which is polynomial and has constant minimum time. The algorithms of Freese and Nation are then shown to be polynomial.     

The projected GSURE for automatic parameter tuning in iterative shrinkage methods

Linear inverse problems are very common in signal and image processing. Many algorithms that aim at solving such problems include unknown parameters that need tuning. In this work we focus on optimally selecting such parameters in iterative shrinkage methods for image deblurring and image zooming. Our work uses the projected Generalized Stein Unbiased Risk Estimator (GSURE) for determining the threshold value λ and the iterations number K in these algorithms. The proposed parameter selection is shown to handle any degradation operator, including ill-posed and even rectangular ones. This is achieved by using GSURE on the projected expected error. We further propose an efficient greedy parameter setting scheme, that tunes the parameter while iterating without impairing the resulting deblurring performance. Finally, we provide extensive comparisons to conventional methods for parameter selection, showing the superiority of the use of the projected GSURE.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

Job shop scheduling with unit time operations under resource constraints and release dates

We consider the problem of job shop scheduling with m machines and n jobs J_i, each consisting of l_i unit time operations. There are s distinct resources R_h and a quantity q_h available of each one. The execution of the j-th operation of J_i requires the presence of u_ijh units of R_h, 1 ≤i≤n, 1 ≤j≤l_i, and 1 ≤h≤s. In addition, each J_i has a release date r_i, that is J_i cannot start before time r_i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{l_i} and u=|{u_ijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time.     

On the Cauchy problem for the evolution p-Laplacian equations with gradient term and source

In this paper, the authors study the equation ut=div(|Du|^p−2Du)+|u|^q−1u−λl|Du| in RN with p>2. We first prove that for 1?l?p−1, the solution exists at least for a short time; then for , the existence and nonexistence of global (in time) solutions are studied in various situations.     

Optimal ordering policies with convertible lead times

A firm receives orders that will be required at an uncertain time given by an Erlang distribution, and over time observes the associated independent exponential events. The firm, in turn, places orders at a linear cost from a supplier with fixed lead time l and has the option of converting (expediting) each order, at a cost, over a certain time interval after the order is originally placed. A converted order arrives l_e < l units of time after it is converted. We show that a threshold policy is optimal. Under such a policy the firm places an order after a certain number of exponential events have been observed. An order is converted the first time, if any, when the residual lead time exceeds a time threshold related to the number of exponential events realized since the order was placed.     

Long cycles in bipartite graphs

Let G be a 2-connected bipartite graph with bipartition (A, B), where |A| ≥ |B|. It is shown that if each vertex of A has degree at least k, and each vertex of B has degree at least l, then G contains a cycle of length at least 2min(|B|, k + l ? 1, 2k ? 2). Then this result is used to determine the minimum number of edges required in a bipartite graph to ensure a cycle of length at least 2m, for any integer m ≥ 2.     

Efficient Comparison Based String Matching

We study the exact number of symbol comparisons that are required to solve the string matching problem and present a family of efficient algorithms. Unlike previous string matching algorithms, the algorithms in this family do not "forget" results of comparisons, what makes their analysis much simpler. In particular, we give a linear-time algorithm that finds all occurrences of a pattern of length m in a text of length n in [formula] comparisons. The pattern preprocessing takes linear time and makes at most 2m comparisons. This algorithm establishes that, in general, searching for a long pattern is easier than searching for a short one. We also show that any algorithm in the family of the algorithms presented must make at least [formula] symbol comparisons, for m = 2^k − 1 and any integer k ≥ 1.     

Hamiltonicity of 3-Arc Graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.     

Search-extension method for finding multiple solutions of nonlinear problem

Based on the eigensystem {λj,φj}of -Δ, the multiple solutions for nonlinear problem Δu f(u) = 0 in Ω, u = 0 on (?)Ωare approximated. A new search-extension method (SEM) is proposed, which consists of three algorithms in three level subspaces. Numerical experiments for f(u) = u3 in a square and L-shape domain are presented. The results show that there exist at least 3k - 1 distinct nonzero solutions corresponding to each κ-ple eigenvalue of -Δ(Conjecture 1).     

The critical Fujita exponent for a diffusion equation with a potential term

We study the initial-boundary-value problem of the diffusion equation u _t = Δu ^m ? V (x)u ^m + u ^p in a conelike domain D = [1,∞) × Ω, where V (x) ~ ω ₂ |x| ^?2 with ω ₂ > 0. Let ω ₁ denote the smallest Dirichlet eigenvalue for the Laplace–Beltrami operator on Ω, and let l denote the positive root of l ² + (n ? 2)l = ω ₁ + ω ₂. We prove that if m < p ≤ m + 2/(n + l), then the problem has no global nonnegative solutions for any nonnegative u ₀ unless u ₀ = 0; if p > m + 2/(n + l), then the problem has global solutions for some \( {u_0}\gneq 0 \) .     

A note on Keller-Osserman conditions on Carnot groups

This paper deals with the study of differential inequalities with gradient terms on Carnot groups. We are mainly focused on inequalities of the form Δ_φu≥f(u)l(|∇₀u|), where f, l and φ are continuous functions satisfying suitable monotonicity assumptions and Δ_φ is the φ-Laplace operator, a natural generalization of the p-Laplace operator which has recently been studied in the context of Carnot groups. We extend to general Carnot groups the results proved in Magliaro et al. (2011) [7] for the Heisenberg group, showing the validity of Liouville-type theorems under a suitable Keller-Osserman condition. In doing so, we also prove a maximum principle for inequality Δ_φu≥f(u)l(|∇₀u|). Finally, we show sharpness of our results for a general φ-Laplacian.     

Mutually independent bipanconnected property of hypercube

A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = 〈v₀, v₁, … , v_m〉 is a sequence of adjacent vertices. Two paths with equal length P₁ = 〈 u₁, u₂, … , u_m〉 and P₂ = 〈 v₁, v₂, … , v_m〉 from a to b are independent if u₁ = v₁ = a, u_m = v_m = b, and u_i ≠ v_i for 2 ? i ? m − 1. Paths with equal length from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, d_G(u, v) ? l ? ∣V(G) − 1∣ with (l − d_G(u, v)) being even. We say that the pair of vertices u, v is (m, l)-mutually independent bipanconnected if there exist m mutually independent paths with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d_Qn(u,v)?n-1, is (n − 1, l)-mutually independent bipanconnected for every with (l-d_Qn(u,v)) being even. As for d_Qn(u,v)?n-2, it is also (n − 1, l)-mutually independent bipanconnected if l?d_Qn(u,v)+2, and is only (l, l)-mutually independent bipanconnected if l=d_Qn(u,v).     

Critical Exponent for the Parabolic Equation u_t=Δu~m + h(t)u~p in a Cone

In this paper,we study the initial-boundary value problem of porous medium equation ut = Δum + h(t)up in a cone D =(0,∞) ×Ω,where h(t) ～ tσ.Let ω1 denote the smallest Dirichlet eigenvalue for the Laplace-Beltrami operator on Ω and let l denote the positive root of l 2 +(n 2)l = ω1.We prove that if m p ≤ m + 2(σ+1) n+l + σ(m 1),then the problem has no global nonnegative solutions for any nonnegative u0 unless u0 = 0;if p m + 2(σ+1) n+l + σ(m1),then the problem has global solutions for some u 0 ≥ 0.     

Integer linear programming approaches for non-unique probe selection

In addition to their prevalent use for analyzing gene expression, DNA microarrays are an efficient tool for biological, medical, and industrial applications because of their ability to assess the presence or absence of biological agents, the targets, in a sample. Given a collection of genetic sequences of targets one faces the challenge of finding short oligonucleotides, the probes, which allow detection of targets in a sample by hybridization experiments. The experiments are conducted using either unique or non-unique probes, and the problem at hand is to compute a minimal design, i.e., a minimal set of probes that allows to infer the targets in the sample from the hybridization results. If we allow to test for more than one target in the sample, the design of the probe set becomes difficult in the case of non-unique probes.Building upon previous work on group testing for microarrays we describe the first approach to select a minimal probe set for the case of non-unique probes in the presence of a small number of multiple targets in the sample. The approach is based on an integer linear programming formulation and a branch-and-cut algorithm. Our implementation significantly reduces the number of probes needed while preserving the decoding capabilities of existing approaches.