Cost-effective allocations of bounded and binary resources in polynomial time

The problem considered is that of the allocation of linear and discrete resources to concave activities with binary effectiveness values of 0 or 1. The objective is to maximize the ratio of the total return to an affine cost. Previously described algorithms are extended to include an upper bound on the quantity of any resource allocated to given disjoint sets of activities, and on the quantity allocated to any activity from given disjoint sets of resources. It is demonstrated that the algorithm solves the problem in polynomial time.     

Operators in pre-Riesz spaces: moduli and homomorphisms

We focus on two topics that are related to moduli of elements in partially ordered vector spaces. First, we relate operators that preserve moduli to generalized notions of lattice homomorphisms, such as Riesz homomorphisms, Riesz* homomorphisms, and positive disjointness preserving operators. We also consider complete Riesz homomorphisms, which generalize order continuous lattice homomorphisms. Second, we characterize elements with a modulus by means of disjoint elements and apply this result to obtain moduli of functionals and operators in various settings. On spaces of continuous functions, we identify those differences of Riesz* homomorphisms that have a modulus. Many of our results for pre-Riesz spaces of continuous functions lead to results on order unit spaces, where the functional representation is used.

     

A Note on Binary Plane Partitions

Abstract. This paper considers binary space partition s (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ω (n log n /log log n) in the worst case.     

Binary signed-graphic matroids: Representations and recognition algorithms

Recognition algorithms determining whether a given matroid is binary signed-graphic or not are presented in this work. Depending on whether the input is a cographic, a binary or a general matroid different algorithms are provided utilizing mainly decomposition results for the class of signed-graphic matroids. Finally, in order to devise such algorithms, necessary results regarding the representability of signed-graphic matroids in various fields are also given.     

A Note on Binary Plane Partitions

   Abstract. This paper considers binary space partition s (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ω (n log n /log log n) in the worst case.     

双水平集逼近油藏模型特征的数值模拟方法

本文使用双水平集函数逼近油藏模型特征, 构造出Uzawas 算法进行数值模拟. 对于两相流渗透率的数值求解问题, 可以通过测量油井数据和地震波数据来实现. 将构造出来的带限制的最优化问题使用变异的Lagrange 方法求解. 如果使用双水平集函数逼近渗透率函数, 则需要对Lagrange 函数进行修正, 从而将带限制的最优化问题转化成无限制的最优化问题. 由于双水平集函数的优越性, 进一步构造出最速梯度下降Uzawas 算法和算子分裂格式Uzawas 算法进行求解对应的最优化子问题. 数值算例表明设计的算法是高效的、稳定的.     

Perfect binary codes of infinite length

A subset C of infinite-dimensional binary cube is called a perfect binary code with distance 3 if all balls of radius 1 (in the Hamming metric) with centers in C are pairwise disjoint and their union cover this binary cube. Similarly, we can define a perfect binary code in zero layer, consisting of all vectors of infinite-dimensional binary cube having finite supports. In this article we prove that the cardinality of all cosets of perfect binary codes in zero layer is the cardinality of the continuum. Moreover, the cardinality of all cosets of perfect binary codes in the whole binary cube is equal to the cardinality of the hypercontinuum.     

Disjoint hypercyclic powers of weighted translations on groups

Let G be a locally compact group and let 1 ≤ p < 1. Recently, Chen et al. characterized hypercyclic, supercyclic and chaotic weighted translations on locally compact groups and their homogeneous spaces. There has been an increasing interest in studying the disjoint hypercyclicity acting on various spaces of holomorphic functions. In this note, we will study disjoint hypercyclic and disjoint supercyclic powers of weighted translation operators on the Lebesgue space L ^p(G) in terms of the weights. Sufficient and necessary conditions for disjoint hypercyclic and disjoint supercyclic powers of weighted translations generated by aperiodic elements on groups will be given.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

Order closed ideals in pre-Riesz spaces and their relationship to bands

In Archimedean vector lattices bands can be introduced via three different coinciding notions. First, they are order closed ideals. Second, they are precisely those ideals which equal their double disjoint complements. The third concept is that of an ideal which contains the supremum of any of its bounded subsets, provided the supremum exists in the vector lattice. We investigate these three notions and their relationships in the more general setting of Archimedean pre-Riesz spaces. We introduce the notion of a supremum closed ideal, which is related to the third aforementioned notion in vector lattices. We show that for a directed ideal I in a pervasive pre-Riesz space with the Riesz decomposition property these three concepts coincide, provided the double disjoint complement of I is directed. In pervasive pre-Riesz spaces every directed band is supremum closed and every supremum closed directed ideal I equals its double disjoint complement, provided the double disjoint complement of I is directed. In general, in Archimedean pre-Riesz spaces the three notions differ. For this we provide appropriate counterexamples.     

A Brylawski decomposition for finite ordered sets

A decomposition is given for finite ordered sets P and is shown to be a unique decomposition in the sense of Brylawski. Hence there exists a universal invariant g(P) for this decomposition, and we compute g(P) explicitly. Some modifications of this decomposition are considered; in particular, one which forms a bidecomposition together with disjoint union.     

Reliability analysis of non‐repairable systems modeled by dynamic fault trees with priority AND gates

Many real‐life systems are typically involved in sequence‐dependent failure behaviors. Such systems can be modeled by dynamic fault trees (DFTs) with priority AND gates, in which the occurrence of the top events depends on not only combinations of basic events but also their failure sequences. To the author's knowledge, the existing methods for reliability assessment of DFTs with priority AND gates are mainly Markov‐state‐space‐based, inclusion–exclusion‐based, Monte Carlo simulation‐based, or sequential binary decision diagram‐based approaches. Unfortunately, all these methods have their shortcomings. They either suffer the problem of state space explosion or are restricted to exponential components time‐to‐failure distributions or need a long computation time to obtain a solution with a high accuracy. In this article, a novel method based on dynamic binary decision tree (DBDT) is first proposed. To build the DBDT model of a given DFT, we present an adapted format of the traditional Shannon's decomposition theorem. Considering that the chosen variable index has a great effect on the final scale of disjoint calculable cut sequences generated from a built DBDT, which to some extent determines the computational efficiency of the proposed method, some heuristic branching rules are presented. To validate our proposed method, a case study is analyzed. The results indicate that the proposed method is reasonable and efficient. Copyright © 2015 John Wiley & Sons, Ltd.     

The universality for linear combinations of Lerch zeta functions and the Tornheim�CHurwitz type of double zeta functions

In this paper, we consider the universality for linear combinations of Lerch zeta functions. J. Kaczorowski, A. Laurin?ikas and J. Steuding treated universal Dirichlet series with the case that the compact sets ${\mathcal{K}_l}$ are disjoint. But we consider the both cases that the compact subset ${\mathcal{K}_l}$ is disjoint and not disjoint. Next, we will show the non-trivial zeros of the Tornheim?CHurwitz type of double zeta functions in the region of absolute convergence. Moreover we show the universality for the Tornheim?CHurwitz type of double zeta function.     

Binary Plane Partitions for Disjoint Line Segments

A binary space partition (BSP) for a set of disjoint objects in Euclidean space is a recursive decomposition where each step partitions the space (and possibly some of the objects) along a hyperplane and recurses on the objects clipped in each of the two open half-spaces. The size of a BSP is defined as the number of resulting fragments of the input objects. It is shown that every set of n disjoint line segments in the plane admits a BSP of size O(nlog n/log log n). This bound is the best possible.     

Highly Nonlinear Resilient Functions Through Disjoint Codes in Projective Spaces

Functions which map n-bits to m-bits are important cryptographic sub-primitives in the design of additive stream ciphers. We construct highly nonlinear t-resilient such functions ((n, m, t) functions) by using a class of binary disjoint codes, a construction which was introduced in IEEE Trans. Inform. Theory, Vol. IT-49 (2) (2003). Our main contribution concerns the generation of suitable sets of such disjoint codes. We propose a deterministic method for finding disjoint codes of length ν m by considering the points of PG ). We then obtain some lower bounds on the number of disjoint codes, by fixing some parameters. Through these sets, we deduce in certain cases the existence of resilient functions with very high nonlinearity values. We show how, thanks to our method, the degree and the differential properties of (n, m, t) functions can be improved.Communicated by: J.D. Key     

Strict Embeddings of Rearrangement Invariant Spaces

A Banach space E of measurable functions on [0,1] is called rearrangement invariant if E is a Banach lattice and equimeasurable functions have identical norms. The canonical inclusion E ? F of two rearrangement invariant spaces is said to be strict if functions from the unit ball of E have absolutely equicontinuous norms in F. Necessary and sufficient conditions for the strictness of canonical inclusion for Orlicz, Lorentz, and Marcinkiewicz spaces are obtained, and the relations of this concept to the disjoint strict singularity are studied.     

Complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections

The problem of reconstructing a special class of binary images from their horizontal and vertical projections is considered. We present a general framework for analyzing the worst case complexity of this task if the image consists of more than one pairwise disjoint component. Applying the presented technique we analyze the complexity of reconstructing canonical hv-convex binary images. We also present parameterized complexity results on general and so-called glued hv-convex images. Moreover, we study how our results are related to the reconstruction of permutation matrices from four projections.     

Convex subsets of 2n and bounded truth-table reducibility

Let 2ⁿ be the set of n-tuples of 0's and 1's, partially ordered componentwise. A characterization is given of the possible decompositions of arbitrary subsets of 2ⁿ as disjoint unions of sets which are convex in this ordering; this result is used to obtain a decomposition theorem for Boolean functions in terms of monotone functions. The second half of the paper contains applications to recursion theory; in particular, canonical forms for certain minimum-norm bounded-truth-table reductions are obtained.     

A Central Limit Theorem for linear random fields

A Central Limit Theorem is proved for linear random fields when sums are taken over union of finitely many disjoint rectangles. The approach does not rely upon the use of Beveridge-Nelson decomposition and the conditions needed are similar in nature to those given by Ibragimov for linear processes. When specializing this result to the case when sums are being taken over rectangles, a complete analogue of the Ibragimov result is obtained for random fields with a lot of uniformity.