We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in $2^{left(1 - Omega(rac{1}{log c}) ight)n}$ time for instances with n variables and cn nodes.

This paper presents a novel data compression method for testing integrated circuits within the selective dictionary coding framework. Due to the inverse value of dictionary indices made use of for the compatibility analysis with the heuristic algorithm utilized to solve the maximum clique problem, the method can obtain a higher compression ratio than existing ones.

Operating swarm robots has the virtues of improved performance, fault tolerance, distributed sensing, and so on. The problem is, high overall system costs are the main barrier in managing a system of foraging swarm robots. Moreover, its control algorithm should be scalable and reliable as the foraging (search) spaces become wider. This paper analyzes a nature-inspired cooperative method to reduce the operating costs of the foraging swarm robots through simulation experiments. The aim of this research is to improve efficiency of mechanisms for reducing the cost by developing a new algorithm for the synergistic cooperation of the group. In this paper, we set the evaluation index of energy efficiency considering that the mission success rate as well as energy saving is important. The value is calculated as the number of successful operations against the total consumption of energy in order to also guarantee optimized for the work processing power than the one simple goal of energy savings. The method employs a behavioral model of a honey bee swarm to improve the energy efficiency in collecting crops or minerals. Experiments demonstrate the effectiveness of the approach. The experiment is set a number of strategies to combine the techniques to the proposed and conventional methods. Considering variables such as the area of search space and the size of a swarm, the efficiency comparison test is performed. As the result, the proposed method showed the enhanced energy efficiency of the average 76.9% as compared to the conventional simple model that means reduction of the recharging cost more than 40%.

In this paper we discuss approximation algorithms for the ELEMENT-DISJOINT STEINER TREE PACKING problem (Element-STP for short). For a graph G=(V,E) and a subset of nodes T⊆V, called terminal nodes, a Steiner tree is a connected, acyclic subgraph that contains all the terminal nodes in T. The goal of Element-STP is to find as many element-disjoint Steiner trees as possible. Element-STP is known to be APX-hard even for |T|=3 [1]. It is also known that Element-STP is NP-hard to approximate within a factor of Ω(log |V|) [3] and there is an O(log |V|)-approximation algorithm for Element-STP [2],[4]. In this paper, we provide a $lceil rac{|T|}{2} ceil$-approximation algorithm for Element-STP on graphs with |T| terminal nodes. Furthermore, we show that the approximation ratio of 3 for Element-STP on graphs with five terminal nodes can be improved to 2.

We present circuit implementations for computing exponentials and logarithms suitable for rapid single-flux-quantum (RSFQ) logic. We propose hardware algorithms based on the sequential table-lookup (STL) method using the radix-2 signed-digit representation that achieve high-throughput, digit-serial calculations. The circuits are implemented by processing elements formed in systolic-array-like, regularly-aligned pipeline structures. The processing elements are composed of adders, shifters, and readouts of precomputed constants. The iterative calculations are fully overlapped, and throughputs approach the maximum throughput of serial processing. The circuit size for calculating significand parts is estimated to be approximately 5-10 times larger than that of a bit-serial floating-point adder or multiplier.

The classification of warheads and decoys is a core technology in the defense of the ballistic missile. Usually, a high range resolution is favorable for the development of the classification algorithm, which requires a high sampling rate in fast time, and thus leads to a heavy computation burden for data processing. In this paper, a novel method based on compressed sensing (CS) is presented to improve the range resolution of the target with low computational complexity. First, a tool for electromagnetic calculation, such as CST Microwave Studio, is used to simulate the frequency response of the electromagnetic scattering of the target. Second, the range-resolved signal of the target is acquired by further processing. Third, a greedy algorithm is applied to this signal. By the iterative search of the maximum value from the signal rather than the calculation of the inner product for raw echo, the scattering coefficients of the target can be reconstructed efficiently. A series of experimental results demonstrates the effectiveness of our method.

It is a well-known and useful problem to find a matching in a given graph G whose size is at most a given parameter k and whose weight is maximized (over all matchings of size at most k in G). In this paper, we consider two natural extensions of this problem. One is to find t disjoint matchings in a given graph G whose total size is at most a given parameter k and whose total weight is maximized, where t is a (small) constant integer. Previously, only the special case where t=2 was known to be fixed-parameter tractable. In this paper, we show that the problem is fixed-parameter tractable for any constant t. When t=2, the time complexity of the new algorithm is significantly better than that of the previously known algorithm. The other is to find a set of vertex-disjoint paths each of length 1 or 2 in a given graph whose total length is at most a given parameter k and whose total weight is maximized. As interesting applications, we further use the algorithms to speed up several known approximation algorithms (for related NP-hard problems) whose approximation ratio depends on a fixed parameter 0<ε<1 and whose running time is dominated by the time needed for exactly solving the problems on graphs in which each connected component has at most ε-1 vertices.

Optimizating the deployment of wireless sensor networks, which is one of the key issues in wireless sensor networks research, helps improve the coverage of the networks and the system reliability. In this paper, we propose an evolutionary algorithm based on modified t-distribution for the wireless sensor by introducing a deployment optimization operator and an intelligent allocation operator. A directed perturbation operator is applied to the algorithm to guide the evolution of the node deployment and to speed up the convergence. In addition, with a new geometric sensor detection model instead of the old probability model, the computing speed is increased by 20 times. The simulation results show that when this algorithm is utilized in the actual scene, it can get the minimum number of nodes and the optimal deployment quickly and effectively.Compared with the existing mainstream swarm intelligence algorithms, this method has satisfied the need for convergence speed and better coverage, which is closer to the theoretical coverage value.

Left-weight sequences (LW-sequences for short) are in common currency for encoding binary trees. In [16], Wu et al. proposed an algorithm associated with tree rotations for listing all binary trees in diverse representations including LW-sequences. In particular, such a list of LW-sequences is generated in Gray-code order. In this paper, based on this ordering, we present efficient ranking and unranking algorithms. For binary trees with n internal nodes, the time complexity and the space requirement in each of our ranking and unranking algorithms are O(n2) and O(n), respectively.

Designing a backbone IP network, especially to support both unicast and multicast traffic under delay constraints, is a difficult problem. Real network design must consider cost, performance and reliability. Therefore, a simulator can help a network designer to test the functionality of the network before the implementation. This paper proposes a heuristic design algorithm called D-MENTOR, and the algorithm was developed by programming based on Mesh Network Topological Optimization and Routing Version 2 (MENTOR-II) to integrate as a new module of DElite tool. The simulation results show that, in almost all test cases, the proposed algorithm yields lower installation cost.

This paper proposes a new class of Hilbert pairs of almost symmetric orthogonal wavelet bases. For two wavelet bases to form a Hilbert pair, the corresponding scaling lowpass filters are required to satisfy the half-sample delay condition. In this paper, we design simultaneously two scaling lowpass filters with the arbitrarily specified flat group delay responses at ω=0, which satisfy the half-sample delay condition. In addition to specifying the number of vanishing moments, we apply the Remez exchange algorithm to minimize the difference of frequency responses between two scaling lowpass filters, in order to improve the analyticity of complex wavelets. The equiripple behavior of the error function can be obtained through a few iterations. Therefore, the resulting complex wavelets are orthogonal and almost symmetric, and have the improved analyticity. Finally, some examples are presented to demonstrate the effectiveness of the proposed design method.

This paper presents the design of a multiple-standard 1080 high definition (HD) video decoder on a mixed-grained reconfigurable computing platform integrating coarse-grained reconfigurable processing units (RPUs) and FPGAs. The proposed RPU, including 16×16 multi-functional processing elements (PEs), is used to accelerate compute-intensive tasks in the video decoding. A soft-core-based microprocessor array is implemented on the FPGA and adopted to speed-up the dynamic reconfiguration of the RPU. Furthermore, a mail-box-based communication scheme is utilized to improve the communication efficiency between RPUs and FPGAs. By exploiting dynamic reconfiguration of the RPUs and static reconfiguration of the FPGAs, the proposed platform achieves scalable performances and cost trade-offs to support a variety of video coding standards, including MPEG-2, AVS, H.264, and HEVC. The measured results show that the proposed platform can support H.264 1080 HD video streams at up to 57 frames per second (fps) and HEVC 1080 HD video streams at up to 52fps under 250MHz, at the same time, it achieves a 3.6× performance gain over an industrial coarse-grained reconfigurable processor for H.264 decoding, and a 6.43× performance boosts over a general purpose processor based implementation for HEVC decoding.

A partitioning parallelization of the multi-objective evolutionary algorithm based on decomposition, pMOEA/D, is proposed in this letter to achieve significant time reductions for expensive bi-objective optimization problems (BOPs) on message-passing clusters. Each sub-population of pMOEA/D resides on a separate processor in a cluster and consists of a non-overlapping partition and some extra overlapping individuals for updating neighbors. Additionally, sub-populations cooperate across separate processors by the hybrid migration of elitist individuals and utopian points. Experimental results on two benchmark BOPs and the wireless sensor network layout problem indicate that pMOEA/D achieves satisfactory performance in terms of speedup and quality of solutions on message-passing clusters.

In this paper, a vehicular antenna design scheme that considers vehicular body effects is proposed. A wire antenna for the global positioning system (GPS) and long-term evolution (LTE) systems is implemented on a plastic plate and then mounted on a windshield of the vehicle. Common outputs are used to allow feed sharing. It is necessary to increase the GPS right-hand circularly polarization (RHCP) gain near the zenith and to reduce the axis ratio (AR). For LTE, we need to increase the horizontal polarization (HP) gain. In addition, for LTE, multiband characteristics are required. In order to achieve the specified performance, the antenna shape is optimized via a Pareto genetic algorithm (PGA). When an antenna is mounted on the body, antenna performance changes significantly. To evaluate the performance of an antenna with complex shape mounted on a windshield, a commercial electromagnetic simulator (Ansoft HFSS) is used. To apply electromagnetic results output by HFSS to the PGA algorithm operating in the MATLAB environment, a MATLAB-to-HFSS linking program via Visual BASIC (VB) script was used. It is difficult to carry out the electromagnetic analysis on the entire body because of the limitations of the calculating load and memory size. To overcome these limitations, we consider only that part of the vehicle's body that influences antenna performance. We show that a series of optimization steps can minimize the degradation caused by the vehicle`s body. The simulation results clearly show that it is well optimized at 1.575GHz for GPS, and 0.74 ∼ 0.79GHz and 2.11 ∼ 2.16GHz for LTE, respectively.

Suppose that we are given two vertex covers C0 and Ct of a graph G, together with an integer threshold k ≥ max{|C0|, |Ct|}. Then, the vertex cover reconfiguration problem is to determine whether there exists a sequence of vertex covers of G which transforms C0 into Ct such that each vertex cover in the sequence is of cardinality at most k and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on k for which any pair of vertex covers in a graph G has a desired sequence. Our upper bound is best possible in some sense.

A projective Reed-Muller (PRM) code, obtained by modifying a Reed-Muller code with respect to a projective space, is a doubly extended Reed-Solomon code when the dimension of the related projective space is equal to 1. The minimum distance and the dual code of a PRM code are known, and some decoding examples have been presented for low-dimensional projective spaces. In this study, we construct a decoding algorithm for all PRM codes by dividing a projective space into a union of affine spaces. In addition, we determine the computational complexity and the number of correctable errors of our algorithm. Finally, we compare the codeword error rate of our algorithm with that of the minimum distance decoding.

This paper presents novel reconfigurable semi-systolic array architecture for the Smith-Waterman with an affine gap penalty algorithm to align protein sequences optimized for shorter database sequences. This architecture has been modified to enable hardware reuse rather than replicating processing elements of the semi-systolic array in multiple FPGAs. The proposed hardware architecture and the previously published conventional one are described at the Register Transfer Level (RTL) using VHDL language and implemented using the FPGA technology. The results show that the proposed design has significant higher normalized speedup (up to 125%) over the conventional one for query sequence lengths less than 512 residues. According to the UniProtKB/TrEMBL protein database (release 2015_05) statistics, the largest number of sequences (about 80%) have sequence length less than 512 residues that makes the proposed design outperforms the conventional one in terms of speed and area in this sequence lengths range.

To improve the performance of capsule endoscope, it is important to add location information to the image data obtained by the capsule endoscope. There is a disadvantage that a lot of existing localization techniques require to measure channel model parameters in advance. To avoid such a troublesome pre-measurement, this paper pays attention to capsule endoscope localization based on an electromagnetic imaging technology which can estimate not only the location but also the internal structure of a human body. However, the electromagnetic imaging with high resolution has huge computational complexity, which should prevent us from carrying out real-time localization. To ensure the accurate real-time localization system without pre-measured model parameters, we apply genetic algorithm (GA) into the electromagnetic imaging-based localization method. Furthermore, we evaluate the proposed GA-based method in terms of the simulation time and the location estimation accuracy compared to the conventional methods. In addition, we show that the proposed GA-based method can perform more accurately than the other conventional methods, and also, much less computational complexity of the proposed method can be accomplished than a greedy algorithm-based method.

We consider a problem of the choice of price plans offered by a telecommunications company: a “pay-as-you-go” plan and a “flat-rate” plan. This problem is formulated as an online optimization problem extending the ski-rental problem, and analyzed using the competitive ratio. We give a lemma for easily calculating the competitive ratio. Based on the lemma, we derive a family of optimal strategies for a realistic class of instances.

In this paper, we consider the problem of generating uniformly random mosaic floorplans. We propose a polynomial-time algorithm that generates such floorplans with f faces. Two modified algorithms are created to meet additional criteria.