<Emphasis Type="Italic">α</Emphasis>-Systems of differential inclusions and their unification

This paper introduces α-systems of differential inclusions on a bounded time interval [t₀, ?] and defines α-weakly invariant sets in [t₀, ?] × ?_n, where ?_n is a phase space of the differential inclusions. We study the problems connected with bringing the motions (trajectories) of the differential inclusions from an α-system to a given compact set M ? ?_n at the moment ? (the approach problems). The issues of extracting the solvability set W ? [t₀, ?] × ?ⁿ in the problem of bringing the motions of an α-system to M and the issues of calculating the maximal α-weakly invariant set W^c ? [t₀, ?] × ?ⁿ are also discussed. The notion of the quasi-Hamiltonian of an α-system (α-Hamiltonian) is proposed, which seems important for the problems of bringing the motions of the α-system to M.     

Polar Codes with Higher-Order Memory

We introduce a construction of a set of code sequences {C_n^(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C_n^(m)} is a generalization of polar codes presented by Ar?kan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n ? 1) and N(n ? m), and {C_n^(m)} coincides with the original polar codes when m = 1. We show that {C_n^(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P_e of {C_n^(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(? ? 1)], where ? ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ^m ? ρ^{m ? 1} ? 1. The encoding and decoding complexities of {C_n^(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Ar?kan’s construction.     

Central limit theorem and large deviations of the fading Wyner cellular model via product of random matrices theory

We apply the theory of products of random matrices to the analysis of multi-user communication channels similar to the Wyner model, which are characterized by short-range intra-cell broadcasting. We study fluctuations of the per-cell sum-rate capacity in the non-ergodic regime and provide results of the type of the central limit theorem (CLT) and large deviations (LD). Our results show that CLT fluctuations of the per-cell sum-rate C _m are of order \(1/\sqrt m \), where m is the number of cells, whereas they are of order 1/m in classical random matrix theory. We also show an LD regime of the form P(|C _m ? C| > ?) ≤ e ^?mα with α = α(?) > 0 and C = \(\mathop {\lim }\limits_{m \to \infty } \) C _m , as opposed to the rate \(e^{ - m^2 \alpha } \) in classical random matrix theory.     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

Approximate Comparison of Functions Computed by Distance Automata

Distance automata are automata weighted over the semiring \((\mathbb {N}\cup \{\infty \},\min , +)\) (the tropical semiring). Such automata compute functions from words to \(\mathbb {N}\cup \{\infty \}\). It is known from Krob that the problems of deciding ‘ f≤g’ or ‘ f=g’ for f and g computed by distance automata is an undecidable problem. The main contribution of this paper is to show that an approximation of this problem is decidable. We present an algorithm which, given ε>0 and two functions f,g computed by distance automata, answers “yes” if f≤(1?ε)g, “no” if f≦?g, and may answer “yes” or “no” in all other cases. The core argument behind this quasi-decision procedure is an algorithm which is able to provide an approximated finite presentation of the closure under products of sets of matrices over the tropical semiring. Lastly, our theorem of affine domination gives better bounds on the precision of known decision procedures for cost automata, when restricted to distance automata.     

An orthogonal analysis method for decoupling the nozzle geometrical parameters of microthrusters

This paper proposes an orthogonal analysis method for decoupling the multiple nozzle geometrical parameters of microthrusters, thus an reconfigured design can be implemented to generate a proper thrust. In this method, the effects of various nozzle geometrical parameters, including throat width W _t , half convergence angle θ _in , half divergence angle θ _out , exit-to-throat section ratio W _e /W _t and throat radius of the curvature R _t /W _t , on the performance of microthrusters are sorted by range analysis. Analysis results show that throat width seriously affects thrust because range value of 67.53 mN is extremely larger than the range value of other geometry parameters. For average specific impulse (ASI), the range value of exit-to-throat section ratio W _e /W _t and half divergence angle θ _out are 4.82 s and 3.72 s, respectively. Half convergence angle with the range value of 0.39 s and throat radius with 0.32 s have less influence on ASI compared with exit-to-throat section ratio and half divergence angle. When increasing the half convergence angle from 10° to 40° and throat radius of the curvature from 3 to 9, average specific impulse initially decreases and then increases. A MEMS solid propellant thruster (MSPT) with the reconfigured geometrical parameters of nozzle is fabricated to verify the feasibility of the proposed method. The thrust of the microthruster can reach 25 mN. Power is estimated to be 0.84 W. This work provides design guideline to reasonably configure geometry parameters of microthruster.     

On the <Emphasis Type="Italic">k</Emphasis>-accessibility of cores of <Emphasis Type="Italic">TU</Emphasis>-cooperative games

This paper proposes a strengthening of the author’s core-accessibility theorem for balanced TU-cooperative games. The obtained strengthening relaxes the influence of the nontransitivity of classical domination αv on the quality of the sequential improvement of dominated imputations in a game v. More specifically, we establish the k-accessibility of the core C(α _v ) of any balanced TU-cooperative game v for all natural numbers k: for each dominated imputation x, there exists a converging sequence of imputations x₀, x₁,..., such that x₀ = x, lim x _r ∈ C(α _v ) and x_r?m is dominated by any successive imputation x _r with m ∈ [1, k] and r ≥ m. For showing that the TU-property is essential to provide the k-accessibility of the core, we give an example of an NTU-cooperative game G with a ”black hole” representing a nonempty closed subset B ? G(N) of dominated imputations that contains all the α _G -monotonic sequential improvement trajectories originating at any point x ∈ B.     

A semi-supervised approach to sentiment analysis using revised sentiment strength based on SentiWordNet

Emergence of MapReduce (MR) framework for scaling data mining and machine learning algorithms provides for Volume, while handling of Variety and Velocity needs to be skilfully crafted in algorithms. So far, scalable clustering algorithms have focused solely on Volume, taking advantage of the MR framework. In this paper we present a MapReduce algorithm—data aware scalable clustering (DASC), which is capable of handling the 3 Vs of big data by virtue of being (i) single scan and distributed to handle Volume, (ii) incremental to cope with Velocity and (iii) versatile in handling numeric and categorical data to accommodate Variety. DASC algorithm incrementally processes infinitely growing data set stored on distributed file system and delivers quality clustering scheme while ensuring recency of patterns. The up-to-date synopsis is preserved by the algorithm for the data seen so far. Each new data increment is processed and merged with the synopsis. Since the synopsis itself may grow very large in size, the algorithm stores it as a file. This makes DASC algorithm truly scalable. Exclusive clusters are obtained on demand by applying connected component analysis (CCA) algorithm over the synopsis. CCA presents subtle roadblock to effective parallelism during clustering. This problem is overcome by accomplishing the task in two stages. In the first stage, hyperclusters are identified based on prevailing data characteristics. The second stage utilizes this knowledge to determine the degree of parallelism, thereby making DASC data aware. Hyperclusters are distributed over the available compute nodes for discovering embedded clusters in parallel. Staged approach for clustering yields dual advantage of improved parallelism and desired complexity in \(\mathcal {MRC}^0\) class. DASC algorithm is empirically compared with incremental Kmeans and Scalable Kmeans++ algorithms. Experimentation on real-world and synthetic data with approximately 1.2 billion data points demonstrates effectiveness of DASC algorithm. Empirical observations of DASC execution are in consonance with the theoretical analysis with respect to stability in resources utilization and execution time.     

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAX W-LIGHT, MIN W-LIGHT, MAX W-HEAVY, and MIN W-HEAVY take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).     

Indefinite summation of rational functions with additional minimization of the summable part

An algorithm of indefinite summation of rational functions is proposed. For a given function f(x), it constructs a pair of rational functions g(x) and r(x) such that f(x) = g(x + 1) ? g(x) + r(x), where the degree of the denominator of r(x) is minimal, and, when this condition is satisfied, the degree of the denominator of g(x) is also minimal.     

On s-uniform property of compressing sequences derived from primitive sequences modulo odd prime powers

Let Z/(p^e) be the integer residue ring modulo p^e with p an odd prime and e ≥ 2. We consider the suniform property of compressing sequences derived from primitive sequences over Z/(p^e). We give necessary and sufficient conditions for two compressing sequences to be s-uniform with α provided that the compressing map is of the form ?(x₀, x₁,...,x_e?1) = g(x_e?1) + η(x₀, x₁,..., x_e?2), where g(x_e?1) is a permutation polynomial over Z/(p) and η is an (e ? 1)-variable polynomial over Z/(p).     

Two-armed bandit problem for parallel data processing systems

We consider application of the two-armed bandit problem to processing a large number N of data where two alternative processing methods can be used. We propose a strategy which at the first stages, whose number is at most r ? 1, compares the methods, and at the final stage applies only the best one obtained from the comparison. We find asymptotically optimal parameters of the strategy and observe that the minimax risk is of the order of N ^α , where α = 2 ^r?1/(2 ^r ? 1). Under parallel processing, the total operation time is determined by the number r of stages but not by the number N of data.     

Preparing large-scale maximally entangled <Emphasis Type="Italic">W</Emphasis> states in optical system

We propose an optical scheme to prepare large-scale maximally entangled W states by fusing arbitrary-size polarization entangled W states via polarization-dependent beam splitter. Because most of the currently existing fusion schemes are suffering from the qubit loss problem, that is the number of the output entangled qubits is smaller than the sum of numbers of the input entangled qubits, which will inevitably decrease the fusion efficiency and increase the number of fusion steps as well as the requirement of quantum memories, in our scheme, we design a effect fusion mechanism to generate \(W_{m+n}\) state from a n-qubit W state and a m-qubit W state without any qubit loss. As the nature of this fusion mechanism clearly increases the final size of the obtained W state, it is more efficient and feasible. In addition, our scheme can also generate \(W_{m+n+t-1}\) state by fusing a \(W_m\), a \(W_n\) and a \(W_t\) states. This is a great progress compared with the current scheme which has to lose at least two particles in the fusion of three W states. Moreover, it also can be generalized to the case of fusing k different W states, and all the fusion schemes proposed here can start from Bell state as well.     

Filtration of aerosol particles by cylindrical fibers within a parallel and staggered array

The World Health Organization (WHO) in 2013 reported that more than seven million unexpected losses every year are credited to air contamination. Because of incredible adaptability and expense viability of fibrous filters, they are broadly used for removing particulates from gasses. The influence of appropriate parameters, e.g., the fiber arrangement, solid volume fraction (SVF or α), fluid flow face velocity (mean inlet velocity), and filter thickness (I _x ), on pressure drop and deposition efficiency are researched. Furthermore, to study the effects of variation of the laminar flow regime and fiber’s cross-sectional shape on the deposition of particles, only a single square fiber has been placed in a channel. By means of finite volume method (FVM), the 2-D motion of 100–1000 nm particles was investigated numerically. The Lagrangian method has been employed and the Saffman’s lift, Drag, and Brownian forces have been considered to affect this motion. Contribution of increasing the Reynolds number to filtration performance increased with smaller fine aerosols to a level of 59.72 %. However, for over 500 nm, the Re = 100 has more efficient results up to 26.97 %. Remarkably, the single square fiber in Re = 200 regime performs similarly to the optimum choice of multi-fibrous filters. It was portrayed the parallel circular multi-fibrous filter with a ratio of horizontal-to-vertical distances between fibers, l/h = 1.143; α = 0.687, I _x  = 116.572, and h/d _f  = 1.0 is the most efficient filter’s structure. The increase in the ratio of vertical distances between fibers-to-fiber’s diameter (h/d _f ) and decrease in SVF or α, results in a drastically decrement of the filtration performance of both parallel and staggered structures. The obtained results have been validated with previous research findings.     

Scheduling fully parallel jobs

We consider the following scheduling problem. We have m identical machines, where each machine can accomplish one unit of work at each time unit. We have a set of n fully parallel jobs, where each job j has \(s_j\) units of workload, and each unit workload can be executed on any machine at any time unit. A job is considered complete when its entire workload has been executed. The objective is to find a schedule that minimizes the total weighted completion time \(\sum w_j C_j\), where \(w_j\) is the weight of job j and \(C_j\) is the completion time of job j. We provide theoretical results for this problem. First, we give a PTAS of this problem with fixed m. We then consider the special case where \(w_j = s_j\) for each job j, and we show that it is polynomial solvable with fixed m. Finally, we study the approximation ratio of a greedy algorithm, the Largest-Ratio-First algorithm. For the special case, we show that the approximation ratio depends on the instance size, i.e. n and m, while for the general case where jobs have arbitrary weights, we prove that the upper bound of the approximation ratio is \(1 + \frac{m-1}{m+2}\).     

Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions

This paper considers the problem of computing general commutative and associative aggregate functions (such as Sum) over distributed inputs held by nodes in a distributed system, while tolerating failures. Specifically, there are N nodes in the system, and the topology among them is modeled as a general undirected graph. Whenever a node sends a message, the message is received by all of its neighbors in the graph. Each node has an input, and the goal is for a special root node (e.g., the base station in wireless sensor networks or the gateway node in wireless ad hoc networks) to learn a certain commutative and associate aggregate of all these inputs. All nodes in the system except the root node may experience crash failures, with the total number of edges incidental to failed nodes being upper bounded by f. The timing model is synchronous where protocols proceed in rounds. Within such a context, we focus on the following question:

Under any given constraint on time complexity, what is the lowest communication complexity, in terms of the number of bits sent (i.e., locally broadcast) by each node, needed for computing general commutative and associate aggregate functions?

This work, for the first time, reduces the gap between the upper bound and the lower bound for the above question from polynomial to polylog. To achieve this reduction, we present significant improvements over both the existing upper bounds and the existing lower bounds on the problem.

     

On weak isometries of Preparata codes

Two codes C ₁ and C ₂ are said to be weakly isometric if there exists a mapping J: C ₁ → C ₂ such that for all x, y in C ₁ the equality d(x, y) = d holds if and only if d(J(x), J(y)) = d, where d is the code distance of C ₁. We prove that Preparata codes of length n ≥ 2¹² are weakly isometric if and only if the codes are equivalent. A similar result is proved for punctured Preparata codes of length at least 2¹⁰ ? 1.     

Error bounds for complementarity problems with tridiagonal nonlinear functions

In this paper we consider the complementarity problem NCP(f) with f(x) = Mx + φ(x), where M ∈ R ^n×n is a real matrix and φ is a so-called tridiagonal (nonlinear) mapping. This problem occurs, for example, if certain classes of free boundary problems are discretized. We compute error bounds for approximations \({\hat x}\) to a solution x* of the discretized problems. The error bounds are improved by an iterative method and can be made arbitrarily small. The ideas are illustrated by numerical experiments.     

LP rounding and combinatorial algorithms for minimizing active and busy time

We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline, and required processing length. The jobs need to be scheduled on a machine so that at most g jobs are active at any given time. The duration for which a machine is active (i.e., “on”) is referred to as its active time. The goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3-approximation (and this bound is tight) and we further improve this to a 2-approximation via LP rounding techniques. Our second contribution is for the non-preemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NP-hard, we allow for an unbounded number of virtual machines, each having capacity of g. This problem is known as the busy time problem in the literature and a 4-approximation is known for this problem. We develop a new combinatorial algorithm that gives a 3-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an algorithm that is 2-approximate.     

B$$_\pi ^R$$-matrices and error bounds for linear complementarity problems

B-matrices form a subclass of P-matrices for which error bounds for the linear complementarity problem are known. It is proved that a bound involved in such problems is asymptotically optimal. \(B_\pi ^R\)-matrices form a subclass of P-matrices containing B-matrices. For the \(B_\pi ^R\)-matrices, error bounds for the linear complementarity problem are obtained. We also include illustrative examples showing the sharpness of these bounds.