Countable linear orders with disjoint infinite intervals are mutually orthogonal

Two linear orderings of a same set are perpendicular if the only self-mappings of this set that preserve them both are the identity and the constant mappings. Two linear orderings are orthogonal if they are isomorphic to two perpendicular linear orderings. We show that two countable linear orderings are orthogonal as soon as each one has two disjoint infinite intervals. From this and previously known results it follows in particular that each countably infinite linear ordering is orthogonal to itself.     

Clustering of imbalanced high-dimensional media data

Media content in large repositories usually exhibits multiple groups of strongly varying sizes. Media of potential interest often form notably smaller groups. Such media groups differ so much from the remaining data that it may be worthy to look at them in more detail. In contrast, media with popular content appear in larger groups. Identifying groups of varying sizes is addressed by clustering of imbalanced data. Clustering highly imbalanced media groups is additionally challenged by the high dimensionality of the underlying features. In this paper, we present the imbalanced clustering (IClust) algorithm designed to reveal group structures in high-dimensional media data. IClust employs an existing clustering method in order to find an initial set of a large number of potentially highly pure clusters which are then successively merged. The main advantage of IClust is that the number of clusters does not have to be pre-specified and that no specific assumptions about the cluster or data characteristics need to be made. Experiments on real-world media data demonstrate that in comparison to existing methods, IClust is able to better identify media groups, especially groups of small sizes.     

Lower Bounds on the Generalized Central Moments of the Optimal Alignments Score of Random Sequences

We present a general approach to the problem of determining tight asymptotic lower bounds for generalized central moments of the optimal alignment score of two independent sequences of i.i.d. random variables. At first, these are obtained under a main assumption for which sufficient conditions are provided. When the main assumption fails, we nevertheless develop a “uniform approximation” method leading to asymptotic lower bounds. Our general results are then applied to the length of the longest common subsequences of binary strings, in which case asymptotic lower bounds are obtained for the moments and the exponential moments of the optimal score. As a by-product, a local upper bound on the rate function associated with the length of the longest common subsequences of two binary strings is also obtained.     

Finding small somatic structural variants in exome sequencing data: a machine learning approach

Genetic variation forms the basis for diversity but can as well be harmful and cause diseases, such as tumors. Structural variants (SV) are an example of complex genetic variations that comprise of many nucleotides ranging up to several megabases. Based on recent developments in sequencing technology it has become feasable to elucidate the genetic state of a person’s genes (i.e. the exome) or even the complete genome. Here, a machine learning approach is presented to find small disease-related SVs with the help of sequencing data. The method uses differences in characteristics of mapping patterns between tumor and normal samples at a genomic locus. This way, the method aims to be directly applicable for exome sequencing data to improve detection of SVs since specific SV detection methods are currently lacking. The method has been evaluated based on a simulation study as well as with exome data of patients with acute myeloid leukemia. An implementation of the algorithm is available at https://github.com/lenz99-/svmod.     

Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.     

Numerical computation of viscous profiles for hyperbolic conservation laws

Viscous profiles of shock waves in systems of conservation laws can be viewed as heteroclinic orbits in associated systems of ordinary differential equations (ODE). In the case of overcompressive shock waves, these orbits occur in multi-parameter families. We propose a numerical method to compute families of heteroclinic orbits in general systems of ODE. The key point is a special parameterization of the heteroclinic manifold which can be understood as a generalized phase condition; in the case of shock profiles, this phase condition has a natural interpretation regarding their stability. We prove that our method converges and present numerical results for several systems of conservation laws. These examples include traveling waves for the Navier-Stokes equations for compressible viscous, heat-conductive fluids and for the magnetohydrodynamics equations for viscous, heat-conductive, electrically resistive fluids that correspond to shock wave solutions of the associated ideal models, i.e., the Euler, resp. Lundquist, equations.

     

Invariant smoothness measures for surfaces

Two novel smoothness measures for surfaces are presented in this paper. The second and third order smoothness are defined as the squared normal curvature and the squared variation in normal curvature integrated over all directions in the tangent plane. Both quantities are truly geometric in the sense that they are invariant with respect to the actual parametrization of the surface. All the same, all formulae are derived in terms of an arbitrary parametrization. In addition to providing a basis for variational surface construction, the second and third order smoothness can also be used for evaluation and assessment of the quality of an existing surface. This revised version was published online in August 2006 with corrections to the Cover Date.     

Retracing the residual curve of a Lyapunov equation solver

Let A∈ℝ ^n×n and let B∈ℝ ^n×p and consider the Lyapunov matrix equation AX+XA ^T +BB ^T =0. If A+A ^T <0, then the extended Krylov subspace method (EKSM) can be used to compute a sequence of low rank approximations of X. In this paper we show how to construct a symmetric negative definite matrix A and a column vector B, for which the EKSM generates a predetermined residual curve.     

Combinatorial integral approximation

We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel approach that is based on a decomposition of the MINLP into a NLP and a MILP. We discuss the relation of the MILP solution to the MINLP solution and formulate bounds for the gap between the two, depending on Lipschitz constants and the control discretization grid size. The MILP solution can also be used for an efficient initialization of the MINLP solution process. The speedup of the solution of the MILP compared to the MINLP solution is considerable already for general purpose MILP solvers. We analyze the structure of the MILP that takes switching constraints into account and propose a tailored Branch and Bound strategy that outperforms cplex on a numerical case study and hence further improves efficiency of our novel method.