Key predistribution schemes for distributed sensor networks via block designs

Key predistribution schemes for distributed sensor networks have received significant attention in the recent literature. In this paper we propose a new construction method for these schemes based on combinations of duals of standard block designs. Our method is a broad spectrum one which works for any intersection threshold. By varying the initial designs, we can generate various schemes and this makes the method quite flexible. We also obtain explicit algebraic expressions for the metrics for local connectivity and resiliency. These schemes are quite efficient with regard to connectivity and resiliency and at the same time they allow a straightforward shared-key discovery.     

A unified solving approach for two and three dimensional coverage problems in sensor networks

The problem of designing a wired or a wireless sensor network to cover, monitor and/or control a region of interest has been widely treated in literature. This problem is referred to in literature as the sensor placement problem (SPP) and in the most general case it consists in determining the number and the location of one or more kind of sensors with the aim of covering all the region of interest or a significant part of it. In this paper we propose a unified and stepwise solving approach for two and three dimensional coverage problems to be used in omni-directional and directional sensor networks. The proposed approach is based on schematizing the region of interest and the sensor potential locations by a grid of points and representing the sensor coverage area by a circle or by a circular sector. On this basis, the SPP is reduced to an optimal coverage problem and can be formulated by integer linear programming (ILP) models. We will resume the main ILP models used in our approach, highlighting, for each of them, the specific target to be achieved and the design constraints taken into account. The paper concludes with an application of the proposed approach to a real test case and a discussion of the obtained results.     

完美门限方案的组合构造

部分平衡t-设计t-(v; b;w; 1; 0) (X;A) 称为可划分的, 如果它同时也是一个部分平衡(t-1)-设计(t -1)-(v; b;w; λ_t-1; 0) 并且可将区组集A划分为A₁;…;A_λt-1; 使得每个(X;A_i) (1≤i≤λ_t-1)是一个部分平衡(t-1)-设计(t-1)-(v; b/λ_t-1;w; 1; 0). 本文证明可划分部分平衡t-设计PPBD t-(v; b;w;λ_t-1; 1; 0) 的存在性蕴含着完美(t;w; v;λ_t-1)-门限方案的存在性; 而且在某些情况下, 最优可划分部分平衡t-设计OPPBD(t;w; v) 的存在性等价于最优(t;w; v)-门限方案的存在性. 由此我们得到了最优(t;w; v)-门限方案的一些新的无穷类.     

A combinatorial approach to cartograms

A homeomorphism from ² to itself distorts metric quantities, such as distance and area. We describe an algorithm that constructs homeomorphisms with prescribed area distortion. Such homeomorphisms can be used to generate cartograms, which are geographic maps purposely distorted so their area distributions reflects a variable different from area, as for example population density. The algorithm generates the homeomorphism through a sequence of local piecewise linear homeomorphic changes. Sample results produced by the preliminary implementation of the method are included.     

A combinatorial approach to complexity

We present a problem of construction of certain intersection graphs. If these graphs were explicitly constructed, we would have an explicit construction of Boolean functions of large complexity.     

A unified interpretation of several combinatorial dualities

Several combinatorial structures exhibit a duality relation that yields interesting theorems, and, sometimes, useful explanations or interpretations of results that do not concern duality explicitly. We present a common characterization of the duality relations associated with matroids, clutters (Sperner families), oriented matroids, and weakly oriented matroids. The same conditions characterize the orthogonality relation on certain families of vector spaces. This leads to a notion of abstract duality.     

A combinatorial approach to p-adic geometry

An important tool in p-adic geometry is the process of p-adic completion. It is shown that this process can be performed on the level of valuated matroids, that is, certain structures which appear to capture much of the essence of p-adic geometry in a coordinate-free, combinatorial manner.     

Generic constructions for partitioned difference families with applications: a unified combinatorial approach

Partitioned difference families are an interesting class of discrete structures which can be used to derive optimal constant composition codes. There have been intensive researches on the construction of partitioned difference families. In this paper, we consider the combinatorial approach. We introduce a new combinatorial configuration named partitioned relative difference family, which proves to be very powerful in the construction of partitioned difference families. In particular, we present two general recursive constructions, which not only include some existing constructions as special cases, but also generate many new series of partitioned difference families. As an application, we use these partitioned difference families to construct several new classes of optimal constant composition codes.     

A combinatorial approach to coarse geometry

Using ideas from shape theory we embed the coarse category of metric spaces into the category of direct sequences of simplicial complexes with bonding maps being simplicial. Two direct sequences of simplicial complexes are equivalent if one of them can be transformed to the other by contiguous factorizations of bonding maps and by taking infinite subsequences. This embedding can be realized by either Rips complexes or analogs of Roe?s anti-?ech approximations of spaces.In this model coarse n-connectedness of K={K₁→K₂→?} means that for each k there is m>k such that the bonding map from Kk to Km induces trivial homomorphisms of all homotopy groups up to and including n.The asymptotic dimension being at most n means that for each k there is m>k such that the bonding map from Kk to Km factors (up to contiguity) through an n-dimensional complex.Property A of G. Yu is equivalent to the condition that for each k and for each ?>0 there is m>k such that the bonding map from |Kk| to |Km| has a contiguous approximation g:|Kk|→|Km| which sends simplices of |Kk| to sets of diameter at most ?.     

A unified approach to fractional derivatives

A new fractional derivative of the Grüwald–Letnikov type is proposed and some properties are studied. The new definition incorporates both the forward and backward Grüwald–Letnikov and the two-sided fractional derivatives. Several properties of such generalized operator are presented, and some particular cases deduced.     

A unified approach to evaluation algorithms for multivariate polynomials

We present a unified framework for most of the known and a few new evaluation algorithms for multivariate polynomials expressed in a wide variety of bases including the Bernstein-Bézier, multinomial (or Taylor), Lagrange and Newton bases. This unification is achieved by considering evaluation algorithms for multivariate polynomials expressed in terms of L-bases, a class of bases that include the Bernstein-Bézier, multinomial, and a rich subclass of Lagrange and Newton bases. All of the known evaluation algorithms can be generated either by considering up recursive evaluation algorithms for L-bases or by examining change of basis algorithms for L-bases. For polynomials of degree in variables, the class of up recursive evaluation algorithms includes a parallel up recurrence algorithm with computational complexity , a nested multiplication algorithm with computational complexity and a ladder recurrence algorithm with computational complexity . These algorithms also generate a new generalization of the Aitken-Neville algorithm for evaluation of multivariate polynomials expressed in terms of Lagrange L-bases. The second class of algorithms, based on certain change of basis algorithms between L-bases, include a nested multiplication algorithm with computational complexity , a divided difference algorithm, a forward difference algorithm, and a Lagrange evaluation algorithm with computational complexities , and per point respectively for the evaluation of multivariate polynomials at several points.

     

A combinatorial approach for Keller's conjecture

The statement, that in a tiling by translates of ann-dimensional cube there are two cubes having common (n-1)-dimensional faces, is known as Keller's conjecture. We shall prove that there is a counterexample for this conjecture if and only if the following graphs _n has a 2 ⁿ size clique. The 4 ⁿ vertices of _n aren-tuples of integers 0, 1, 2, and 3. A pair of thesen-tuples are adjacent if there is a position at which the difference of the corresponding components is 2 modulo 4 and if there is a further position at which the corresponding components are different. We will give the size of the maximal cliques of _n forn5.     

A combinatorial approach to the classification problem

We study the two-group classification problem which involves classifying an observation into one of two groups based on its attributes. The classification rule is a hyperplane which misclassifies the fewest number of observations in the training sample. Exact and heuristic algorithms for solving the problem are presented. Computational results confirm the efficiency of this approach.     

A unified pre-training and adaptation framework for combinatorial optimization on graphs

Combinatorial optimization(CO) on graphs is a classic topic that has been extensively studied across many scientific and industrial fields. Recently, solving CO problems on graphs through learning methods has attracted great attention. Advanced deep learning methods, e.g., graph neural networks(GNNs), have been used to effectively assist the process of solving COs. However, current frameworks based on GNNs are mainly designed for certain CO problems, thereby failing to consider their transferabl...