Search

With the rapid increasing of smart phones and the advances of embedded sensing technologies, mobile crowd sensing (MCS) becomes an emerging sensing paradigm for large-scale sensing applications. One of the key challenges of large-scale mobile crowd sensing is how to effectively select the minimum set of participants from the huge user pool to perform the tasks and achieve a certain level of coverage while satisfying some constraints. This becomes more complex when the sensing tasks are dynamic (coming in real time) and heterogeneous (with different temporal and spacial coverage requirements). In this paper, we consider such a dynamic participant selection problem with heterogeneous sensing tasks which aims to minimize the sensing cost while maintaining certain level of probabilistic coverage. Both offline and online algorithms are proposed to solve the challenging problem. Extensive simulations over a real-life mobile dataset confirm the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this work, we consider a sparse code multiple access uplink system, where $J$ users simultaneously transmit data over $K$ subcarriers, such that $J > K$ , with a constraint on the power transmitted by each user. To jointly optimize the subcarrier assignment and the transmitted power per subcarrier, two new iterative algorithms are proposed, the first one aims to maximize the sum-rate (Max-SR) of the network, while the second aims to maximize the fairness (Max-Min). In both cases, the optimization problem is of the mixed-integer nonlinear programming (MINLP) type, with non-convex objective functions, which are generally not tractable. We prove that both joint allocation problems are NP-hard. To address these issues, we employ a variant of the block successive upper-bound minimization (BSUM) framework, obtaining polynomial-time approximation algorithms to the original problem. Moreover, we evaluate the algorithms’ robustness against outdated channel state information (CSI), present an analysis of the convergence of the algorithms, and a comparison of the sum-rate and Jain’s fairness index of the novel algorithms with three other algorithms proposed in the literature. The Max-SR algorithm outperforms the others in the sum-rate sense, while the Max-Min outperforms them in the fairness sense. [ABSTRACT FROM AUTHOR]

The explosive growth in high-dimensional visual data requires effective regularization techniques to utilize the underlying low-dimensional structure. We consider low-rank matrix recovery, and many existing approaches are based on the nuclear norm regularization. Recently, truncated nuclear norm (TNNR) has been proposed to achieve a better approximation to the rank function than that of the traditional nuclear norm. TNNR was defined by the nuclear norm by subtracting the sum of the largest $r$ singular values. However, the estimation of $r$ is not trivial. In addition, the original algorithm based on TNNR only considers the matrix completion cases and requires double loops, which is not quite computationally efficient. Correspondingly, in this paper, we propose the adaptive bisection method to adaptively estimate $r$ , which can efficiently reduce the cost of computation. Moreover, to further accelerate computing, we apply iteratively reweighted nuclear norm to solve the nonconvex TNNR directly, and the convergence can also be guaranteed. Finally, we extend the applications of TNNR from the matrix completion problems to the general low-rank matrix recovery. Extensive experiments validate the superiority of the proposed algorithm over the state-of the-art methods. [ABSTRACT FROM AUTHOR]

The existing multiobjective evolutionary algorithms (EAs) based on nondominated sorting may encounter serious difficulties in tackling many-objective optimization problems (MaOPs), because the number of nondominated solutions increases exponentially with the number of objectives, leading to a severe loss of selection pressure. To address this problem, some existing many-objective EAs (MaOEAs) adopt Euclidean or Manhattan distance to estimate the convergence of each solution during the environmental selection process. Nevertheless, either Euclidean or Manhattan distance is a special case of Minkowski distance with the order ${P=2}$ or ${P=1}$ , respectively. Thus, it is natural to adopt Minkowski distance for convergence estimation, in order to cover various types of Pareto fronts (PFs) with different concavity–convexity degrees. In this paper, a Minkowski distance-based EA is proposed to solve MaOPs. In the proposed algorithm, first, the concavity–convexity degree of the approximate PF, denoted by the value of ${P}$ , is dynamically estimated. Subsequently, the Minkowski distance of order ${P}$ is used to estimate the convergence of each solution. Finally, the optimal solutions are selected by a comprehensive method, based on both convergence and diversity. In the experiments, the proposed algorithm is compared with five state-of-the-art MaOEAs on some widely used benchmark problems. Moreover, the modified versions for two compared algorithms, integrated with the proposed ${P}$ -estimation method and the Minkowski distance, are also designed and analyzed. Empirical results show that the proposed algorithm is very competitive against other MaOEAs for solving MaOPs, and two modified compared algorithms are generally more effective than their predecessors. [ABSTRACT FROM AUTHOR]

Mobile CrowdSensing is a new paradigm in which requesters launch tasks to the mobile users who provide the sensing services. The tasks, in practice, are usually heterogeneous (have diverse spatial-temporal requirements), which make it hard to select an efficient subset of users to perform the tasks. In this paper, we present a point of interest (PoI) based mobility prediction model to obtain the probabilities that tasks would be completed by users. Based on it, we propose a greedy offline algorithm to select a set of users under a participant number constraint. Furthermore, we extend the user selection problem to a more realistic online setting where users come in real time and we decide to select or not immediately. We formulate the problem as a submodular $k$k-secretaries problem and propose an online algorithm. Finally, we design a distributed user selection framework Crowd UserS and implement an Android prototype system as proof of the concept. Extensive simulations have been conducted on three real-life mobile traces and the results prove the efficiency of our proposed framework. [ABSTRACT FROM AUTHOR]

Exploiting the sparse activity of users, compressed sensing (CS) has been of interest in multiuser detection (MUD) for non-orthogonal multiple access (NOMA), to enable a massive connection of users in machine-type communications (MTC). In this letter, we propose a greedy algorithm with unknown sparsity level for CS-based multiuser activity and data detection in uplink grant-free NOMA. To accommodate practical scenarios, the algorithm employs a criterion to stop the iteration with no prior knowledge of sparsity level. Also, it requires no knowledge of noise variance by computing the log-likelihood ratios (LLR) approximately in its operation. With no need of sparsity and noise levels, we perform CS-based MUD with low complexity. Simulation results demonstrate that the proposed algorithm outperforms conventional CS-based solutions, nearly achieving the oracle performance of fully known supports. [ABSTRACT FROM AUTHOR]

Wireless relay network has been widely used in many applications to improve the wireless service. In this paper, we aim to maximize users' satisfaction by deploying limited number of relays in a target region to form a wireless relay network, and define the Deployment of Cooperative Relay (DoCR) problem, which is proved to be NP-complete. We first propose two approximation algorithms, an $O(\log n)$O(logn) algorithm that utilizes the algorithms for budget weighted Steiner tree problem with novel position weighting assignment, and an $O(\sqrt{k})$O(k) algorithm that iteratively scans potential positions and determines relay placement plan with the help of submodular function theory, partition technique, and greedy strategy. We name them Relay Effective Deployment Algoirthm (REDA) and Submodular Iterative Deployment Algorithm (SIDA), respectively. We further propose Gradient-Descent Based Algorithm (GDBA), a heuristic method, to solve the DoCR problem releasing potential location constraints. Our extensive experiments indicate that the algorithms we propose can significantly improve the total satisfaction of the network. Furthermore, we establish a testbed using USRP to showcase our designs in real scenarios. To the best of our knowledge, we are the first to propose approximation algorithms for relay placement problem to maximize user satisfaction, which has both theoretical and practical significance in the related area. [ABSTRACT FROM AUTHOR]

The analysis of gene expression data is useful for detecting the biological information of genes. Biclustering of microarray data has been proposed as a powerful computational tool to discover subsets of genes that exhibit consistent expression patterns along subsets of conditions. In this paper, we propose a novel biclustering algorithm called the bi-phase evolutionary biclustering algorithm. The first phase is for the evolution of rows and columns, and the other is for the evolution of biclusters. The interaction of the two phases ensures a reliable search direction and accelerates the convergence to good solutions. Furthermore, the population is initialized using a conventional hierarchical clustering strategy to discover bicluster seeds. We also developed a seed-based parallel implementation of evolutionary searching to search biclusters more comprehensively. The performance of the proposed algorithm is compared with several popular biclustering algorithms using synthetic datasets and real microarray datasets. The experimental results show that the algorithm demonstrates a significant improvement in discovering biclusters. [ABSTRACT FROM AUTHOR]

Device-to-device (D2D) communication has recently gained much attention for its potential to boost the capacity of cellular systems. D2D enables direct communication between devices while bypassing a base station (BS), hence decreasing the load of BSs and increasing the network throughput via spatial reuse of radio resources. However, the cellular system is highly dynamic, an optimal allocation plan of radio resource to D2D links at one time point can easily become suboptimal when devices move. Thus, to maximize spatial reuse in cellular systems, it is crucial to update the resource allocation adaptively to reflect the current system status. In this paper, we develop the first adaptive solution framework to the dynamic resource problem for maximizing spatial reuse. At the core of the framework, we present the two algorithms for the adaptive set multicover problem with approximation ratio $f$ and $\log n$ , respectively, where $f$ is the frequency of the most frequent element and $n$ is the total number of elements. The experimental results not only show that our solutions have a significant improvement in running time, compared with optimal or approximated offline methods, but also demonstrate their good performance through the resource usage, network throughput, and other metrics. [ABSTRACT FROM AUTHOR]

In this paper, we consider two distance-based relaxed variants of the maximum clique problem (Max Clique), named Maxd-Clique and Maxd-Club for positive integers d. Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n 1 - ε for any real ε > 0 unless P = NP , since they are identical to Max Clique (Håstad in Acta Math 182(1):105–142, 1999; Zuckerman in Theory Comput 3:103–128, 2007). In addition, it is NP -hard to approximate Maxd-Clique and Maxd-Club to within a factor of n 1 / 2 - ε for any fixed integer d ≥ 2 and any real ε > 0 (Asahiro et al. in Approximating maximum diameter-bounded subgraphs. In: Proc of LATIN 2010, Springer, pp 615–626, 2010; Asahiro et al. in Optimal approximation algorithms for maximum distance-bounded subgraph problems. In: Proc of COCOA, Springer, pp 586–600, 2015). As for approximability of Maxd-Clique and Maxd-Club, a polynomial-time algorithm, called ReFindStar d , that achieves an optimal approximation ratio of O (n 1 / 2) for Maxd-Clique and Maxd-Club was designed for any integer d ≥ 2 in Asahiro et al. (2015, Algorithmica 80(6):1834–1856, 2018). Moreover, a simpler algorithm, called ByFindStar d , was proposed and it was shown in Asahiro et al. (2010, 2018) that although the approximation ratio of ByFindStar d is much worse for any odd d ≥ 3 , its time complexity is better than ReFindStar d . In this paper, we implement those approximation algorithms and evaluate their quality empirically for random graphs. The experimental results show that (1) ReFindStar d can find larger d-clubs (d-cliques) than ByFindStar d for odd d, (2) the size of d-clubs (d-cliques) output by ByFindStar d is the same as ones by ReFindStar d for even d, and (3) ByFindStar d can find the same size of d-clubs (d-cliques) much faster than ReFindStar d . Furthermore, we propose and implement two new heuristics, Hclub d for Maxd-Club and Hclique d for Maxd-Clique. Then, we present the experimental evaluation of the solution size of ReFindStar d , Hclub d , Hclique d and previously known heuristic algorithms for random graphs and Erdős collaboration graphs. [ABSTRACT FROM AUTHOR]

Motivated by the importance of service quality in nowadays customer business environment, we focus on inventory optimization under probabilistic service level constraints, namely, the α service level (also known as the ready rate) or the β service level (also known as the fill rate). Under service level constraints, we consider two canonical stochastic inventory models: (i) the classical inventory control model with backlogging and (ii) the remanufacturing inventory control model with random product returns. The random demands could be non‐stationary, evolving and correlated over time. For each model, we first establish the optimality of generalized base‐stock policies, and then propose a new approximation algorithm that admits a worst‐case performance guarantee of 2. The core concept developed in this study is called the delayed forced holding and production cost, which is proven effective in dealing with service level constrained inventory systems. We also provide an efficient heuristic algorithm for the multi‐item inventory system. Our extensive computational experiments show that the proposed algorithms perform within 2% of optimality. [ABSTRACT FROM AUTHOR]

The Mobile Edge Network (MEN) has emerged as the basic infrastructure to support fifth-generation networks, mobile edge computing and fog computing. The characteristics of mobility must be addressed to guarantee the quality of service in MENs. As one of the critical problems in MENs, flexible deployment plays a part in exploiting edge networks. Despite the abundance of recently proposed strategies, most concentrate on the change in user demands and inevitably ignore the influence for the user mobility, which is common in future networks. We propose Provision for Mobile Edge Computing (PMEC), a prototype that takes advantage of storage devices with flexible placement. In PMEC, we accommodate various considerations and select different storage devices to cache, deploying the cache with the relationship of a two-tiered structure in the MEN. Thus, we construct a flexible overlay network with the objective of minimizing the cost in a two-tiered edge network. Based on the analysis of the problem, we solve the two-tiered placement from bottom to top using the dynamic minimal spanning tree (MST) algorithm and design two algorithms for each tier including the basic algorithm and the improved algorithms. The simulation is conducted on realistic data to demonstrate the performance of our algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we present a meta-heuristic algorithm for the resource-constrained project scheduling problem with discounted cash flows. We assume fixed payments associated with the execution of project activities and develop a heuristic optimisation procedure to maximise the net present value of a project subject to the precedence and renewable resource constraints. We investigate the use of a bi-directional generation scheme and a recursive forward/backward improvement method from literature and embed them in a meta-heuristic scatter search framework. We generate a large dataset of project instances under a controlled design and report detailed computational results. The solutions and project instances can be downloaded from a website in order to facilitate comparison with future research attempts. [ABSTRACT FROM AUTHOR]

We study the approximation capabilities of two families of univariate polynomials that arise in applications of quantum signal processing. Although approximation only in the domain [ 0 , 1 ] is physically desired, these polynomial families are defined by bound constraints not just in [ 0 , 1 ] , but also with additional bound constraints outside [ 0 , 1 ]. One might wonder then if these additional constraints inhibit their approximation properties within [ 0 , 1 ]. The main result of this paper is that this is not the case — the additional constraints do not hinder the ability of these polynomial families to approximate arbitrarily well any continuous function f : [ 0 , 1 ] → [ 0 , 1 ] in the supremum norm, provided f also matches any polynomial in the family at 0 and 1. We additionally study the specific problem of approximating the step function on [ 0 , 1 ] (with the step from 0 to 1 occurring at x = 1 2 ) using one of these families, and propose two subfamilies of monotone and non-monotone approximations. For the non-monotone case, under some additional assumptions, we provide an iterative heuristic algorithm that finds the optimal polynomial approximation. [ABSTRACT FROM AUTHOR]

This paper focuses on developing new navigation algorithms for cooperative unmanned vehicles in costmap environments. The vehicles need to plan optimal paths subject to mutual diversity. We first propose three algorithms that can find optimal paths in costmap environments with improved computational efficiency. The proposed algorithms include 1) the scaled A*; 2) the A* plus-plus; and 3) the A* plus-plus with reconstruction. The heuristics of the three algorithms are proved admissible. Then, a diversity-based path planning algorithm is proposed based on the new A star variant algorithms for multiple vehicles to plan diverse paths for risk management. In particular, we propose an iterative segment planner, which generates a set of spatially diverse paths by iteratively planning segments of all paths in a sequential manner. To prevent the generation of spatially close paths, the iterative segment planner utilizes a penalty function to increase the cost of paths that lie near the route(s) assigned to other vehicles. By varying the penalty gains, different degrees of path diversity can be achieved. Some illustrative examples are provided to compare the performance of the proposed algorithms with the standard A* and Dijkstra's algorithms, and show the effectiveness of the proposed diversity-based path planning algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present an accuracy-aware design framework [called accuracy-aware high-level synthesis (Achilles)], which synthesizes a high-level description of an input application with the objective of minimizing the energy consumption of the synthesized circuit. The proposed framework includes two main parts of Achilles and light-weight predictor selection. The framework leverages light-weight error predictors (i.e., machine learning-based classifiers) to achieve more energy reduction by dynamically managing the output quality level (exact or approximate) of the synthesized circuit. To synthesize the input application, first, we exploit a heuristic algorithm to determine the quality level required for each operation in the data flow graph (DFG) representation of the input application. Next, for synthesizing the input application, we propose an effective Achilles algorithm which utilizes the flexibility of the available multiquality arithmetic units in a high-level cell library to synthesize the datapath. To improve the efficiency, the process starts by iteratively reducing the number of functional units required for synthesizing the DFG. Then, a proper light-weight error predictor satisfying the user expected quality is chosen from the available predictors in the framework. Based on the quality requirements, three different quality management modes are considered. The efficacy of the proposed framework is assessed for benchmarks from image and signal processing as well as robotics domains. The study of these benchmarks indicates that Achilles may reduce the energy consumption up to 51% (36% on average), up to 72% (51% on average), and up to 57% (33% on average) in threshold, average, and hybrid modes, respectively, for the studied cases. Moreover, the results show that relative coverage of large errors may be increased from 21% to 55% by employing synthetic minority oversampling technique method. [ABSTRACT FROM AUTHOR]

Network function virtualization paradigm enables us to implement network functions provided in middleboxes as softwares that run on commodity servers. This paper proposes a backup resource allocation model for middleboxes with considering both failure probabilities of network functions and backup servers. A backup server can protect several functions; a function can have multiple backup servers. We take the importance of functions into account by defining a weighted unavailability for each function. We aim to find an assignment of backup servers to functions, where the worst weighted unavailability is minimized. We formulate the proposed backup resource allocation model as a mixed integer linear programming problem. We prove that the backup resource allocation problem for middlebox with importance is NP-complete. We develop three heuristic algorithms with polynomial time complexity to solve the problem. We analyze the approximation performances of different heuristic algorithms with providing several lower and upper bounds. We present the competitive evaluation in terms of deviation and computation time among the results obtained by running the heuristic algorithms and by solving the mixed integer linear programming problem. The results show the pros and cons of different approaches. With our analyses, a network operator can choose an appropriate approach according to the requirements in specific application scenarios. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of location-dependent opportunistic bandwidth sharing between static and mobile (i.e., moving) downlink users in a cellular network. Each cell of the network has some fixed number of static users. Mobile users enter the cell, move inside the cell for some time, and then leave the cell. In order to provide higher data rate to the highly mobile users whose fast fading channel variation is difficult to track, we propose location dependent bandwidth sharing between the two classes of static and mobile users; the idea is to provide higher bandwidth to the mobile users at favourable locations, and provide higher bandwidth to the static users in other times. Our approach is agnostic to the way the bandwidth is further shared within the same class of users; it can be combined with any particular bandwidth allocation policy employed for one of these two classes of users. We formulate the problem as a long run average reward Markov decision process (MDP) where the per-step reward is a linear combination of instantaneous data volumes received by static and mobile users, and find the optimal policy. The optimal policy is binary in nature; it allocates the entire bandwidth either to the static users or to the mobile users at any given time. The reward structure of this MDP is not known in general, and it may change with time. To alleviate these issues, we propose a learning algorithm based on single timescale stochastic approximation. Also, noting that the MDP problem can be used to maximize the long run average data rate for mobile users subject to a constraint on the long run average data rate of static users, we provide a learning algorithm based on multi-timescale stochastic approximation. We prove asymptotic convergence of the bandwidth sharing policies under these learning algorithms to the optimal policy. The results are extended to address the issue of fair bandwidth sharing between the two classes of static and mobile users, where the notion of fairness is motivated by the popular notion of $\alpha$α-fairness in the literature. Numerical results exhibit significant performance improvement by our scheme, as well as fast convergence, and also demonstrate the trade-off between performance gain and fairness requirement. [ABSTRACT FROM AUTHOR]

The structural graph clustering algorithm SCAN is a fundamental technique for managing and analyzing graph data. However, its high runtime remains a computational bottleneck, which limits its applicability. In this paper, we propose a novel interactive approach for tackling this problem on multicore CPUs. Our algorithm, called anySCAN, iteratively processes vertices in blocks. The acquired results are merged into an underlying cluster structure consisting of the so-called super-nodes for building clusters. During its runtime, anySCAN can be suspended for examining intermediate results and resumed for finding better results at arbitrary time points, making it an anytime algorithm which is capable of handling very large graphs in an interactive way and under arbitrary time constraints. Moreover, its block processing scheme allows the design of a scalable parallel algorithm on shared memory architectures such as multicore CPUs for speeding up the algorithm further at each iteration. Consequently, anySCAN uniquely is a both interactive and work-efficient parallel algorithm. We further introduce danySCAN an efficient bulk update scheme for anySCAN on dynamic graphs in which the clusters are updated in bulks and in a parallel interactive scheme. Experiments are conducted on very large real graph datasets for demonstrating the performance of anySCAN. They show its ability to acquire very good approximate results early, leading to orders of magnitude speedup compared to SCAN and its variants. Moreover, it scales very well with the number of threads when dealing with both static and dynamic graphs. [ABSTRACT FROM AUTHOR]

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the "diminishing returns" property of the representativeness of selected subsets, but often only has a single constraint (e.g., cardinality), which limits its applications in many real-world problems. To capture the data recency issue and support different types of constraints, we formulate dynamic RSS in data streams as maximizing submodular functions subject to general $d$d-knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes the KnapStream algorithm (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and KS instances over the sliding window. Theoretically, KW is $\frac{1-\varepsilon }{1+d}$1-ɛ1+d-approximate for SMDK. Furthermore, we propose a KnapWindowPlus framework (KW$^{+}$+) to improve upon KW. KW$^{+}$+ builds an index SubKnapChk to manage the checkpoints and KS instances. SubKnapChk deletes a checkpoint whenever it can be approximated by its successors. By keeping much fewer checkpoints, KW$^{+}$+ achieves higher efficiency than KW while still guaranteeing a $\frac{1-\varepsilon ^{\prime }}{2+2d}$1-ɛ'2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW$^{+}$+ in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK over sliding windows. KW$^{+}$+ further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities. [ABSTRACT FROM AUTHOR]

We research a scheduling algorithm for a feasible schedule construction on one machine by the total earliness of jobs minimization criterion. We propose an improvement to this algorithm. During the research, we have developed a software system to verify reliability of the algorithms. We compared the schedules built by the algorithm with those constructed by an exhaustive enumeration. We calculated the percentage of a non-exact schedule construction by the investigated algorithm for different characteristics of the schedule. The object of research is the process of schedules' optimization and their investigation. The purpose of the paper is to increase the efficiency of feasible schedules construction process for one machine in the presence of penalties for jobs completion prior to their due dates. We need to use appropriate economic and mathematical methods, in particular those from scheduling theory, to organize the production and planning on an enterprise efficiently. Scheduling problems have a great application value today. Rapid development of communication and electronics technologies increasingly requires the construction of schedules. The schedules are related to functioning of industrial enterprises and the service sector, education, transport and many other areas. Tasks of scheduling theory include study of the computational complexity of the problems and development of exact, approximation and heuristic algorithms for their solution. Most papers are devoted to combinatorial approaches' development. However, as practice shows, possibilities of combinatorial algorithms are substantially limited by the dimension of the problems they solve. This is why we believe in importance of the research and improvement of the scheduling algorithm to minimize the total earliness of jobs on one machine. We use combinatorial optimization methods, scheduling theory, heuristic algorithms and statistical analysis. The scientific novelty of the results consists in modification to the existing scheduling algorithm that minimizes the total earliness on one machine. New algorithm has better efficiency than the existing ones. [ABSTRACT FROM AUTHOR]

Cross-docks serve as distribution centers where shipments from different vendors are first consolidated according to their destinations, and then delivered to the retailers directly, with little or no storage in between. A critical problem encountered in the operation of cross-docks is the assignment of receiving and shipping doors, which greatly influences the labor or machinery cost of transferring the shipments between inbound and outbound transports. We show that the cross-dock door assignment problem (CDAP) is strictly non-deterministic polynomial-time complete. Although some deterministic algorithms have been reported to handle small-scale problems, the solutions to the middle- and large-scale CDAPs progressed at a slow pace. In this paper, we develop a nature-inspired dual-colony ant algorithm for CDAP, in which the two colonies of ants cooperatively search the optimal assignments of receiving and shipping doors to minimize the transferring costs of shipments. A collaborative local search strategy is designed and incorporated into the algorithm to enhance the search efficiency. Experiments have been conducted on a number of problem instances with different cross-dock sizes and freight flow patterns. The results show that the proposed algorithm is very competitive and can provide better solutions than the state-of-the-art heuristic algorithms. [ABSTRACT FROM AUTHOR]

We develop the optimal economical caching schemes in cache-enabled heterogeneous networks, while delivering multimedia video services with personalized viewing qualities to mobile users. By applying scalable video coding (SVC), each video file to be requested is divided into one base layer (BL) and several enhancement layers (ELs). In order to assign different transmission tasks, the serving small-cell base stations (SBSs) are grouped into $K$ clusters. The SBSs are able to cache and cooperatively transmit BL and EL contents to the user. We analytically derive expressions for successful transmission probability and ergodic service rate, and then the closed-form expression for EConomical Efficiency (ECE) is obtained. In order to enhance the ECE performance, we formulate the ECE optimization problems for two cases. In the first case, with equal cache size equipped at each SBS, the layer caching indicator is determined. Since this problem is NP-hard, after the $l_{0}$ -norm approximation, the discrete optimization variables are relaxed to be continuous, and this relaxed problem is convex. Next, based on the optimal solution derived from the relaxed problem, we devise a greedy-strategy based heuristic algorithm to achieve the near-optimal layer caching indicators. In the second case, the cache size for each SBS, the layer size, and the layer caching indicator are jointly optimized. This problem is a mixed integer programming problem, which is more challenging. To effectively solve this problem, the original ECE maximization problem is divided into two subproblems. These two subproblems are iteratively solved until the original optimization problem is convergent. Numerical results verify the correctness of the theoretical derivations. Additionally, compared to the most popular layer placement strategy, the performance superiority of the proposed SVC-based caching schemes is testified. [ABSTRACT FROM AUTHOR]

This paper proposes a novel technique using fuzzy logic controller (FLC) in circulating mode to improve the performance of the International Thermonuclear Experimental Reactor (ITER) poloidal field (PF) converter systems. The accurate mathematical modeling of the complex system is challenging using conventional proportional integral and derivative (PID) controller. The novel approach using FLC overcomes the complexity of the modeling by human expert’s knowledge and experience. The FLC is considered for ITER PF converter system and compared with a conventional PI controller. The dynamic behavior and transient response of the PF converter system in the circulating mode are verified by analysis and simulation. The analysis results determine that the FLC can achieve better operation performance. [ABSTRACT FROM AUTHOR]

Contactors are typical electromagnetic devices whose optimization is multi-objective optimization problems. Contactors’ static and dynamic characteristics obtained by the finite-element method (FEM) are typical objectives. Due to the low efficiency of FEM, the intelligent optimization algorithms that require multiple computations cannot be applied well here. In this paper, a fast algorithm for characteristics of contactors based on radial basis function neural network approximate model is proposed. The orthogonal least squares, data pre-processing and subsection modeling methods are adopted here to make the model more accurate. Meanwhile, a hybrid multi-objective optimization algorithm which combines the differential evolution and the particle swarm optimization is also proposed to speed up convergence and obtain the limit optimal solutions. The feasibility of the above-mentioned methods has been verified by solving a multi-objective optimization problem of the contactor with solenoid structure. [ABSTRACT FROM AUTHOR]

Given a set of points in the Euclidean plane, the Euclidean δ -minimum spanning tree (δ -MST) problem is the problem of finding a spanning tree with maximum degree no more than δ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean δ -minimum bottleneck spanning tree (δ -MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When δ ≤ 4 , these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested. [ABSTRACT FROM AUTHOR]

An important evolution of the users’ needs is represented by the on-demand access to the network, storage, and compute resources in order to dynamically match the level of resource consumption with their service requirements. The response of the network providers is to transition to an architecture based on softwarization and cloudification of the network functions. This is the rationale for the deployment of network functions virtualization (NFV) where virtual network functions (VNFs) may be chained together to create network services. Efficient online routing of demand across nodes handling the functions involved in a given service chain is the novel problem that we address in this paper. We provide an original formulation of this problem that includes link and CPU capacity constraints and is based on the construction of an expanded network. We derive the exact mathematical formulation and propose several heuristic algorithms taking into account the main system’s parameters. We conclude by deriving some interesting insights both about the algorithms and the network performance by comparing the heuristics with the exact solutions. [ABSTRACT FROM AUTHOR]

Highlights • The algorithm is on average 20% more efficient (faster). • The algorithm has 511% (158%) (mean, median) faster convergence. • Probability bound is calculated. • The algorithm can potentially have many applications. Abstract It is well known that Minimum Feedback Arc Set is in a general case NP-complete. There are different kinds of exact, heuristic and approximation algorithms for solving this problem, but currently there is only one published Monte Carlo algorithm which solves Minimum Feedback Arc Set in polynomial time with arbitrary probability. To further advance the state of the art we have devised new and improved ant inspired Monte Carlo algorithm which on average has 20% faster empirical running time. Due to a learning mechanism the new algorithm also achieved 511% faster convergence in terms of median and 158% improvement in terms of arithmetic mean. This has been done while at the same time maintaining the ability of the algorithm to find optimal solution with arbitrary probability. In addition, the new and improved ant inspired algorithm has substantially improved convergence consistency. A tighter probability bound has also been calculated for the Monte Carlo algorithm. The aforementioned contributions have their significance in a design and implementation of expert and intelligent system. Considering a wide presence of MFAS in a variety of areas the obtained results are significant in other applications as well. [ABSTRACT FROM AUTHOR]

In this paper, we investigate non-cooperative radio resource management in a vehicle-to-vehicle communication network. The technical challenges lie in high-vehicle mobility and data traffic variations. Over the discrete scheduling slots, each vehicle user equipment (VUE)-pair competes with other VUE-pairs in the coverage of a road side unit (RSU) for the limited frequency to transmit queued data packets, aiming to optimize the expected long-term performance. The frequency allocation at the beginning of each slot at the RSU is regulated by a sealed second-price auction. Such interactions among VUE-pairs are modeled as a stochastic game with a semi-continuous global network state space. By defining a partitioned control policy, we transform the original game into an equivalent stochastic game with a global queue state space of finite size. We adopt an oblivious equilibrium (OE) to approximate the Markov perfect equilibrium, which characterizes the optimal solution to the equivalent game. The OE solution is theoretically proven to be with an asymptotic Markov equilibrium property. Due to the lack of a priori knowledge of network dynamics, we derive an online algorithm to learn the OE solution. Numerical simulations validate the theoretical analysis and show the effectiveness of the proposed online learning algorithm. [ABSTRACT FROM AUTHOR]

We consider the problem of throughput-optimal broadcasting in a time-varying wireless network with an underlying Directed Acyclic (DAG) topology. Known broadcast algorithms route packets along pre-computed spanning trees. In large wireless networks with time-varying connectivities, the optimal trees are difficult to compute and maintain. In this paper, we propose a new online throughput-optimal broadcast algorithm, which takes packet-by-packet scheduling and routing decisions, obviating the need for any global topological structures, such as spanning trees. Our algorithm utilizes certain queue-like system-state information for making transmission decisions and hence, may be thought of as a generalization of the well-known back-pressure policy, which makes point-to-point unicast transmission decisions based on the local queue-length information. Technically, the back-pressure algorithm is derived by greedily stabilizing the queues. However, because of packet-duplications, the work-conservation principle is violated, and an analogous queueing process is non-trivial to define in the broadcast setting. To address this fundamental issue, we identify certain state variables whose dynamics behave like virtual queues. By stochastically stabilizing these virtual queues, we devise a throughput-optimal broadcast policy. We also derive new characterizations of the broadcast capacity of time-varying wireless DAGs and propose efficient algorithms to compute the capacity either exactly or approximately under various assumptions. [ABSTRACT FROM AUTHOR]

Our ever-increasing reliance on electricity coupled with inefficient consumption has resulted in several economical and environmental threats. To curb these threats, smart grids are emerging. These improved power systems could potentially reduce the peak consumption and better match demand to supply, to produce both economical and environmental advantages. In this work, we consider two pricing problems in the smart grid, under a dynamic pricing model, where consumers follow threshold policies to schedule their power consumption. The first problem is to set the prices during the different time periods such that the peak demand is minimized. The second problem is to set the prices such that the power demand matches the supply. Firstly, we propose generic heuristics called GREEDY and SLIDING-WINDOW that are able to solve the two studied problems in addition to any other optimization problem, under the same model. Secondly, we provide theoretical analysis for the uniform-pricing approach in the context of peak-demand minimization. In addition, we propose optimal algorithms for the two optimization problems that can be used when the maximum deadline period of the power jobs is relatively small. Moreover, we conduct several experiments to evaluate the proposed algorithms and the uniform pricing approach on real data. Our experimental results showed that our proposed heuristics have a relatively low approximation ratio, and have the potential to provide a significant energy saving in many cases compared to the Time-of-Use (ToU) pricing. Furthermore, the experiments showed that while the uniform pricing has an acceptable approximation ratio in the average case, it leads to energy loss compared to the ToU pricing. Finally, the experiments demonstrated a tradeoff between optimality and speed. [ABSTRACT FROM AUTHOR]

Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable $X_i$ is represented by $\ell$ nodes (where $\ell$ is the number of labels) arranged in a column. However, this method in general requires $2\;\ell ^2$ edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer. [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]

Multicasting is a fundamental functionality of many network applications, including online conferencing, event monitoring, video streaming, and so on. To ensure reliable, secure, and scalable multicasting, a service chain that consists of network functions (e.g., firewalls, intrusion detection systems, and transcoders) usually is associated with each multicast request. We refer to such a multicast request with service chain requirement as an network function virtualization (NFV)-enabled multicast request. In this paper, we study NFV-enabled multicasting in a software-defined network (SDN) with an aim to maximize network throughput while minimizing the implementation cost of admitted NFV-enabled multicast requests, subject to network resource capacity, where the implementation cost of a request consists of its computing resource consumption cost in servers and its network bandwidth consumption cost when routing and processing its data packets in the network. To this end, we first formulate two NFV-enabled multicasting problems with and without resource capacity constraints and one online NFV-enabled multicasting problem. We then devise two approximation algorithms with an approximation ratio of $2M$ for the NFV-enabled multicasting problems with and without resource capacity constraints, if the number of servers for implementing the service chain of each request is no greater than a constant $M$ (≥1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an efficient heuristic, and for the special case of dynamic request admissions, we devise an online algorithm with a competitive ratio of $O(\log n)$ for it when $M=1$ , where $n$ is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising and outperform existing heuristics. [ABSTRACT FROM AUTHOR]

We introduce a new technique for the analysis of online algorithms, namely bijective analysis, that is based on pair-wise comparison of the costs incurred by the algorithms. Under this framework, an algorithm A is no worse than an algorithm B if there is a bijection π defined over all request sequences of a given size such that the cost of A on σ is no more than the cost of B on B(π(σ)). We also study a relaxation of bijective analysis, termed average analysis, in which we compare two algorithms based on their corresponding average costs over request sequences of a given size. We apply these new techniques in the context of two fundamental online problems, namely paging and list update. For paging, we show that any two lazy online algorithms are equivalent under bijective analysis. This result demonstrates that, without further assumptions on characteristics of request sequences, it is unlikely, or even undesirable, to separate online paging algorithms based on their performance. However, once we restrict the set of request sequences to those exhibiting locality of reference, and in particular using a model of locality due to Albers et al. (J Comput Syst Sci 70(2):145-175, 2005), we demonstrate that Least-Recently-Used (LRU) is the unique optimal strategy according to average analysis. This is, to our knowledge, the first deterministic model to provide full theoretical backing to the empirical observation that LRU is preferable in practice. Concerning list update, we obtain similar conclusions, in terms of the bijective comparison of any two online algorithms, and in terms of the superiority (albeit not necessarily unique) of the Move-To-Front (MTF) heuristic in the presence of locality of reference. [ABSTRACT FROM AUTHOR]

We propose a method of supervised estimation with a training set of the posterior probabilities of an object belonging to classes according to a collection of known values of its features. These probabilities represent comprehensive information for solving the classification problem. They allow to solve the classification problem under various criteria (maximum probability, minimum average cost of error, etc.), which are usually chosen subjectively. Our approach to solving this problem is based on the construction of a series of approximations of special discriminant functions at whose zero points the posterior probabilities of the classes are specified during their construction. The heuristic approximation algorithm of the discriminant function used in the neighborhood of zero values is a part of the method. In the method, there is no need for additional modifications such as the Platt's calibrator for the method of support vector machines. We give model examples of applying the proposed approach and an example from medical diagnostics with real data. [ABSTRACT FROM AUTHOR]

Unmanned Aerial Vehicle (UAV) networks have emerged as a promising technique to rapidly provide wireless coverage to a geographical area, where a flying UAV can be fast deployed to serve as cell site. Existing work on UAV-enabled wireless networks overlook the fast UAV deployment for wireless coverage, and such deployment problems have only been studied recently in sensor networks. Unlike sensors, UAVs should be deployed to the air and they are generally different in flying speed, operating altitude and wireless coverage radius. By considering such UAV heterogeneity to cover the whole target area, this paper studies two fast UAV deployment problems: one is to minimize the maximum deployment delay among all UAVs (min-max) for fairness consideration, and the other is to minimize the total deployment delay (min-sum) for efficiency consideration. We prove both min-max and min-sum problems are NP-complete in general. When dispatching UAVs from the same location, we present an optimal algorithm of low computational complexity $O(n^2)$ for the min-max problem. When UAVs are dispatched from different locations, we propose to preserve their location order during deployment and successfully design a fully polynomial time approximation scheme (FPTAS) of computation complexity $O(n^2 \log \frac{1}{\epsilon })$ to arbitrarily approach the global optimum with relative error $\epsilon$ . The min-sum problem is more challenging. When UAVs are dispatched from the same initial location, we present an approximation algorithm of linear time. As for the general case, we further reformulate it as a dynamic program and propose a pseudo polynomial-time algorithm to solve it optimally. [ABSTRACT FROM AUTHOR]

In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized.We first prove the objective function of RSM problem is not submodular. Then, we propose both submodular lower-bound and upper-bound of the objective function. Next, we develop a heuristic algorithm to approximate the objective function. Furthermore, we reformulate our objective function as the DS function (the Difference of Submodular functions). Finally, we conduct experiments on real-world datasets to evaluate our proposed method. The experiment results show that the upper and lower bounds are very close, which indicates the good quality of them. And, the proposed method outperforms the comparison methods. [ABSTRACT FROM AUTHOR]

Lifetime of a battery is one of the major concerns in wireless sensor networks (WSNs). The traditional network algorithm chooses the data transmission path based on the distance between sender and receiver. For example, in directed diffusion, the nodes closer to the sink node are more active so that the continuous data flow of the network is maintained. However, in such a scenario, there is an energy hole problem because the nodes closer to the sink reduce their energy since they are more active. But if the residual energy and shortest hop counts can be taken together, then the problem can be overcome. We have analyzed different transmission cost functions with respect to approximated uniform energy dissipation directed diffusion algorithm. The final goal of the paper is to find out the suitable cost function to resist the early death of the first node of a network. We introduce dynamic priority variable, which is a tradeoff between total energy consumption and uniform energy dissipation. [ABSTRACT FROM AUTHOR]