Triangular Dissections, Aperiodic Tilings, and Jones Algebras

The Brattelli diagram associated with a given bicolored Dynkin-Coxeter graph of type A_n determines planar fractal sets obtained by infinite dissections of a given triangle. All triangles appearing in the dissection process have angles that are multiples of π/(n + 1). There are usually several possible infinite dissections compatible with a given n but a given one makes use of n/2 triangle types if n is even. Jones algebra with index [4 cos²(π/(n + 1))]⁻¹ (values of the discrete range) act naturally on vector spaces associated with those fractal sets. Triangles of a given type are always congruent at each step of the dissection process. In the particular case n = 4, there are isometric and the whole structure lead, after proper inflation, to aperiodic Penrose tilings. The "tilings" associated with other values of the index are discussed and shown to be encoded by equivalence classes of infinite sequences (with appropriate constraints), using n/2 digits (if- n is even) and generalizing the Fibonacci numbers.     

Text Indexing and Dictionary Matching with One Error

The indexing problem is where a text is preprocessed and subsequent queries of the form “Find all occurrences of pattern P in the text” are answered in time proportional to the length of the query and the number of occurrences. In the dictionary matching problem a set of patterns is preprocessed and subsequent queries of the form “Find all occurrences of dictionary patterns in text T” are answered in time proportional to the length of the text and the number of occurrences.There exist efficient worst-case solutions for the indexing problem and the dictionary matching problem, but none that find approximate occurrences of the patterns, i.e., where the pattern is within a bound edit (or Hamming) distance from the appropriate text location.In this paper we present a uniform deterministic solution to both the indexing and the general dictionary matching problem with one error. We preprocess the data in time O(n log² n), where n is the text size in the indexing problem and the dictionary size in the dictionary matching problem. Our query time for the indexing problem is O(m log n log log n + tocc), where m is the query string size and tocc is the number of occurrences. Our query time for the dictionary matching problem is O(n log³ d log log d + tocc), where n is the text size and d the dictionary size. The time bounds above apply to both bounded and unbounded alphabets.     

Likelihood Maximization and Moment Matching in Low SNR Gaussian Mixture Models

We derive an asymptotic expansion for the log-likelihood of Gaussian mixture models (GMMs) with equal covariance matrices in the low signal-to-noise regime. The expansion reveals an intimate connection between two types of algorithms for parameter estimation: the method of moments and likelihood optimizing algorithms such as Expectation-Maximization (EM). We show that likelihood optimization in the low SNR regime reduces to a sequence of least squares optimization problems that match the moments of the estimate to the ground truth moments one by one. This connection is a stepping stone towards the analysis of EM and maximum likelihood estimation in a wide range of models. A motivating application for the study of low SNR mixture models is cryo-electron microscopy data, which can be modeled as a GMM with algebraic constraints imposed on the mixture centers. We discuss the application of our expansion to algebraically constrained GMMs, among other example models of interest. © 2022 The Authors. Communications on Pure and Applied Mathematics published by Wiley Periodicals LLC.     

Families of Finite Subsets of ℕ of Low Complexity and Tsirelson Type Spaces

We study Tsirelson type spaces of the form T[(ℳ︁_k, θ_k)^l_k=1] defined by a finite sequence (ℳ︁_k)^l_k=1 of compact families of finite subsets of ℕ. Using an appropriate index, denoted by i(ℳ︁), to measure the complexity of a family ℳ︁, we prove the following: If i(ℳ︁_k) < ω for all k = 1, …, l, then the space T[(ℳ︁_k, θ_k)^l_k=1] contains isomorphically some l_p, 1 < p < ∞, or c₀. If i(ℳ︁) = ω, then the space T[ℳ︁, θ] contains a subspace isomorphic to a subspace of the original Tsirelson's space.     

Geometric Structures, Lobe Dynamics, and Lagrangian Transport in Flows with Aperiodic Time-Dependence, with Applications to Rossby Wave Flow

Summary. In this paper we develop the mathematical framework for studying transport in two-dimensional flows with aperiodic time dependence from the geometrical point of view of dynamical systems theory. We show how the notion of a hyperbolic fixed point, or periodic trajectory, and its stable and unstable manifolds generalize to the aperiodically time-dependent setting. We show how these stable and unstable manifolds act as mediators of transport, and we extend the technique of lobe dynamics to this context. We discuss Melnikov's method for two classes of systems having aperiodic time dependence. We develop a numerical method for computing the stable and unstable manifolds of hyperbolic trajectories in two-dimensional flows with aperiodic time dependence. The theory and the numerical techniques are applied to study the transport in a kinematic model of Rossby wave flow studied earlier by Pierrehumbert [1991a]. He considered flows with periodic time dependence, and we continue his study by considering flows having quasi-periodic, wave-packet, and purely aperiodic time dependencies. These numerical simulations exhibit a variety of new transport phenomena mediated by the stable and unstable manifolds of hyperbolic trajectories that are unique to the case of aperiodic time dependence. Received April 10, 1997; revision received August 1, 1997 and accepted October 7, 1997     

Combinatorial optimization with interaction costs: Complexity and solvable cases

We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures.     

订单生产方式下供应链1:1买卖双方协调订货模型

供需关系贯穿供应链的整个过程。因此，供需双方订货批量研究是供应链管理的一个最重要也最基本的内容之一。本以订单方式为背景，讨论了供应链环境下1：1非合作订货模型，并在此基础上给出了1：1供需双方通过适当的线性价格折扣政策的Stackelberg博弈模型。最后给出了两个算例加以说明。     

订单生产方式下供应链1∶1买卖双方协调订货模型

供需关系贯穿供应链的整个过程。因此,供需双方订货批量研究是供应链管理的一个最重要也最基本的内容之一。本文以订单方式为背景,讨论了供应链环境下1∶1非合作订货模型,并在此基础上给出了1∶1供需双方通过适当的线性价格折扣政策的Stackelberg博弈模型。最后给出了两个算例加以说明。     

System-Wide Probabilities for Systems with Runs and Scans Rules

Systems that include multiple decision rules are encountered in many fields. We focus on systems with several states or levels where the rules determining when and how to move between the levels are based on runs or scans. Our target is to evaluate the proportion of time spent at each level. This information is valuable since it is required for constructing various cost functions. In this paper we address two questions: How to incorporate the system of levels and decision rules into a probabilistic setting and which measures to use in order to evaluate the proportion of time spent at each level. We take a waiting-time approach, and use special features of runs and scans distributions in order to investigate long and short-term measures of the time spent at the different levels of a system. We introduce a short term per-cycle measure and compare it with the finite-time measure. We find that the two measures can differ significantly.     

Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays

We consider shop problems with transportation delays where not only the jobs on the machines have to be scheduled, but also transportation of the jobs between the machines has to be taken into account. Jobs consisting of a given number of operations have to be processed on machines in such a way that each machine processes at most one operation at a time and a job is not processed by more than one machine simultaneously. Transportation delays occur if a job changes from one machine to another. The objective is to find a feasible schedule which minimizes some objective function. A survey of known complexity results for flow-shop and open-shop environments is given and some new complexity results are derived.     

一种带链规则的变样本容量X图

将一种链规则和变化样本容量的思想一起并入休哈特均值图以加快其发现过程均值小漂移的速度.利用马氏链方法计算了控制图稳态表现下的平均链长.与几种图的比较显示,该图能显著加速发现过程均值小的漂移.     

Computing over the Reals with Addition and Order: Higher Complexity Classes

This paper deals with issues of structural complexity in a linear version of the Blum-Shub-Smale model of computation over the real numbers. Real versions of PSPACE and of the polynomial time hierarchy are defined, and their properties are investigated. Mainly two types of results are presented:

• •Equivalence between quantification over the real numbers and over {0, 1};
• •Characterizations of recognizable subsets of {0, 1}* in terms of familiar discrete complexity classes.

The complexity of the decision and quantifier elimination problems in the theory of the reals with addition and order is also studied.     

Complexity of Lambek Calculi with Modalities and of Total Derivability in Grammars

Algebra and Logic - The Lambek calculus with the unit can be defined as the atomic theory (algebraic logic) of the class of residuated monoids. This calculus, being a theory of a broader class of...     

Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity

In many practical situations, batching of similar jobs to avoid set-ups is performed whilst constructing a schedule. On the other hand, each job may consist of many identical items. Splitting a job often results in improved customer service or in reduced throughput time. Thus, implicit in determining a schedule is a lot-sizing decision which specifies how a job is to be split. This paper proposes a general model which combines batching and lot-sizing decisions with scheduling. A review of research on this type of model is given. Some important open problems for which further research is required are also highlighted.     

考虑不同商业目标和公平关切的动态博弈模型及复杂性研究

建立双寡头零售商具有不同商业目标和公平关切的动态价格博弈模型,着重分析了基于零售商考虑不同商业目标和公平关切下的价格博弈模型的复杂性。数值模拟了不同参数数值组合条件下的价格动态博弈过程,通过系统稳定域,分岔,李雅普诺夫指数,混沌吸引子等对模型进行了复杂性分析,发现零售商考虑公平关切会使自身稳定域减小;公平关切的水平越高,系统越容易进入混沌状态。同时研究了价格调整速度对零售商利润的影响,结果发现当价格调整速度过大时,系统会进入混沌状态,利润值波动剧烈且平均利润随着价格调整速度的增大而减小。最后选择控制因子对系统混沌进行了控制,该研究对零售商价格决策有着很好的借鉴意义。