Search

Many production datacenters nowadays service multiple applications with dynamically allocated network bandwidth, and some applications are time-critical so their data transfers or flows are constrained by deadlines. To meet deadlines, several flow scheduling schemes for datacenter networks are proposed, but most of them are unaware of bandwidth variations, leading to suboptimal throughputs. In this paper, we present a flow scheduling scheme, called UBAS, to improve deadline-meeting throughputs for time-critical applications with uncertain time-varying bandwidth allocations. First, we model an optimization problem of scheduling deadline-constrained flows under uncertain time-varying bandwidth allocations to maximize the expected deadline-meeting throughput. The problem is NP-hard. Then, we propose an approximation algorithm under a mild condition for the problem in a special case, where bandwidth allocations are certain, as well as a conditional approximation algorithm for the problem in general. To adapt to practice, scalable and online variants of the algorithm are also presented. In evaluation, we conduct simulations based on a real traffic trace in a production datacenter. The results demonstrate that, with severe practical settings, UBAS still achieves nearly optimal deadline-meeting throughputs. Moreover, the throughput improvements of UBAS against existing bandwidth-agnostic schemes are more substantial when the variance of bandwidth allocations over time increases. [ABSTRACT FROM AUTHOR]

The fusion of hesitant fuzzy set (HFS) and fuzzy–rough set (FRS) is explored and applied into the task of classification due to its capability of conveying hesitant and uncertainty information. In this paper, on the basis of studying the equivalence relations between hesitant fuzzy elements and HFS operation updating, the target instances are classified by employing the lower and upper approximations in hesitant FRS theory. Extensive performance analysis has been conducted including classification accuracy results, execution time, and the impact of k parameter to evaluate the proposed hesitant fuzzy–rough nearest-neighbor (HFRNN) algorithm. The experimental analysis has shown that the proposed HFRNN algorithm significantly outperforms current leading algorithms in terms of fuzzy–rough nearest-neighbor, vaguely quantified rough sets, similarity nearest-neighbor, and aggregated-similarity nearest-neighbor. [ABSTRACT FROM AUTHOR]

The SDN control plane needs to frequently update the data plane as the network conditions change. Since each switch updates its flow table independently and asynchronously, the transition of data plane state—if done directly from the initial to the final stage—may result in serious flash congestion. Prior work strives to find a congestion-free update plan with multiple stages, each with the property that there will be no congestion independent of the update order. Yet congestion-free update may prevent the network from being fully utilized. It also requires solving a series of LP which is time-consuming. In this paper, we propose congestion-minimizing update and focus on two general problems: The first is to find routing at each intermediate stage that minimizes transient congestion for a given number of intermediate stages. The second is to find the minimum number of intermediate stages and an update plan for a given maximum level of transient congestion. We formulate them as two optimization programs and prove their hardness. We propose a set of algorithms to find the update plan in a scalable manner. Extensive experiments with Mininet show that our solution reduces update time by 50 percent and saves control overhead by 38 percent compared to prior work. [ABSTRACT FROM AUTHOR]

Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) –a novel algorithm for the frequency, top-k, and byte volume estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives, for the frequency estimation problem, by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top- $k$ identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the workloads’ skewness. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. In Addition, we present d-way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits. [ABSTRACT FROM AUTHOR]

This paper presents a parameterized batch reinforcement learning algorithm for near-optimal longitudinal control of autonomous land vehicles (ALVs). The proposed approach uses an actor-critic architecture, where parameterized feature vectors based on kernels are learned from collected samples for approximating the value functions and policies. One difference between the parameterized batch actor-critic (PBAC) algorithm and previous actor-critic learning approaches is that the critic and actor in PBAC share the same linear features, which has been theoretically proved to be a beneficial property for the convergence of actor-critic learning approaches. In order to obtain better learning efficiency, least-squares-based batch updating rules are designed for the critic and actor, respectively. Based on the PBAC learning algorithm, a data-driven longitudinal control method is presented for ALVs to obtain near-optimal control policies which adaptively tune the fuel/brake control signals to track different speeds. A multiobjective reward function is designed so that both tracking precision and driving smoothness are considered. Extensive experiments were conducted on a real ALV platform while driving on flat, slippery, sloping, and bumpy roads. The experimental results illustrate the superiority of the PBAC-based self-learning controller over conventional longitudinal control methods such as proportional-integral (PI) control and learning-based PI control. [ABSTRACT FROM AUTHOR]

Inverted generational distance (IGD) has been widely considered as a reliable performance indicator to concurrently quantify the convergence and diversity of multiobjective and many-objective evolutionary algorithms. In this paper, an IGD indicator-based evolutionary algorithm for solving many-objective optimization problems (MaOPs) has been proposed. Specifically, the IGD indicator is employed in each generation to select the solutions with favorable convergence and diversity. In addition, a computationally efficient dominance comparison method is designed to assign the rank values of solutions along with three newly proposed proximity distance assignments. Based on these two designs, the solutions are selected from a global view by linear assignment mechanism to concern the convergence and diversity simultaneously. In order to facilitate the accuracy of the sampled reference points for the calculation of IGD indicator, we also propose an efficient decomposition-based nadir point estimation method for constructing the Utopian Pareto front (PF) which is regarded as the best approximate PF for real-world MaOPs at the early stage of the evolution. To evaluate the performance, a series of experiments is performed on the proposed algorithm against a group of selected state-of-the-art many-objective optimization algorithms over optimization problems with 8-, 15-, and 20-objective. Experimental results measured by the chosen performance metrics indicate that the proposed algorithm is very competitive in addressing MaOPs. [ABSTRACT FROM AUTHOR]

Microarray technology enables the collection of vast amounts of gene expression data from biological experiments. Clustering algorithms have been successfully applied to exploring the gene expression data. Since a set of genes may be only correlated to a subset of samples, it is useful to use co-clustering to recover co-clusters in the gene expression data. In this paper, we propose a novel algorithm, called Subspace Weighting Co-Clustering (SWCC), for high dimensional gene expression data. In SWCC, a gene subspace weight matrix is introduced to identify the contribution of gene objects in distinguishing different sample clusters. We design a new co-clustering objective function to recover the co-clusters in the gene expression data, in which the subspace weight matrix is introduced. An iterative algorithm is developed to solve the objective function, in which the subspace weight matrix is automatically computed during the iterative co-clustering process. Our empirical study shows encouraging results of the proposed algorithm in comparison with six state-of-the-art clustering algorithms on ten gene expression data sets. We also propose to use SWCC for gene clustering and selection. The experimental results show that the selected genes can improve the classification performance of Random Forests. [ABSTRACT FROM AUTHOR]

Service selection is crucial to service composition in determining the composite Quality of Service (QoS). The proliferation of composable services on the Internet and the practical need for timely delivering optimized composite solutions motivate the adoption of population-based algorithms for QoS-aware service selection. However, existing population-based algorithms are generally complicated to use, and often used as a general approach to solving different optimization problems. We propose to develop specialized algorithms for QoS-aware service selection, based on the artificial bee colony algorithm (ABC). ABC is a new and simpler implementation of swarm intelligence, which has proven to be successful in solving many real-world problems, especially the numerical optimization problems. We develop an approximate approach for the neighborhood search of ABC, which enables effective local search in the discrete space of service selection in a way that is analogical to the search in a continuous space. We present three algorithms based on the approach. All the three algorithms are designed to improve the performance and meanwhile preserve the simplicity of ABC. Each algorithm applies a different technique to leverage the unique characteristics of the service selection problem. Experimental results show higher accuracy and convergence speed of the proposed algorithms over the state of the art algorithms. [ABSTRACT FROM AUTHOR]

High-order graph matching is a feature-matching algorithm that uses geometric information among features. This algorithm is more robust to repetitive patterns or unclear areas than first-order matching that uses only feature descriptors. However, the processing speed of high-order matching is very slow because of its high computational complexity. To accelerate its speed, this paper proposes a new parallelization algorithm of high-order matching for GPU execution. The obstacle for parallelization is the write collision caused by multiple threads that must simultaneously update the data at the same memory location. In high-order matching, multiple formulations of the objective function can generate the same solution. By taking advantage of this property, the proposed algorithm replaces the operation causing write collision with another operation eliminating the collision while generating the same solution. The proposed algorithm is tested with GTX 960 and takes 31.3 ms, which is 68 times faster than the execution time with a CPU and approximately three times faster than that with a straightforward parallelization for the same GPU. [ABSTRACT FROM AUTHOR]

Intelligent computing technologies are useful and important for online data modeling, where system dynamics may be nonstationary with some uncertainties. In this paper, an efficient learning mechanism is developed for building self-organizing fuzzy neural networks (SOFNNs), where a second-order algorithm (SOA) with adaptive learning rate is employed, the network size and the parameters can be determined simultaneously in the learning process. First, all parameters of SOFNN are adjusted by using the SOA strategy to achieve fast convergence through a powerful search scheme. Second, the structure of SOFNN can be self-organized using the relative importance index of each rule. The fuzzy rules used in SOFNN with SOA (SOA-SOFNN) are generated or pruned automatically to reduce the computational complexity and potentially improve the generalization power. Finally, a theoretical analysis on the learning convergence of the proposed SOA-SOFNN is given to show the computational efficiency. To demonstrate the merits of our proposed approach for data modeling, several benchmark datasets, and a real world application associated with nonlinear systems modeling problems are examined with comparisons against other existing methods. The results indicate that our proposed SOA-SOFNN performs favorably in terms of both learning speed and prediction accuracy for online data modeling. [ABSTRACT FROM AUTHOR]

Graph matching aims at establishing correspondences between graph elements, and is widely used in many computer vision tasks. Among recently proposed graph matching algorithms, those utilizing the path following strategy have attracted special research attentions due to their exhibition of state-of-the-art performances. However, the paths computed in these algorithms often contain singular points, which could hurt the matching performance if not dealt properly. To deal with this issue, we propose a novel path following strategy, named branching path following (BPF), to improve graph matching accuracy. In particular, we first propose a singular point detector by solving a KKT system, and then design a branch switching method to seek for better paths at singular points. Moreover, to reduce the computational burden of the BPF strategy, an adaptive path estimation (APE) strategy is integrated into BPF to accelerate the convergence of searching along each path. A new graph matching algorithm named ABPF-G is developed by applying APE and BPF to a recently proposed path following algorithm named GNCCP (Liu & Qiao 2014). Experimental results reveal how our approach consistently outperforms state-of-the-art algorithms for graph matching on five public benchmark datasets. [ABSTRACT FROM AUTHOR]

Measuring the performance of an algorithm for solving multiobjective optimization problem has always been challenging simply due to two conflicting goals, i.e., convergence and diversity of obtained tradeoff solutions. There are a number of metrics for evaluating the performance of a multiobjective optimizer that approximates the whole Pareto-optimal front. However, for evaluating the quality of a preferred subset of the whole front, the existing metrics are inadequate. In this paper, we suggest a systematic way to adapt the existing metrics to quantitatively evaluate the performance of a preference-based evolutionary multiobjective optimization algorithm using reference points. The basic idea is to preprocess the preferred solution set according to a multicriterion decision making approach before using a regular metric for performance assessment. Extensive experiments on several artificial scenarios, and benchmark problems fully demonstrate its effectiveness in evaluating the quality of different preferred solution sets with regard to various reference points supplied by a decision maker. [ABSTRACT FROM AUTHOR]

Weighted vertex cover (WVC), a generalized type of vertex cover, is one of the most important combinatorial optimization problems. In this paper, we provide a novel solution to the WVC problem from the view of network engineering. We model the WVC problem as an asymmetric game on weighted networks, where each vertex is treated as an intelligent rational agent rather than an inanimate one. Under the framework of asymmetric game, we find that strict Nash equilibriums of the asymmetric game are the intermediate states between the WVC states and the minimum WVC (MWVC) states. Besides, we propose best response algorithms with memory and feedback to solve the WVC problem, and find that a better approximate solution to the MWVC can be obtained under the feedback-based best response algorithm. Numerical illustrations verify the performance of the proposed game solution on weighted networks. Our findings pave a new way to solve the WVC problem from the perspective of asymmetric game, which opens a bottom-up avenue to address the combinatorial optimization problems. [ABSTRACT FROM AUTHOR]

With the proliferation of spatial-textual data such as location-based services and geo-tagged websites, spatial keyword queries are ubiquitous in real life. One example of spatial-keyword query is the so-called collective spatial keyword query (CoSKQ) which is to find for a given query consisting a query location and several query keywords a set of objects which covers the query keywords collectively and has the smallest cost wrt the query location. In the literature, many different functions were proposed for defining the ${cost}$ and correspondingly, many different approaches were developed for the CoSKQ problem. In this paper, we study the CoSKQ problem systematically by proposing a unified cost function and a unified approach for the CoSKQ problem (with the unified cost function). The unified cost function includes all existing cost functions as special cases and the unified approach solves the CoSKQ problem with the unified cost function in a unified way. Experiments were conducted on both real and synthetic datasets which verified our proposed approach. [ABSTRACT FROM AUTHOR]

We present a novel and efficient approach for computing joint graph layouts and then use it to visualize collections of segmented meshes. Our joint graph layout algorithm takes as input the adjacency matrices for a set of graphs along with partial, possibly soft, correspondences between nodes of different graphs. We then use a two stage procedure, where in the first step, we extend spectral graph drawing to include a consistency term so that a collection of graphs can be handled jointly. Our second step extends metric multi-dimensional scaling with stress majorization to the joint layout setting, while using the output of the spectral approach as initialization. Further, we discuss a user interface for exploring a collection of graphs. Finally, we show multiple example visualizations of graphs stemming from collections of segmented meshes and we present qualitative and quantitative comparisons with previous work. [ABSTRACT FROM AUTHOR]

Compared to most of the linear detection algorithms in massive multiple-input multiple-output (MIMO) systems, the Gauss-Seidel algorithm with initialization (GSI) promises a faster convergence rate. We improve the GSI algorithm by employing the first three items of Taylor expansion to approximate the reciprocals of diagonal entries and using the group inversion to obtain the inversion of the lower triangle matrix, which is feasible and efficient to implement. Simulation results show that the bit error rate performance of the improved GSI algorithm is similar to that of the minimum mean square error equalization for a MIMO system with 128 base station (BS) antennas and eight users. The algorithm can be applied to 64 and 32 BS antennas by employing two and three iterations, respectively. Based on the above improved algorithm, we develop a high-throughput and area-efficient architecture, which is further implemented on a Xilinx Virtex-7 XC7VX690T FPGA. The data are interleaved during the pipeline processing so that we can make the best use of the hardware. The presented architecture can achieve a maximum throughput of 127 Mb/s, which is 2.6 times higher than that of the existing architecture based on the GS algorithm. When ten received vectors are considered at a time, the throughput of the proposed architecture can reach up to 607 Mb/s, and it outperforms the optimized coordinate descent method in terms of resource utilization efficiency (throughput per look-up tables) by two times. [ABSTRACT FROM AUTHOR]

Three-phase four-wire (TPFW) distribution systems are prone to various power quality (PQ) issues, such as voltage fluctuations, poor power factor, unbalanced load conditions, and the presence of harmonics in current. Mitigation of these PQ problems using appropriate shunt compensator requires advanced control algorithms for control of three-phase voltage source converters (VSC) in a distribution system. In this paper, Chebyshev functional expansion based artificial neural network (ChANN) algorithm for shunt compensation using distribution static compensator (DSTATCOM) is proposed. The parameters of ChANN are trained in real time. Implementation results with linear and nonlinear loads are demonstrated on a prototype hardware designed and developed using dSPACE 1104, current and voltage sensors for the realization of DSTATCOM for TPFW system. A zigzag transformer is used along with conventional three-phase, three-wire (TPTW) DSTATCOM to reduce its overall rating. Suitable comparisons with conventional control techniques are also mentioned. [ABSTRACT FROM AUTHOR]

This paper focuses on power distribution systems with inverter-interfaced renewable energy sources (RESs), and develops a distributed control framework to steer the RES output powers to solutions of ac optimal power flow (OPF) problems. The design of the distributed control algorithm is based on suitable linear approximation of the ac power-flow equations, and leverages the so-called alternating direction method of multipliers (ADMM). Convergence of the RES-inverter output powers to solutions of the approximate ac OPF problem is established under suitable conditions on the mismatches between the commanded setpoints and actual RES output powers. Overall, since the proposed scheme can be cast as an ADMM with inexact primal and dual updates, the convergence results can be applied to more general distributed optimization settings. [ABSTRACT FROM AUTHOR]

In this paper, we devise a fast encoding algorithm for triply extended Reed–Solomon codes. The proposed approach requires approximately two XORs per bit, which improves the prior result of three XORs per bit established by certain maximum distance separable (MDS) array codes. We also prove that, for MDS codes with two and three parities, the scheduling algorithms require at least two XORs per bit. To the best of our knowledge, this is the first provable scheduling algorithm for the triple-parity MDS codes to approach the theoretical lower bounds. The implementation with SIMD instructions is provided. The simulations show that the proposed approach is competitive, as compared with other cutting edge implementations. [ABSTRACT FROM AUTHOR]

This paper presents a random walk approach to the problem of querying informative constraints for clustering. The proposed method is based on the properties of the commute time, that is the expected time taken for a random walk to travel between two nodes and return, on the adjacency graph of data. Commute time has the nice property of that, the more short paths connect two given nodes in a graph, the more similar those nodes are. Since computing the commute time takes the Laplacian eigenspectrum into account, we use this property in a recursive fashion to query informative constraints for clustering. At each recursion, the proposed method constructs the adjacency graph of data and utilizes the spectral properties of the commute time matrix to bipartition the adjacency graph. Thereafter, the proposed method benefits from the commute times distance on graph to query informative constraints between partitions. This process iterates for each partition until the stop condition becomes true. Experiments on real-world data show the efficiency of the proposed method for constraints selection. [ABSTRACT FROM AUTHOR]

Effective incentive mechanisms are invaluable in mobile crowd sensing, for stimulating participation of smartphone users. Online auction mechanisms represent a natural solution for such sensing task allocation. Departing from existing studies that focus on an isolated system round, we optimize social cost across the system lifespan, while considering location constraints and capacity constraints when assigning sensing tasks to users. The winner determination problem (WDP) at each round is NP-hard even without inter-round coupling imposed by user capacity constraints. We first propose a truthful one-round auction, comprising of an approximation algorithm for solving the one-round WDP and a payment scheme for computing remuneration to winners. We then propose an online algorithm framework that employs the one-round auction as a building block towards a flexible mechanism that makes on-spot decisions upon dynamically arriving bids. Through both theoretical analysis and trace-driven simulations, we demonstrate that our online auction is truthful, individually rational, computationally efficient, and achieves a good competitive ratio. [ABSTRACT FROM AUTHOR]

Although various methods of controlling mobile robots have been studied, the distributed tracking control problem for uncertain nonholonomic mobile multirobot (NMMR) systems in an optimal manner with disturbance rejection for both kinematics and dynamics has not been thoroughly solved. This paper, therefore, devotes a novel method to solve the problem with application to real NMMR systems equipped with omnidirectional vision sensors, of which parameters are unknown or uncalibrated. First, the distributed optimal tracking control problem of a separate system in the presence of kinematic and dynamic disturbances is transformed into the equivalent optimal regulation with disturbance rejection of an integrated system. Then, the theory of differential games is utilized to formulate the integrated system into coupled Hamilton–Jacobi–Isaac equations, of which the solutions are approximated in real time by designed algorithms. By the Lyapunov theory, it is proven that the algorithms converge, and the closed-loop systems are stable. Finally, compared simulations and experiments for a group of three robots are provided to show the effectiveness of the proposed algorithms. [ABSTRACT FROM PUBLISHER]

We consider a model of competition on complex networks, in which two competitors are fixed to opposite states while other agents, called normal agents, adjust their states according to a distributed consensus protocol. Suppose that one of the competitors could enhance its influence by creating new links. A natural question is, when the number of new links is limited due to the limited resource, how to add these links so as to maximize the influence of the given competitor over the other one (called competitiveness). We consider two competitiveness maximization problems: Problem 1 tries to maximize the number of supporters of the competitor, while Problem 2 tries to maximize the total supporting degree of normal agents toward the competitor. We prove that Problem 1 is NP-hard. We also show that the objective function of Problem 2 is monotonous and submodular, and hence there exists a polynomial-time greedy algorithm (GA) approximately solving Problem 2. Several centrality-based heuristic algorithms of less computational burden are also designed to provide approximate solutions to these two problems. We carry out extensive simulations to check the performances of these algorithms in six real networks. We find that GA always provides the best approximate solution to Problem 2, while for Problem 1, GA only has the best performance in directed networks. Furthermore, among those heuristic algorithms, an algorithm based on centrality in descending order is better than its counterpart in ascending order in solving Problem 2 in statistical sense. But for Problem 1, the performance of the centrality-based heuristic algorithms is more sensitive to the network structure and the locations of competitors. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of heterogeneous physical machines resource management (HPMRM); that is, providing and allocating multiple virtual machine (VM) instances from heterogeneous physical machines to maximize social welfare. Although existing allocation mechanisms allocate VMs to users through the single-mapping mechanism, such allocations cannot guarantee maximum social welfare or efficient utilization of multiple types of resources for cloud providers. Thus, we consider the multi-mapping mechanism, which permits mapping VMs allocated to one user to physical machines for VM provisioning and allocation. This can result in improved social welfare and lead to less resource fragmentation. We formulate the HPMRM problem in an auction-based setting, and design optimal and approximate mechanisms to solve it. In addition, we show that our proposed mechanism is strategy-proof; that is, our proposed mechanism drives the system into an equilibrium where no users have incentives to maximize their own profit by untruthfully reporting their requests. Furthermore, we analyze the approximation ratio of our proposed approximation algorithm. We also perform experiments to investigate the performance of our proposed approximation mechanism compared to the optimal mechanism. Experimental results demonstrate that our proposed approximation mechanism can obtain near optimal solutions and significantly improve allocation efficiency, while generating greater social welfare. [ABSTRACT FROM AUTHOR]

A new density-based clustering algorithm, RNN-DBSCAN, is presented which uses reverse nearest neighbor counts as an estimate of observation density. Clustering is performed using a DBSCAN-like approach based on $k$ nearest neighbor graph traversals through dense observations. RNN-DBSCAN is preferable to the popular density-based clustering algorithm DBSCAN in two aspects. First, problem complexity is reduced to the use of a single parameter (choice of $k$ nearest neighbors), and second, an improved ability for handling large variations in cluster density (heterogeneous density). The superiority of RNN-DBSCAN is demonstrated on several artificial and real-world datasets with respect to prior work on reverse nearest neighbor based clustering approaches (RECORD, IS-DBSCAN, and ISB-DBSCAN) along with DBSCAN and OPTICS. Each of these clustering approaches is described by a common graph-based interpretation wherein clusters of dense observations are defined as connected components, along with a discussion on their computational complexity. Heuristics for RNN-DBSCAN parameter selection are presented, and the effects of $k$ on RNN-DBSCAN clusterings discussed. Additionally, with respect to scalability, an approximate version of RNN-DBSCAN is presented leveraging an existing approximate $k$ nearest neighbor technique. [ABSTRACT FROM PUBLISHER]

Scientific workloads are often described by Directed Acyclic task Graphs. Indeed, DAGs represent both a theoretical model and the structure employed by dynamic runtime schedulers to handle HPC applications. A natural problem is then to compute a makespan-minimizing schedule of a given graph. In this paper, we are motivated by task graphs arising from multifrontal factorizations of sparse matrices and therefore work under the following practical model. Tasks are malleable (i.e., a single task can be allotted a time-varying number of processors) and their speedup behaves perfectly up to a first threshold, then speedup increases linearly, but not perfectly, up to a second threshold where the speedup levels off and remains constant. After proving the NP-hardness of minimizing the makespan of DAGs under this model, we study several heuristics. We propose model-optimized variants for PropScheduling, widely used in linear algebra application scheduling, and FlowFlex. GreedyFilling is proposed, a novel heuristic designed for our speedup model, and we demonstrate that PropScheduling and GreedyFilling are 2-approximation algorithms. In the evaluation, employing synthetic data sets and task graphs arising from multifrontal factorization, the proposed optimized variants and GreedyFilling significantly outperform the traditional algorithms, whereby GreedyFilling demonstrates a particular strength for balanced graphs. [ABSTRACT FROM AUTHOR]

As a by-product of industrial development, large quantities of hazardous materials are shipped in the transportation network every day. The risk of transporting hazardous materials is an important consideration in transportation planning. Vehicle routing models in previous studies simultaneously minimized the transportation cost and the total risk. However, simply evaluating the total risk of a fleet as a whole does not consider each individual vehicle’s risk. Even if the total risk is low, the risk of a specific vehicle may still be very high. In addition, the situation of several vehicles of a logistics company shipping hazardous materials and travelling on the same road together, called vehicles travelling in echelon, may cause a chain of incidents. This situation has been ignored in previous studies. In this paper, a bi-objective vehicle routing model for hazardous materials transportation with no vehicles travelling in echelon is developed, simultaneously minimizing the maximum risk of each vehicle and the transportation cost. A two-stage exact algorithm is developed based on the $\varepsilon $ -constraint method with several improvements to solve the proposed problem. An approximation approach is proposed for this two-stage algorithm for large-scale problems. Furthermore, the approximation ratio and time complexity of this approximation algorithm are analyzed. Computational experiments with randomly generated instances are reported, and several managerial insights are derived from the sensitivity analysis. [ABSTRACT FROM AUTHOR]

Feature selection based on fuzzy rough sets is an effective approach to select a compact feature subset that optimally predicts a given decision label. Despite being studied extensively, most existing methods of fuzzy rough set based feature selection are restricted to computing the whole dataset in batch, which is often costly or even intractable for large datasets. To improve the time efficiency, we investigate the incremental perspective for fuzzy rough set based feature selection assuming data can be presented in sample subsets one after another. The key challenge for the incremental perspective is how to add and delete features with the subsequent arrival of sample subsets. We tackle this challenge with strategies of adding and deleting features based on the relative discernibility relations that are updated as subsets arrive sequentially. Two incremental algorithms for fuzzy rough set based feature selection are designed based on the strategies. One updates the selected features as each sample subset arrives, and outputs the final feature subset where no sample subset is left. The other updates the relative discernibility relations but only performs feature selection where there is no further subset arriving. Experimental comparisons suggest our incremental algorithms expedite fuzzy rough set based feature selection without compromising performance. [ABSTRACT FROM AUTHOR]

The main challenge of attribute reduction in large data applications is to develop a new algorithm to deal with large, noisy, and uncertain large data linking multiple relevant data sources, structured or unstructured. This paper proposes a new and efficient layered-coevolution-based attribute-boosted reduction algorithm (LCQ-ABR*) using adaptive quantum-behavior particle swarm optimization (PSO). First, the quantum rotation angle of an evolutionary particle is updated by a dynamic change of self-adapting step size. Second, a self-adaptive partitioning strategy is employed to group particles into different memeplexes, and the quantum-behavior mechanism with the particles’ states depicted by the wave function cooperates to achieve superior performance in their respective memeplexes. Third, a new layered coevolutionary model with multiagent interaction is constructed to decompose a complex attribute set, and it can self-adapt the attribute sizes among different layers and produce the reasonable decompositions by exploiting any interdependence among multiple relevant attribute subsets. Fourth, the decomposed attribute subsets are evolved to compute the positive region and discernibility matrix by using their best quantum particles, and the global optimal reduction set is induced successfully. Finally, extensive comparative experiments are provided to illustrate that LCQ-ABR* has better feasibility and effectiveness of attribute reduction on large-scale and uncertain dataset problems with complex noise as compared with representative algorithms. Moreover, LCQ-ABR* can be successfully applied in the consistent segmentation for neonatal brain three-dimensional MRI, and the consistent segmentation results further demonstrate its stronger applicability. [ABSTRACT FROM AUTHOR]

Bandwidth reservation has been increasingly used in high-performance networks to provide quality of service for various applications ranging from real-time multimedia communication in early years to big data transfer more recently. In this paper, we consider multiple bandwidth reservation requests in a batch awaiting to be scheduled in a dedicated network, and formulate two scheduling maximization problems: 1) maximize the amount of data to be transferred and 2) maximize the number of requests to be scheduled. We prove both problems are NP-complete and very difficult to approximate. We then design two heuristic algorithms and evaluate their performance against a scheduling algorithm widely used in real production networks through extensive simulation-based experiments. The experimental results show that the proposed heuristic algorithms achieve significantly better overall scheduling performance than the existing algorithm. [ABSTRACT FROM AUTHOR]

This paper considers a general stochastic resource allocation problem that arises widely in wireless networks, cognitive radio, networks, smart-grid communications, and cross-layer design. The problem formulation involves expectations with respect to a collection of random variables with unknown distributions, representing exogenous quantities such as channel gain, user density, or spectrum occupancy. We consider the constant step-size stochastic dual subgradient descent (SDSD) method that has been widely used for online resource allocation in networks. The problem is solved in dual domain, which results in a primal resource allocation subproblem at each time instant. The goal here is to characterize the non-asymptotic behavior of such stochastic resource allocations in an almost sure sense. It is well known that with a step size of \epsilon , SDSD converges to an \mathcal {O}(\epsilon) -sized neighborhood of the optimum. In practice, however, there exists a trade-off between the rate of convergence and the choice of \epsilon $ . This paper establishes a convergence rate result for the SDSD algorithm that precisely characterizes this trade-off. Toward this end, a novel stochastic bound on the gap between the objective function and the optimum is developed. The asymptotic behavior of the stochastic term is characterized in an almost sure sense, thereby generalizing the existing results for the stochastic subgradient methods. For the stochastic resource allocation problem at hand, the result explicates the rate with which the allocated resources become near-optimal. As an application, the power and user-allocation problem in device-to-device networks is formulated and solved using the SDSD algorithm. Further intuition on the rate results is obtained from the verification of the regularity conditions and accompanying simulation results. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a new multi-edge metric-constrained quasi-cyclic progressive edge-growth algorithm (MM-QC-PEGA), which is suitable for constructing both single- and multi-weighted (binary) QC low-density parity-check (LDPC) codes with arbitrary lengths, rates, circulant sizes, and variable node (VN)-degree distributions. The MM-QC-PEGA is able to detect all cyclic-edge-set-minimum-virtual cycles (CMVCs), as it accurately computes the metric value of each CMVC with an a posteriori test. In addition, we propose a new greatest-common-divisor (GCD)-approximation for time efficiently approximating the metric value of a CMVC without a posteriori tests, and propose a new GCD-approximated MM-QC-PEGA (G-MM-QC-PEGA) by using the GCD-approximation to replace the a posteriori test involved in the MM-QC-PEGA. As a result, the G-MM-QC-PEGA is faster than the MM-QC-PEGA, and the CMVCs undetectable to the G-MM-QC-PEGA under multi- and single-weighted QC-LDPC code graphs have minimum lengths of eight and ten, respectively. Moreover, we propose a new masking technique that is efficient in masking the parity-check matrix consisting of an array of arbitrary circulants of the same size. Compared with the several existing works, our proposed algorithms could perform better or comparably in terms of avoiding generating small cycles and error performances. Our proposed algorithms somewhat perfect the works of QC-LDPC code construction. [ABSTRACT FROM PUBLISHER]

The dynamic frame sizing algorithm is a throughput-optimal algorithm that can achieve maximum network throughput without the knowledge of arrival rates. Motivated by the need for energy-efficient communication in wireless networks, in this paper, we propose a new dynamic frame sizing algorithm, called the Greenput algorithm, that takes power allocation into account. In our Greenput algorithm, time is partitioned into frames, and the frame size of each frame is determined based on the backlogs presented at the beginning of a frame. To obtain a good delay-energy efficiency tradeoff, the key insight of our Greenput algorithm is to reduce transmit power to save energy when the backlogs are low so as not to incur too much packet delay. For this, we define a threshold parameter T\max (for the minimum time to empty the backlogs with maximum power allocation), and the Greenput algorithm enters the (mixed) power-saving mode when the backlogs are below the threshold. Using a large deviation bound, we prove that our Greenput algorithm is still throughput optimal. In addition to the stability result, we also perform a fluid approximation analysis for energy efficiency and average packet delay when T\max is very large. To show the delay-energy efficiency tradeoff, we conduct extensive computer simulations by using the Shannon formula as the channel model in a wireless network. Our simulation results show that both energy efficiency and average packet delay are quite close to their fluid approximations even when T\max is moderately large. [ABSTRACT FROM AUTHOR]

We study the optimal placement of content over a network of caches, a problem naturally arising in several networking applications. Given a demand of content request rates and paths followed, we wish to determine the content placement that maximizes the expected caching gain, i.e., the reduction of routing costs due to intermediate caching. The offline version of this problem is NP-hard and, in general, the demand and topology may be a priori unknown. Hence, a distributed, adaptive approximation algorithm for placing contents into caches is desired. We show that path replication, a simple algorithm frequently encountered in literature, can be arbitrarily suboptimal when combined with traditional eviction policies. We propose a distributed, adaptive algorithm that performs stochastic gradient ascent on a concave relaxation of the expected caching gain, and constructs a probabilistic content placement within a $1-1/e$ factor from the optimal, in expectation. Motivated by our analysis, we also propose a novel greedy eviction policy to be used with path replication, and show through numerical evaluations that both algorithms significantly outperform path replication with traditional eviction policies over a broad array of network topologies. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new approach to approximate the $\ell _0$ -norm for linear sparse hyperspectral unmixing of images. We approximate the $\ell _0$-norm with the $\ell _p$-norm and iteratively reduce $p$ to enhance the results. The $p$-changing heuristic scheme that reduces the value of $p$ smoothly and iteratively, results in an enhanced sparse solution. We introduce an iteratively reweighted $\ell _2$ -norm to approximate the $\ell _p$ -norm. In this approach, a parameter $\epsilon$ is involved to deal with the fact that $\ell _p$ -norm problem is not Lipschitz continuous for the region of $p<1$. We propose two different methods to update the pair $(p,\epsilon)$. Finally, we evaluate our proposed heuristic $\ell _p$-norm method over the synthetic data as well as real hyperspectral dataset. Experimental results show that our algorithm outperforms several state-of-the-art algorithms in terms of the reconstruction errors and their probability of success. [ABSTRACT FROM PUBLISHER]

In this letter, an improved algorithm for electromagnetic (EM)-driven size reduction of wideband antennas is proposed. Our methodology utilizes variable-fidelity EM simulation models, auxiliary polynomial regression surrogates, as well as multipoint response correction. The constraint handling is implicit, using penalty functions. The core optimization algorithm is a trust-region gradient search with a repair step added in order to facilitate exploration of the feasible region boundary. The latter results in considerable reduction of the computational cost of the optimization process. The proposed methodology is demonstrated using two wideband antennas and compared to both direct optimization of the high-fidelity model and the surrogate-assisted framework without the aforementioned repair step. The results indicate superiority of the presented approach. Experimental validation of the fabricated prototypes of the optimized antennas is also provided. [ABSTRACT FROM AUTHOR]

This paper studies the base station operation and association (BOA) problem for energy-efficient heterogeneous cellular networks. The objective is to find the set of base stations (BSs) to activate and to associate users to BSs under minimum rate requirements. BOA is formulated as a nonconvex programming problem. In order to solve it, we distinguish between two cases: 1) BOA with high-rate requirements (BOAH) and 2) BOA with low-rate requirements (BOAL). First, we show that finding feasible solutions for BOAH is NP-hard, and second, we reduce it to a BS operation problem (i.e., user association becomes straightforward). Based on this reduction, we develop a brute force algorithm and show that its complexity can be extremely reduced though it is still exponential. Hence, we propose a polynomial-time heuristic algorithm. As for BOAL, since BOA is extremely coupled, we relax the problem. Consequently, BOAL can be formulated as an integer linear program. Finding feasible solutions to it is shown to be NP-hard. To efficiently solve it, we propose a greedy-based algorithm. The proposed greedy algorithm is shown to admit a logarithmic approximation factor when it finds feasible solutions and a constant approximation factor otherwise. Finally, simulation results illustrate the performance of the proposed algorithms. [ABSTRACT FROM PUBLISHER]

The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform edit costs and incorporates information about both node and edge labels. In this paper, we demonstrate that this algorithm is incorrect. We present a corrected version \mathsf B\scriptstyleRANCH that runs in \mathcalO(n^2\Delta ^3+n^3) time, where \Delta is the maximum of the maximum degrees of input graphs G and H . We also develop a speed-up that runs in \mathcal{O}(n^2\Delta ^2+n^3) time and computes an only slightly less accurate lower bound. The lower bounds produced by \mathsf B\scriptstyleRANCH and \mathsf {B\scriptstyle{RANCH}}\mathsf{F\scriptstyle{AST}} are shown to be pseudo-metrics on a collection of graphs. Finally, we suggest an anytime algorithm \mathsf B\scriptstyleRANCH\mathsfT\scriptstyleIGHT that iteratively improves \mathsf B\scriptstyleRANCH ’s lower bound. \mathsf B\scriptstyleRANCH\mathsfT\scriptstyleIGHT runs in \mathcalO(n^3\Delta ^2+I(n^2\Delta ^3+n^3)) time, where the number of iterations $I$ is controlled by the user. A detailed experimental evaluation shows that all suggested algorithms are Pareto optimal, that they are very effective when used as filters for edit distance range queries, and that they perform excellently when used within classification frameworks. [ABSTRACT FROM AUTHOR]

Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors \mathbfW and \mathbfH , for the given input matrix \mathbfA , such that \mathbfA\approx \mathbfW\mathbfH . NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient parallel algorithms to solve the problem for big data sets. The main contribution of this work is a new, high-performance parallel computational framework for a broad class of NMF algorithms that iteratively solves alternating non-negative least squares (NLS) subproblems for \mathbfW and \mathbfH . It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). The framework is flexible and able to leverage a variety of NMF and NLS algorithms, including Multiplicative Update, Hierarchical Alternating Least Squares, and Block Principal Pivoting. Our implementation allows us to benchmark and compare different algorithms on massive dense and sparse data matrices of size that spans from few hundreds of millions to billions. We demonstrate the scalability of our algorithm and compare it with baseline implementations, showing significant performance improvements. The code and the datasets used for conducting the experiments are available online. [ABSTRACT FROM AUTHOR]

Motifs in complex biological, technological, and social networks, or in other types of networks are connected to patterns that occur at significantly higher frequency compared to similar random networks. Finding motifs helps scientists to know more about networks’ structure and function, and this goal cannot be achieved without efficient algorithms. Existing methods for counting network motifs are extremely costly in CPU time and memory consumption. In addition, they restrict to the larger motifs. In this paper, a new algorithm called FraMo is presented based on ‘fractal theory’. This method consists of three phases: at first, a complex network is converted to a multifractal network. Then, using maximum likelihood estimation, distribution parameters is estimated for the multifractal network, and at last the approximate number of network motifs is calculated. Experimental results on several benchmark datasets show that our algorithm can efficiently approximate the number of motifs in any size in undirected networks and compare its performance favorably with similar existing algorithms in terms of CPU time and memory usage. [ABSTRACT FROM PUBLISHER]

Bilateral filter is an edge-preserving smoother that has applications in image processing, computer vision, and computational photography. In the past, field-programmable gate array (FPGA) implementations of the filter have been proposed that can achieve high throughput using parallelization and pipelining. An inherent limitation with direct implementations is that their complexity scales as $O(\omega ^2)$ with the filter width $\omega$ . In this paper, we propose an FPGA implementation of a fast bilateral filter that requires just $O(1)$ operations for any arbitrary $\omega$. The attractive feature of the FPGA implementation is that it is both scalable and reconfigurable. To the best of our knowledge, this is the first scalable FPGA implementation of the bilateral filter. As an application, we use the FPGA implementation for image denoising. [ABSTRACT FROM PUBLISHER]

In this paper, a perturbative technique and the related computational algorithms are presented for the prediction of differential mode (DM) to common mode (CM) conversion arising from asymmetry and nonuniformity in differential interconnects. It is shown that discontinuities evolving from nonuniformities and geometrical imbalance along the (usually desired uniform) lines give rise to equivalent distributed sources that couple the (ideally decoupled) DM and CM circuits. The prediction of modal quantities is then achieved numerically, as an iterative perturbative refinement of the frequency response of an ideal differential line. Different levels of approximation are introduced and discussed. Specifically, the assumption of weak imbalance allows analyzing the propagation of the two modes separately. Moreover, the assumption of weak nonuniformity allows avoiding CM refinements. The proposed technique applies to both ideally uniform and inherently nonuniform interconnects, and leads to a significant simulation speed-up compared to traditional approaches that analyze nonuniform lines by their subdivision into uniform sections. The methodology is illustrated based on two differential microstrip lines, one tapered and one with sinusoidally varying trace edges. Validation against full-wave simulations and measurements is provided. [ABSTRACT FROM AUTHOR]

This paper proposes a new framework for digital image processing; it relies on inexact computing to address some of the challenges associated with the discrete cosine transform (DCT) compression. The proposed framework has three levels of processing; the first level uses approximate DCT for image compressing to eliminate all computational intensive floating-point multiplications and executing the DCT processing by integer additions and in some cases logical right/left shifts. The second level further reduces the amount of data (from the first level) that need to be processed by filtering those frequencies that cannot be detected by human senses. Finally, to reduce power consumption and delay, the third level introduces circuit level inexact adders to compute the DCT. For assessment, a set of standardized images are compressed using the proposed three-level framework. Different figures of merits (such as energy consumption, delay, power-signal-to-noise-ratio, average-difference, and absolute-maximum-difference) are compared to existing compression methods; an error analysis is also pursued confirming the simulation results. Results show very good improvements in reduction for energy and delay, while maintaining acceptable accuracy levels for image processing applications. [ABSTRACT FROM AUTHOR]

Modern network elements are increasingly required to deal with heterogeneous traffic. Recent works consider processing policies for buffers that hold packets with different processing requirements (number of processing cycles needed before a packet can be transmitted out) but uniform value, aiming to maximize the throughput, i.e., the number of transmitted packets. Other developments deal with packets of varying value but uniform processing requirement (each packet requires one processing cycle); the objective here is to maximize the total transmitted value. In this paper, we consider a more general problem, combining packets with both nonuniform processing and nonuniform values in the same queue. We study the properties of various processing orders in this setting. We show that in the general case, natural processing policies have poor performance guarantees, with linear lower bounds on their competitive ratio. Moreover, we show several adversarial lower bounds for every priority queue and even for every online policy. On the positive side, in the special case when only two different values are allowed, 1 and V , we present a policy that achieves competitive ratio \left ({1+({W+2}/{V})}\right) , where W$ is the maximal number of required processing cycles. We also consider copying costs during admission. [ABSTRACT FROM AUTHOR]

Compared with traditional virtual machines, cloud containers are more flexible and lightweight, emerging as the new norm of cloud resource provisioning. We exploit this new algorithm design space, and propose scheduling frameworks for cloud container services. Our offline and online schedulers permit partial execution, and allow a job to specify its job deadline, desired cloud containers, and inter-container dependence relations. We leverage the following classic and new techniques in our scheduling algorithm design. First, we apply the compact-exponential technique to express and handle nonconventional scheduling constraints. Second, we adopt the primal-dual framework that determines the primal solution based on its dual constraints in both the offline and online algorithms. The offline scheduling algorithm includes a new separation oracle to separate violated dual constraints, and works in concert with the randomized rounding technique to provide a near-optimal solution. The online scheduling algorithm leverages the online primal-dual framework with a learning-based scheme for obtaining dual solutions. Both theoretical analysis and trace-driven simulations validate that our scheduling frameworks are computationally efficient and achieve close-to-optimal aggregate job valuation. [ABSTRACT FROM AUTHOR]

Software defined networking (SDN) is becoming increasingly prevalent for its programmability that enables centralized network configuration and management. With the growth of SDNs, a cluster of controllers cooperatively manages more and more switches/flows in a network to avoid the single-controller congestion/failure and improve the control-plane robustness. Under the architecture with multiple controllers, it is expected to minimize the maximum response time on these controllers to provide better QoS for users. To achieve this target, two previous methods are mainly used, the static scheme and the dynamic scheme. However, these methods may lead to an increase of the control-plane communication overhead/delay. In this paper, we propose to minimize the maximum response time on controllers through flow redirecting, which is implemented by installing wildcard rules on switches. We formulate the minimum controller response time problem, which takes the flow-table size and link capacity constraints into account, as an integer linear program, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The testing results and extensive simulation results show that our proposed algorithm can reduce the maximum controller response time by about 50%–80% compared with the static/dynamic methods under the same controller cost, or reduce the number of controllers by 30% compared with the dynamic method while preserving almost the same controller response time. [ABSTRACT FROM PUBLISHER]

This paper investigates how to optimize the fingerprints reporting strategy to improve localization accuracy, and how the optimal strategy theory can be utilized to streamline the design of WLAN fingerprinting localization systems. In particular, we first reveal that the fingerprints reporting problem is essentially an NP-Hard size-constrained supermodular maximization problem, and then show the inapplicability of the state-of-the-art approximation algorithms to the problem. We then propose a new algorithm and show that if the number of fingerprints measurements is large enough, then the localization accuracy is at most $1-\varepsilon$ times worse than the optimal value, with $\varepsilon$ any given constant close to 0. Moreover, we demonstrate how the optimal strategy theory can be utilized to improve accuracy of location estimation by resolving the issue of similar fingerprints for both faraway and close-by locations, with an iterative algorithm developed to cross check fingerprints sampled in different locations, in order to derive the best possible result of localization. Further, we reveal the relationship between accuracy of location estimation and coverage of Wi-Fi signals in indoor spaces when planning deployment of APs. Experiment results are presented to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

A fuzzy restricted Boltzmann machine (FRBM) is extended from a restricted Boltzmann machine (RBM) by replacing all the real-valued parameters with fuzzy numbers. A new FRBM that employs the crisp possibilistic mean value of a fuzzy number to defuzzify the fuzzy free energy function is presented. This approach is much clearer and easier to obtain the expression of the defuzzified free energy function and its approximation than the centroid method. Several theorems that discuss the error bounds of the approximation to ensure the rationality and validity are also investigated. Learning algorithms are given for the designed FRBM with symmetric triangular fuzzy numbers (STFNs), asymmetric triangular fuzzy numbers, and Gaussian fuzzy numbers. By appropriately choosing the parameters, a theorem is concluded that all FRBMs with symmetric fuzzy numbers will have identical learning algorithm to that of FRBMs with STFNs. This is illustrated by a case of FRBM with Gaussian fuzzy numbers. Two experiments including the MNIST handwriting recognition and the Bars-and-Stripes benchmark are carried out. The results show that the proposed FRBMs significantly outperform RBMs in learning accuracy and generalization ability, especially when encountering unlearned samples and recovering incomplete images. [ABSTRACT FROM PUBLISHER]