Omnibus Sequences, Coupon Collection, and Missing Word Counts

In this paper, we study the properties of k-omnisequences of length n, defined to be strings of length n that contain all strings of smaller length k embedded as (not necessarily contiguous) subsequences. We start by proving an elementary result that relates our problem to the classical coupon collector problem. After a short survey of relevant results in coupon collection, we focus our attention on the number M of strings (or words) of length k that are not found as subsequences of an n string, showing that there is a gap between the probability threshold for the emergence of an omnisequence and the zero-infinity threshold for ${\mathbb E}(M)$ .     

A Survey of the Coupon Collector’s Problem with Random Sample Sizes

This paper surveys the coupon collector’s waiting time problem with random sample sizes and equally likely balls. Consider an urn containing m red balls. For each draw, a random number of balls are removed from the urn. The group of removed balls is painted white and returned to the urn. Several approaches to addressing this problem are discussed, including a Markov chain approach to compute the distribution and expected value of the number of draws required for the urn to contain j white balls given that it currently contains i white balls. As a special case, E[N], the expected number of draws until all the balls are white given that all are currently red is also obtained.      

On Computing the Subset Graph of a Collection of Sets

Let a given collection of sets have size N measured by the sum of the cardinalities. Yellin and Jutla presented an algorithm which constructed the partial order induced by the subset relation (a “subset graph”) in a claimed O(N²/log N) operations over a dictionary ADT, and exhibited a collection whose subset graph had Θ(N²/log² N) edges. This paper first establishes a matching upper bound on the number of edges in a subset graph. It also presents a finer analysis of the algorithm, which confirms the claimed upper bound and shows it to be tight. A simple implementation requiring O(1) bit-parallel operations per ADT operation is presented, along with a variant of the algorithm with an implementation requiring O(N²/log N) RAM operations.     

Approximability of the Problem of Finding a Vector Subset with the Longest Sum

We answer the question of existence of polynomial-time constant-factor approximation algorithms for the space of nonfixed dimension. We prove that, in Euclidean space the problem is solvable in polynomial time with accuracy \(\sqrt a \), where α = 2/π, and if P ≠ NP then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the ?_p spaces, the problem is APX-complete if p ∈ [1, 2] and not approximable with constant accuracy if P ≠ NP and p ∈ (2,∞).     

带有优惠券销售的商品利润模型及其求解

根据"满100元返x元"的优惠券的特点,建立了商场商品在保持原来定价的基础上、以商家利润最大化为目的的数学模型;同时,利用遗传算法对此模型优化求解,仿真结果说明该模型及其解法具有一定的实用价值.     

Ordinal Optimization with Subset Selection Rule

Ordinal optimization (OO) has enjoyed a great degree of success in addressing stochastic optimization problems characterized by an independent and identically distributed (i.i.d.) noise. The methodology offers a statistically quantifiable avenue to find good enough solutions by means of soft computation. In this paper, we extend the OO methodology to a more general class of stochastic problems by relaxing the i.i.d. assumption on the underlying noise. Theoretical results and their applications to simple examples are presented.     

城市垃圾收运系统中的车辆收运计划问题

将垃圾收运系统中收运小车一天的收运计划问题,分为停车场设在转运站或别处两种情况,以小车行走总距离最小为目标,分别构建了混合整数规划模型.接着提出问题的求解思路:当停车场设在转运站时,可以将问题转化为VRP问题求解;若停车场设在别处,在求解上一问题的基础上设计了最近回路节点插入法将停车场插入离其最近的回路节点即可.最后以实例验证了模型和求解思路的可行性和有效性.     

广义Sierpinski集

本文考察了包括平面上的各种广义 Cantor集 ,Sierpinski集和包括某些连续不可微曲线在内的广义 Sierpinski集 .由相似变换 ,导出了它们的级数表达式 ,并利用它和字符串空间的对应关系 ,计算出它们的Hausdorff维数     

Commutativity of Rings with Constraints Involving a Subset

Suppose that R is an associative ring with identity 1, J(R) the Jacobson radical of R, and N(R) the set of nilpotent elements of R. Let m 1 be a fixed positive integer and R an m-torsion-free ring with identity 1. The main result of the present paper asserts that R is commutative if R satisfies both the conditions(i) [x ^m, y ^m] = 0 for all and(ii) [(xy) ^m + y ^m x ^m, x] = 0 = [(yx) ^m + x ^m y ^m, x], for all This result is also valid if (i) and (ii) are replaced by (i) [x ^m, y ^m] = 0 for all and (ii) [(xy) ^m + y ^m x ^m, x] = 0 = [(yx) ^m + x ^m y ^m, x] for all Other similar commutativity theorems are also discussed.     

奇异协方差阵下证券组合的有效子集

Szeg\"{o}曾猜想当协方差阵奇异时可能存在有效子集, 本文在奇异协方差阵下利用有效组合的通解, 给出了证券组合有效子集的一个等价定义, 并得到了在证券全集中存在有效子集的充要条件,还给出了证券子集为有效子集的一些新的充要条件.     

不确定环境下具有减排配额的PM2.5治理博弈与税收决策

由于雾霾治理遵循浓度控制原则,且跨界传输因子存在异质性,因此,要使各地区在追求减排成本最小化时又达到减排指标,中央政府仅实施税收政策并不能满足其收支平衡条件。基于此,本文将税收与减排配额相结合,以期实现中央政府收支平衡与优化各地区治理成本的双重目标。同时,本文以京津冀地区雾霾治理为实证分析对象,验证了具有减排配额的税收决策具有可实施性。     

The Two-Period Travelling Salesman Problem Applied to Milk Collection in Ireland

We describe a new extension to the Symmetric Travelling Salesman Problem (STSP) in which some nodes are visited inboth of 2 periods and the remaining nodes are visited in either 1 ofthe periods. A number of possible Integer Programming Formulationsare given. Valid cutting plane inequalities are defined for thisproblem which result in an, otherwise prohibitively difficult, modelof 42 nodes becoming easily solvable by a combination of cuts andBranch-and-Bound. Some of the cuts are entered in a pool andonly used when it is automatically verified that they are violated.Other constraints which are generalisations of the subtour and combinequalities for the single period STSP, are identified manuallywhen needed. Full computational details of solution process aregiven.     

The Subset Sum game

In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in the knapsack. The solution is built as follows: Each agent, in turn, selects one of its items (not previously selected) and includes it in the knapsack if there is enough capacity. The process ends when the remaining capacity is too small for including any item left.     

Penalized Fast Subset Scanning

We present the penalized fast subset scan (PFSS), a new and general framework for scalable and accurate pattern detection. PFSS enables exact and efficient identification of the most anomalous subsets of the data, as measured by a likelihood ratio scan statistic. However, PFSS also allows incorporation of prior information about each data element’s probability of inclusion, which was not previously possible within the subset scan framework. PFSS builds on two main results: first, we prove that a large class of likelihood ratio statistics satisfy a property that allows additional, element-specific penalty terms to be included while maintaining efficient computation. Second, we prove that the penalized statistic can be maximized exactly by evaluating only O(N) subsets. As a concrete example of the PFSS framework, we incorporate “soft” constraints on spatial proximity into the spatial event detection task, enabling more accurate detection of irregularly shaped spatial clusters of varying sparsity. To do so, we develop a distance-based penalty function that rewards spatial compactness and penalizes spatially dispersed clusters. This approach was evaluated on the task of detecting simulated anthrax bio-attacks, using real-world Emergency Department data from a major U.S. city. PFSS demonstrated increased detection power and spatial accuracy as compared to competing methods while maintaining efficient computation.     

基于电子优惠券投放和服务创新的线上线下渠道竞争分析

基于豪泰林模型分析具有渠道偏好的线上网络渠道和线下实体渠道市场竞争格局及其博弈关系,构建线上网络渠道投放电子优惠券、线下实体渠道服务创新的渠道竞争模型,剖析优惠券和服务创新对市场份额、定价及利润的影响,并给出具有市场进入时序的渠道退出边界。研究发现:市场缺额情形凭借高价获得较小市场份额下的较高利润,而市场重叠情形的低价策略在较大市场份额下获得较小利润。当服务创新足以支撑实体渠道要价时,其可获得较高利润,守住混合偏好市场;投放电子优惠券的让价方式可增大网络渠道的调价空间,且存在最优电子优惠券面值使网络渠道获得期望收益,夺得混合偏好市场。     

Subset simulation for multi-objective optimization

Subset simulation is an efficient Monte Carlo technique originally developed for structural reliability problems, and further modified to solve single-objective optimization problems based on the idea that an extreme event (optimization problem) can be considered as a rare event (reliability problem). In this paper subset simulation is extended to solve multi-objective optimization problems by taking advantages of Markov Chain Monte Carlo and a simple evolutionary strategy. In the optimization process, a non-dominated sorting algorithm is introduced to judge the priority of each sample and handle the constraints. To improve the diversification of samples, a reordering strategy is proposed. A Pareto set can be generated after limited iterations by combining the two sorting algorithms together. Eight numerical multi-objective optimization benchmark problems are solved to demonstrate the efficiency and robustness of the proposed algorithm. A parametric study on the sample size in a simulation level and the proportion of seed samples is performed to investigate the performance of the proposed algorithm. Comparisons are made with three existing algorithms. Finally, the proposed algorithm is applied to the conceptual design optimization of a civil jet.     

Subset currents on free groups

We introduce and study the space ${{\mathcal{S}{\rm Curr} (F_N)}}$ of subset currents on the free group F _N , and, more generally, on a word-hyperbolic group. A subset current on F _N is a positive F _N -invariant locally finite Borel measure on the space ${{\mathfrak{C}_N}}$ of all closed subsets of ?F _N consisting of at least two points. The well-studied space Curr(F _N ) of geodesics currents–positive F _N -invariant locally finite Borel measures defined on pairs of different boundary points–is contained in the space of subset currents as a closed ${{\mathbb{R}}}$ -linear Out(F _N )-invariant subspace. Much of the theory of Curr(F _N ) naturally extends to the ${{\mathcal{S}\;{\rm Curr} (F_N)}}$ context, but new dynamical, geometric and algebraic features also arise there. While geodesic currents generalize conjugacy classes of nontrivial group elements, a subset current is a measure-theoretic generalization of the conjugacy class of a nontrivial finitely generated subgroup in F _N . If a free basis A is fixed in F _N , subset currents may be viewed as F _N -invariant measures on a “branching” analog of the geodesic flow space for F _N , whose elements are infinite subtrees (rather than just geodesic lines) of the Cayley graph of F _N with respect to A. Similarly to the case of geodesics currents, there is a continuous Out(F _N )-invariant “co-volume form” between the Outer space cv _N and the space ${{\mathcal{S}\;{\rm Curr} (F_N)}}$ of subset currents. Given a tree ${{T \in {\rm cv}_N}}$ and the “counting current” ${{\eta_H \in \mathcal{S}\;{\rm Curr} (F_N)}}$ corresponding to a finitely generated nontrivial subgroup H ≤  F _N , the value ${{\langle T, \eta_H \rangle}}$ of this intersection form turns out to be equal to the co-volume of H, that is the volume of the metric graph T _H /H, where ${{T_H \subseteq T}}$ is the unique minimal H-invariant subtree of T. However, unlike in the case of geodesic currents, the co-volume form ${{{\rm cv}_N \times \mathcal{S}\;{\rm Curr}(F_N)\; \to [0,\infty)}}$ does not extend to a continuous map ${{\overline{{\rm cv}}_N \times \mathcal{S}\; {\rm Curr} (F_N) \to [0,\infty)}}$ .