A new zero-forcing block diagonalization (ZF-BD) scheme that enables both a more simplified ZF-BD and further increase in sum rate of MU-MIMO channels is proposed in this paper. The proposed scheme provides the improvement in BER performance for equivalent SU-MIMO channels. The proposed scheme consists of two components. First, a permuted channel matrix (PCM), which is given by moving the submatrix related to a target user to the bottom of a downlink MIMO channel matrix, is newly defined to obtain a precoding matrix for ZF-BD. Executing QR decomposition alone for a given PCM provides null space for the target user. Second, a partial MSQRD (PMSQRD) algorithm, which adopts MSQRD only for a target user to provide improvement in bit rate and BER performance for the user, is proposed. Some numerical simulations are performed, and the results show improvement in sum rate performance of the total system. In addition, appropriate bit allocation improves the bit error rate (BER) performance in each equivalent SU-MIMO channel. A successive interference cancellation is applied to achieve further improvement in BER performance of user terminals.

A branching program is a well-studied model of computation and a representation for Boolean functions. It is a directed acyclic graph with a unique root node, some accepting nodes, and some rejecting nodes. Except for the accepting and rejecting nodes, each node has a label with a variable and each outgoing edge of the node has a label with a 0/1 assignment of the variable. The satisfiability problem for branching programs is, given a branching program with n variables and m nodes, to determine if there exists some assignment that activates a consistent path from the root to an accepting node. The width of a branching program is the maximum number of nodes at any level. The satisfiability problem for width-2 branching programs is known to be NP-complete. In this paper, we present a satisfiability algorithm for width-2 branching programs with n variables and cn nodes, and show that its running time is poly(n)·2(1-µ(c))n, where µ(c)=1/2O(c log c). Our algorithm consists of two phases. First, we transform a given width-2 branching program to a set of some structured formulas that consist of AND and Exclusive-OR gates. Then, we check the satisfiability of these formulas by a greedy restriction method depending on the frequency of the occurrence of variables.

In this paper, we aim to develop technologies for the circuit fault diagnosis and propose a formulation of a measure of a test pattern for the circuit fault diagnosis. Given a faulty circuit, the fault diagnosis is to deduce locations of faults that had occurred in the circuit. The fault diagnosis is executed in software before the failure analysis by which engineers inspect physical defects, and helps to improve the manufacturing process which yielded faulty circuits. The heart of the fault diagnosis is to distinguish between candidate faults by using test patterns, which are applied to the circuit-under-diagnosis (CUD), and thus test patterns that can distinguish as many faults as possible need to be generated. This fact motivates us to consider the test pattern measure based on the number of fault-pairs that become distinguished by a test pattern. To the best of the authors' knowledge, that measure requires the computational time of complexity order O(NF2), where NF denotes the number of candidate faults. Since NF is generally large for real industrial circuits, the computational time of the measure is long even when a high-performance computer is used. The formulation proposed in this paper makes it possible to calculate the measure in the computational complexity of O(NF log NF), and thus that measure is useful for the test pattern selection in the fault diagnosis. In computational experiments, the effectiveness of the formulation is demonstrated as samples of computational times of the measure calculated by the traditional and the proposed formulae and thorough comparisons between several greedy heuristics which are based on the measure.

Air quality index (AQI) is a non-dimensional index for the description of air quality, and is widely used in air quality management schemes. A novel method for Air Quality Index Forecasting based on Deep Dictionary Learning (AQIF-DDL) and machine vision is proposed in this paper. A sky image is used as the input of the method, and the output is the forecasted AQI value. The deep dictionary learning is employed to automatically extract the sky image features and achieve the AQI forecasting. The idea of learning deeper dictionary levels stemmed from the deep learning is also included to increase the forecasting accuracy and stability. The proposed AQIF-DDL is compared with other deep learning based methods, such as deep belief network, stacked autoencoder and convolutional neural network. The experimental results indicate that the proposed method leads to good performance on AQI forecasting.

Softwarized networks are expected to be utilized as a core network for the 5th Generation (5G) mobile services. For the mobile core network architecture, service chaining is expected to be utilized for dynamically steering traffic across multiple network functions. In this paper, for dynamic multipath service chaining, we propose a greedy-based VNF placement algorithm. This method can provide multipath service chaining so as to utilize the node resources such as CPU effectively while decreasing the cost about bandwidth and transmission delay. The proposed algorithm consists of four difference algorithms, and VNFs are placed appropriately with those algorithm. Our proposed algorithm obtains near optimal solution for the formulated optimization problem with a greedy algorithm, and hence multipath service chains can be provided dynamically. We evaluate the performance of our proposed method with simulation and compare its performance with the performances of other methods. In numerical examples, it is shown that our proposed algorithm can provide multipath service chains appropriately so as to utilize the limited amount of node resources effectively. Moreover, it is shown that our proposed algorithm is effective for providing service chaining dynamically in large-scale network.

Depth-based action recognition has been attracting the attention of researchers because of the advantages of depth cameras over standard RGB cameras. One of these advantages is that depth data can provide richer information from multiple projections. In particular, multiple projections can be used to extract discriminative motion patterns that would not be discernible from one fixed projection. However, high computational costs have meant that recent studies have exploited only a small number of projections, such as front, side, and top. Thus, a large number of projections, which may be useful for discriminating actions, are discarded. In this paper, we propose an efficient method to exploit pools of multiple projections for recognizing actions in depth videos. First, we project 3D data onto multiple 2D-planes from different viewpoints sampled on a geodesic dome to obtain a large number of projections. Then, we train and test action classifiers independently for each projection. To reduce the computational cost, we propose a greedy method to select a small yet robust combination of projections. The idea is that best complementary projections will be considered first when searching for optimal combination. We conducted extensive experiments to verify the effectiveness of our method on three challenging benchmarks: MSR Action 3D, MSR Gesture 3D, and 3D Action Pairs. The experimental results show that our method outperforms other state-of-the-art methods while using a small number of projections.

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.

The growth of the size of the routing tables limits the scalability of the conventional IP routing. As scalable routing schemes for large-scale networks are highly demanded, this paper proposes and evaluates an efficient geometric routing scheme and related low-cost node design applicable to large-scale networks. The approach guarantees that greedy forwarding on derived coordinates will result in successful packet delivery to every destination in the network by relying on coordinates deduced from a spanning tree of the network. The efficiency of the proposed scheme is measured in terms of routing quality (stretch) and size of the coordinates. The cost of the proposed router is quantified in terms of area complexity of the hardware design and all the evaluations involve comparison with a state-of-the-art approach with virtual coordinates in the hyperbolic plane. Extensive simulations assess the proposal in large topologies consisting of up to 100K nodes. Experiments show that the scheme has stretch properties comparable to geometric routing in the hyperbolic plane, while enabling a more efficient hardware design, and scaling considerably better in terms of storage requirements for coordinate representation. These attractive properties make the scheme promising for routing in large networks.

Information Centric Networking (ICN) is a promising architecture as an alternative paradigm to traditional IP networking. The innovative concepts, such as named data, name-based routing, and in-network caching bring lots of benefits to Wireless Sensor Networks (WSNs). Simple and robust communication model of ICN, based on interest/data messages exchange, is appealing to be deployed in WSNs. However, ICN architectures are designed for power supplied network devices rather than resource-constrained sensor nodes. Introducing ICN-liked architecture to WSNs needs to rethink the naming scheme and forwarding strategy to meet the requirements of energy efficiency and failure recovery. This paper presents a light weight data centric routing mechanism (GRMR) for interest dissemination and data delivery in location-aware WSNs. A simple naming scheme gives assistance for routing decision by individual nodes. Greedy routing engaging with regional multicast mechanism provides an efficient data centric routing approach. The performance is analytically evaluated and simulated in NS-2. The results indicate that GRMR achieves significant energy efficiency under investigated scenarios.

We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $rac{15}{16}n^2+O(n)$ swaps for k=3.

Sparse Matrix-Vector Multiplication (SpMxV) is widely used in many high-performance computing applications, including information retrieval, medical imaging, and economic modeling. To eliminate the overhead of zero padding in SpMxV, prior works have focused on partitioning a sparse matrix into row vectors sets (RVS's) or sub-matrices. However, performance was still degraded due to the sparsity pattern of a sparse matrix. In this letter, we propose a heuristics, called recursive merging, which uses a greedy approach to recursively merge those row vectors of nonzeros in a matrix into the RVS's, such that each set included is ensured a local optimal solution. For ten uneven benchmark matrices from the University of Florida Sparse Matrix Collection, our proposed partitioning algorithm is always identified as the method with the highest mean density (over 96%), but with the lowest average relative difference (below 0.07%) over computing powers.

This paper proposes a novel greedy algorithm, called Creditability-Estimation based Matching Pursuit (CEMP), for the compressed sensing signal recovery. As proved in the algorithm of Stagewise Orthogonal Matching Pursuit (StOMP), two Gaussian distributions are followed by the matched filter coefficients corresponding to and without corresponding to the actual support set of the original sparse signal, respectively. Therefore, the selection for each support point is interpreted as a process of hypothesis testing, and the preliminarily selected support set is supposed to consist of rejected atoms. A hard threshold, which is controlled by an input parameter, is used to implement the rejection. Because the Type I error may happen during the hypothesis testing, not all the rejected atoms are creditable to be the true support points. The creditability of each preliminarily selected support point is evaluated by a well-designed built-in mechanism, and the several most creditable ones are adaptively selected into the final support set without being controlled by any extra external parameters. Moreover, the proposed CEMP does not necessitate the sparsity level to be a priori control parameter in operation. In order to verify the performance of the proposed algorithm, Gaussian and Pulse Amplitude Modulation sparse signals are measured in the noiseless and noisy cases, and the experiments of the compressed sensing signal recoveries by several greedy algorithms including CEMP are implemented. The simulation results show the proposed CEMP can achieve the best performances of the recovery accuracy and robustness as a whole. Besides, the experiment of the compressed sensing image recovery shows that CEMP can recover the image with the highest Peak Signal to Noise Ratio (PSNR) and the best visual quality.

A threshold secret sharing scheme protects content by dividing it into many pieces and distributing them among different servers. This scheme can also be utilized for the reliable delivery of important content. Thanks to this scheme, the receiver can still reconstruct the original content even if several pieces are lost during delivery due to a multiple-link failure. Nevertheless, the receiver cannot reconstruct the original content unless it receives pieces more than or equal to the threshold. This paper aims to obtain reliable delivery routes for the pieces, as this will minimize the probability that the receiver cannot reconstruct the original content. Although such a route optimization problem can be formulated using an integer linear programming (ILP) model, computation of globally optimum delivery routes based on the ILP model requires large amounts of computational resources. Thus, this paper proposes a lightweight method for computing suboptimum delivery routes. The proposed greedy method computes each of the delivery routes successively by using the conventional shortest route algorithm repeatedly. The link distances are adjusted iteratively on the basis of the given probability of failure on each link and they are utilized for the calculation of each shortest route. The results of a performance evaluation show that the proposed method can compute sub-optimum delivery routes efficiently thanks to the precise adjustment of the link distances, even in backbone networks on a real-world scale.

The potential of infrastructureless vehicular ad hoc networks (VANETs) for providing multihop applications is quite significant. Although the Epidemic Routing protocol performs well in highly mobile and frequently disconnected VANETs with low vehicle densities or light packet traffic loads, its performance degrades greatly in environments of high vehicle density together with heavy packet traffic loads that create serious bandwidth contention and frequent collisions. We propose a new epidemic routing protocol in urban environments called Greedy Zone Epidemic Routing (GZER), in which the neighbors of a vehicle are divided into different zones according to their physical locations. Each vehicle maintains a summary vector (SV) of packets buffered locally and zone summary vectors (ZSVs) of all packets buffered in each zone. Whether the infection will be transmitted in each zone is decided by the difference between SV and ZSV. Simulation results show that the proposed GZER protocol outperforms the existing solutions significantly, especially in the environments of high vehicle densities together with heavy packet traffic loads.

We give a unified view to greedy geometric routing algorithms in ad hoc networks. For this, we first present a general form of greedy routing algorithm using a class of objective functions which are invariant under congruent transformations of a point set. We show that several known greedy routing algorithms such as Greedy Routing, Compass Routing, and Midpoint Routing can be regarded as special cases of the generalized greedy routing algorithm. In addition, inspired by the unified view of greedy routing, we propose three new greedy routing algorithms. We then derive a sufficient condition for our generalized greedy routing algorithm to guarantee packet delivery on every Delaunay graph. This condition makes it easier to check whether a given routing algorithm guarantees packet delivery, and it is closed under convex linear combination of objective functions. It is shown that Greedy Routing, Midpoint Routing, and the three new greedy routing algorithms proposed in this paper satisfy the sufficient condition, i.e., they guarantee packet delivery on Delaunay graphs. We also discuss merits and demerits of these methods.

Estimation of distribution algorithms (EDAs), since they were introduced, have been successfully used to solve discrete optimization problems and hence proven to be an effective methodology for discrete optimization. To enhance the applicability of EDAs, researchers started to integrate EDAs with discretization methods such that the EDAs designed for discrete variables can be made capable of solving continuous optimization problems. In order to further our understandings of the collaboration between EDAs and discretization methods, in this paper, we propose a quality measure of discretization methods for EDAs. We then utilize the proposed quality measure to analyze three discretization methods: fixed-width histogram (FWH), fixed-height histogram (FHH), and greedy random split (GRS). Analytical measurements are obtained for FHH and FWH, and sampling measurements are conducted for FHH, FWH, and GRS. Furthermore, we integrate Bayesian optimization algorithm (BOA), a representative EDA, with the three discretization methods to conduct experiments and to observe the performance difference. A good agreement is reached between the discretization quality measurements and the numerical optimization results. The empirical results show that the proposed quality measure can be considered as an indicator of the suitability for a discretization method to work with EDAs.

A key challenge in developing energy-efficient sensor networks is to extend network lifetime in resource-limited environments. As sensors are often densely distributed, they can be scheduled on alternative duty cycles to conserve energy while satisfying the system requirements. Directional sensor networks composed of a large number of directional sensors equipped with a limited battery and with a limited angle of sensing have recently attracted attention. Many types of directional sensors can rotate to face a given direction. Maximizing network lifetime while covering all of the targets in a given area and forwarding sensor data to the sink is a challenge in developing such rotatable directional sensor networks. In this paper, we address the maximum directional cover tree (MDCT) problem of organizing directional sensors into a group of non-disjoint subsets to extend network lifetime. One subset, in which the directional sensors cover all of the targets and forward the data to the sink, is activated at a time, while the others sleep to conserve energy. For the MDCT problem, we first present an energy-consumption model that mainly takes into account the energy expenditure for sensor rotation as well as for the sensing and relaying of data. We also develop a heuristic scheduling algorithm called directional coverage and connectivity (DCC)-greedy to solve the MDCT problem. To verify and evaluate the algorithm, we conduct extensive simulations and show that it extends network lifetime to a reasonable degree.

A finite buffer shared by multiple packet queues is considered. Partitioning the buffer to maximize total throughput is formulated as a resource allocation problem, the solution is shown to be achieved by a greedy incremental algorithm in polynomial time. The optimal buffer allocation strategy is applied to different models for a wireless downlink. First, a set of parallel M/M/1/mi queues, corresponding to a downlink with orthogonal channels is considered. It is verified that at high load, optimal buffer partitioning can boost the throughput significantly with respect to complete sharing of the buffer. Next, the problem of optimal combined buffer allocation and channel assignment problems are shown to be separable in an outage scenario. Motivated by this observation, buffer allocation is considered in a system where users need to be multiplexed and scheduled based on channel state. It is observed that under finite buffers in the high load regime, scheduling simply with respect to channel state with a simply partitioned buffer achieves comparable throughput to combined channel and queue-aware scheduling.

Target Q coverage is needed to secure the stability of data collection in WSN. The targets may have different level of importance then the multiple-target coverage scheme must schedule sensors according to each target's weight to increase the network lifetime. The schedule scheme previously proposed for weighted coverage uses an iterative solution to solve the problem but it has long computation time. We propose a heuristic greedy-TQC algorithm to use the residual energy of sensors to generate multiple scheduling cover sets. A simulation shows a dramatic reduction in computation time. The greedy-TQC algorithm is suitable for the frequently topology-changing WSN and for the often changing targets' weights in WSN.

In this paper, a novel algorithm, Cross Low-dimension Pursuit, based on a new structured sparse matrix, Permuted Block Diagonal (PBD) matrix, is proposed in order to recover sparse signals from incomplete linear measurements. The main idea of the proposed method is using the PBD matrix to convert a high-dimension sparse recovery problem into two (or more) groups of highly low-dimension problems and crossly recover the entries of the original signal from them in an iterative way. By sampling a sufficiently sparse signal with a PBD matrix, the proposed algorithm can recover it efficiently. It has the following advantages over conventional algorithms: (1) low complexity, i.e., the algorithm has linear complexity, which is much lower than that of existing algorithms including greedy algorithms such as Orthogonal Matching Pursuit and (2) high recovery ability, i.e., the proposed algorithm can recover much less sparse signals than even 1-norm minimization algorithms. Moreover, we demonstrate both theoretically and empirically that the proposed algorithm can reliably recover a sparse signal from highly incomplete measurements.