Search

The explosive growth of mobile devices promotes the prosperity of novel mobile applications, which can be realized by service offloading with the assistance of edge computing servers. However, due to limited computation and storage capabilities of a single server, long service latency hinders the continuous development of service offloading in mobile networks. By supporting multi-server cooperation, Pervasive Edge Computing (PEC) is promising to enable service migration in highly dynamic mobile networks. With the objective of maximizing the system utility, we formulate the optimization problem by jointly considering the constraints of server storage capability and service execution latency. To enable dynamic service placement, we first utilize Lyapunov optimization method to decompose the long-term optimization problem into a series of instant optimization problems. Then, a sample average approximation-based stochastic algorithm is proposed to approximate the future expected system utility. Afterwards, a distributed Markov approximation algorithm is utilized to determine the service placement configurations. Through theoretical analysis, the time complexity of our proposed algorithm is linear to the number of users, and the backlog queue of PEC servers is stable. Performance evaluations are conducted based on both synthetic and real trace-driven scenarios, with numerical results demonstrating the effectiveness of our proposed algorithm from various aspects. [ABSTRACT FROM AUTHOR]

This paper addresses the output feedback distributed containment control problem for a class of nonlinear stochastic multiagent systems under a fixed directed graph. Existing works usually design the containment control protocol using backstepping design method based on a conservative Lipschitz condition on nonlinear functions, which has a tedious control design procedure. In this paper, a new output feedback distributed containment control algorithm is proposed based on a novel dynamic compensator, which can not only simplify the control design procedure but also relax the condition on nonlinear terms. The proposed distributed containment protocol for each agent depends only on the agent output and the relative outputs of its neighbor agents, and can reduce the communication burden between the agents. Based on the Lyapunov stability theory, it is proved that the outputs of the followers are driven into the convex hull spanned by the outputs of the leaders with the proposed linear controller. Finally, the effectiveness of the theoretical results is illustrated by simulation examples. [ABSTRACT FROM AUTHOR]

Only when we understand how hackers think, can we defend against their attacks. Towards this end, this paper studies the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one type of such attacks called Maximum Vertex Coverage Attacks under Knapsack constraint (MVCAK), in which a hacker has a fixed budget to remove nodes from a network with the nodes involving different costs for removal, and the hacker’s goal is to maximize the number of links incident to the nodes removed. Since the MVCAK problem is NP-hard, we firstly propose an optimal solution by Integer Linear Program formulation. Secondly, we give an approximate solution by Linear Programming relaxation that achieves an approximation ratio of 3/4, outperforming the existing 1 - 1√(e) (about 0.39). Thirdly, since the straightforward implementation of our approximate solution has a high time complexity, we propose two heuristics to significantly reduce its complexity while preserving the approximation ratio. We formally prove the correctness and the effectiveness of these two heuristics. Finally, we conduct extensive experiments on both artificial and real-world networks, showing that our approximate solution produces almost the same results as the optimal solution in practice and has an acceptable running time. [ABSTRACT FROM AUTHOR]

In-memory error correction code (ECC) is a promising technique to improve the yield and reliability of high density memory design. However, the use of in-memory ECC poses a new problem to memory repair analysis algorithm, which has not been explored before. This article first makes a quantitative evaluation and demonstrates that the straightforward algorithms for memory with redundancy and in-memory ECC have serious deficiency on either repair rate or repair analysis speed. Accordingly, an optimal repair analysis algorithm that leverages preprocessing/filter algorithms, hybrid search tree, and depth-first search strategy is proposed to achieve low computational complexity and optimal repair rate in the meantime. In addition, a heuristic repair analysis algorithm that uses a greedy strategy is proposed to efficiently find repair solutions. Experimental results demonstrate that the proposed optimal repair analysis algorithm can achieve optimal repair rate and increase the repair analysis speed by up to 105 × compared with the straightforward exhaustive search algorithm. The proposed heuristic repair analysis algorithm is approximately 28 percent faster than the proposed optimal algorithm, at the expense of 5.8 percent repair rate loss. [ABSTRACT FROM AUTHOR]

As an emerging social dynamic system, geo-social network can be used to facilitate viral marketing through the wide spread of targeted advertising. However, unlike traditional influence spread problem, the heterogeneous spatial distribution has to incorporated into geo-social network environment. Moreover, from the perspective of business managers, it is indispensable to balance the tradeoff between the objective of influence spread maximization and objective of promotion cost minimization. Therefore, these two goals need to be seamlessly combined and optimized jointly. In this paper, considering the requirements of real-world applications, we develop a multiobjective optimization-based influence spread framework for geo-social networks, revealing the full view of Pareto-optimal solutions for decision makers. Based on the reverse influence sampling (RIS) model, we propose a similarity matching-based RIS sampling method to accommodate diverse users, and then transform our original problem into a weighted coverage problem. Subsequently, to solve this problem, we propose a greedy-based incrementally approximation approach and heuristic-based particle swarm optimization approach. Extensive experiments on two real-world geo-social networks clearly validate the effectiveness and efficiency of our proposed approaches. [ABSTRACT FROM AUTHOR]

Conventional Internet of Things (IoT) applications involve data capture from various sensors in environments, and the captured data then is processed in remote clouds. However, some critical IoT applications (e.g., autonomous vehicles) require a much lower response latency and more secure guarantees than those offered by remote clouds today. Mobile edge clouds (MEC) supported by the network function virtualization (NFV) technique have been envisioned as an ideal platform for supporting such IoT applications. Specifically, MECs enable to handle IoT applications in edge networks to shorten network latency, and NFV enables agile and low-cost network functions to run in low-cost commodity servers as virtual machines (VMs). One fundamental problem for the provisioning of IoT applications in an NFV-enabled MEC is where to place virtualized network functions (VNFs) for IoT applications in the MEC, such that the operational cost of provisioning IoT applications is minimized. In this paper, we first address this fundamental problem, by considering a special case of the IoT application placement problem, where the IoT application and VNFs of each service request are consolidated into a single location (gateway or cloudlet), for which we propose an exact solution and an approximation algorithm with a provable approximation ratio. We then develop a heuristic algorithm that controls the resource violation ratios of edge clouds in the network. For the IoT application placement problem for IoT applications where their VNFs can be placed to multiple locations, we propose an efficient heuristic that jointly places the IoT application and its VNFs. We finally study the performance of the proposed algorithms by simulations and implementations in a real test-bed, Experimental results show that the performance of the proposed algorithms outperform their counterparts by at least 10 percent. [ABSTRACT FROM AUTHOR]

It is necessary for reliability and yield to minimize the number of used vias on nets in printed circuit board (PCB) designs. To our knowledge, the proposed fuzzy-clustering-based algorithm is the first work for a general routing region with multiple-pin nets in k-layer circular topological via minimization (k-CTVM). In this article, given the topological connections in a set of routing nets and a set of k available layers in a routing plane, first, all the multipin nets can be transformed into a set of two-pin nets by introducing a set of preassigned vias onto the branch points on multipin nets and a conflict graph can be constructed for a final set of two-pin nets. Furthermore, the probabilistic similarity between two connected vertices using the same color can be computed for the constrained vertex-coloring problem with k colors in a conflict graph. Next, based on the definition of the clustering distance between two connected vertices in a conflict graph, fuzzy graph clustering can be developed to obtain a fuzzy matrix on k clusters. Finally, all the given nets can be assigned onto the k available layers by introducing a set of necessary vias on two-pin nets and eliminating the unnecessary preassigned vias on multipin nets. Compared with the combination of Cong's algorithm and an iterative net postassignment, NetInsertion1, in the k-CTVM problem, the experimental results show that our proposed fuzzy-clustering- based algorithm can use less CPU time to reduce 57.3% of the number of the total used vias for eight tested PCB designs. Compared with the combination of Yan's algorithm and an iterative net postassignment, NetInsertion2, in the k-CTVM problem, the experimental results show that our proposed fuzzy-clustering-based algorithm can reduce 34.0% of the number of the total used vias for eight tested PCB designs. [ABSTRACT FROM AUTHOR]

Fuzzy testing is the most effective method for vulnerability mining, which can deal with complex programmes better than other vulnerability mining techniques and has strong scalability. However, in the large-scale vulnerability analysis test, the fuzzy test input sample set faces the challenges of low quality, high repeatability and low availability etc. Therefore, this paper studies the input sample set and proposes heuristic genetic algorithm. By using 0–1 matrix, the genetic algorithm is improved with a consideration of practical problems and the execution path for sample set is selected and compressed through approximation algorithm, thus obtaining a smallest sample set and accelerating the efficiency of fuzzy test. Experimental results show that the proposed method is effective. [ABSTRACT FROM AUTHOR]

In opportunistic mobile crowdsensing, the objective of service requesters is to have as many of their sensing tasks completed as possible within their budget constraints, whereas that of participants (workers) is to collect the highest monetary reward possible on their trajectories. However, these objectives can conflict and may result in unhappy service requesters or workers if the matching between them is not handled carefully. In this paper, we study the problem of finding task assignments that fulfill both coverage-aware preferences of service requesters and profit-based preferences of workers in a budget-constrained, opportunistic mobile crowdsensing system. Since this is a matching problem with bilateral preferences, we aim to find a matching in which everyone is satisfied with their assignment based on their preference profile. We first propose a polynomial-time approximation algorithm for general settings, and then show that a slightly modified version of this algorithm has a constant approximation ratio when the rewards offered to workers by service requesters are proportional to the coverage capability of workers for corresponding tasks. Through extensive simulations, we evaluate the performance of our algorithms in different settings, and show that they mostly provide substantially better task assignments in terms of user happiness and coverage quality while having a few orders of magnitude lower running times compared to the benchmark algorithms. [ABSTRACT FROM AUTHOR]

This paper revisits the classical problem of multiple query optimization in federated RDF systems. We propose a heuristic query rewriting-based approach to optimize the evaluation of multiple queries. This approach can take advantage of SPARQL 1.1 to share the common computation of multiple queries while considering the cost of both query evaluation and data shipment. Although we prove that finding the optimal rewriting for multiple queries is NP-complete, we propose a heuristic rewriting algorithm with a bounded approximation ratio. Furthermore, we propose an efficient method to use the interconnection topology between RDF sources to filter out irrelevant sources, and utilize some characteristics of SPARQL 1.1 to optimize multiple joins of intermediate matches. The extensive experimental studies show that the proposed techniques are effective, efficient and scalable. [ABSTRACT FROM AUTHOR]

Nonlinear optimization problems with dynamical parameters are widely arising in many practical scientific and engineering applications, and various computational models are presented for solving them under the hypothesis of short-time invariance. To eliminate the large lagging error in the solution of the inherently dynamic nonlinear optimization problem, the only way is to estimate the future unknown information by using the present and previous data during the solving process, which is termed the future dynamic nonlinear optimization (FDNO) problem. In this paper, to suppress noises and improve the accuracy in solving FDNO problems, a novel noise-tolerant neural (NTN) algorithm based on zeroing neural dynamics is proposed and investigated. In addition, for reducing algorithm complexity, the quasi-Newton Broyden–Fletcher–Goldfarb–Shanno (BFGS) method is employed to eliminate the intensively computational burden for matrix inversion, termed NTN-BFGS algorithm. Moreover, theoretical analyses are conducted, which show that the proposed algorithms are able to globally converge to a tiny error bound with or without the pollution of noises. Finally, numerical experiments are conducted to validate the superiority of the proposed NTN and NTN-BFGS algorithms for the online solution of FDNO problems. [ABSTRACT FROM AUTHOR]

Tucker decomposition is a standard method for processing multi-way (tensor) measurements and finds many applications in machine learning and data mining, among other fields. When tensor measurements arrive in a streaming fashion or are too many to jointly decompose, incremental Tucker analysis is preferred. In addition, dynamic adaptation of bases is desired when the nominal data subspaces change. At the same time, it has been documented that outliers in the data can significantly compromise the performance of existing methods for dynamic Tucker analysis. In this work, we present Dynamic L1-Tucker: an algorithm for dynamic and outlier-resistant Tucker analysis of tensor data. Our experimental studies on both real and synthetic datasets corroborate that the proposed method (i) attains high bases estimation performance, (ii) identifies/rejects outliers, and (iii) adapts to changes of the nominal subspaces. [ABSTRACT FROM AUTHOR]

FIR filters have boosted the development of digital signal processing, beamformers, and so on, due to their stability and low coefficient sensitivity. Generally, the design of FIR filters follows two main principles, i.e., the specification on the response error and the low implementation complexity. In this brief, we describe the sparsity of the filter coefficients using the k-maximum function, which equals to ℓ0-norm under mild conditions and has no restriction on the magnitude of nonzero coefficients. In order to avoid possible violation of specifications on response errors caused by frequency discretization, we estimate the frequencies at which the magnitude of the response error is maximized when constructing linear problems in the proposed algorithm. To address the nonlinearity and nonconvexity of the resulted optimization problem, we transform it into a piecewise linear concave optimization (PLCO) problem. Considering the fact that a PLCO problems is reduced to a linear programming (LP) problem locally, we outline an iterative algorithm by solving a series of LP problems and provide a brief complexity analysis. Numerical experiments on the propose method and some state-of-the-art methods are performed, the result of which shows the excellent performance of the propose method on balancing the sparsity and computational efficiency. [ABSTRACT FROM AUTHOR]

Scheduling sensor activity to prolong the network lifetime while guaranteeing coverage and connectivity is a fundamental and critical issue in handling wireless sensor networks. Although many efforts have been made in this area, none of the prior works considers the relay hop bound constraint. As a result, the existing scheduling algorithms can provide only connectivity with uncontrollable latency to the sinks and can’t be applied to delay-sensitive applications. In this paper, we are the first one coping with the scheduling problem for network lifetime maximization under the requirements of full target coverage and connectivity with bounded relay hop. We first propose an exact LP (i.e., Linear Programming) formulation to determine the optimal solution. Then, to reduce the time complexity, we develop a ${\left ({1+\epsilon }\right)}^{2}$ -approximation algorithm based on the partitioning and shifting technique. Furthermore, we propose an approximate LP formulation whose variable size is polynomial to the number of targets and sensors and whose performance ratio is $\widehat {M}$ , where $\widehat {M}$ is the maximum number of targets covered by a sensor. The experiment results show that when the number of sensors is sufficiently large, our algorithms extend the network lifetime up to 3.68 times compared to the existing approaches. Moreover, the proposed algorithms shorten time complexity significantly. Specifically, our algorithms’ time complexity is always less than 20% that of the benchmarks. [ABSTRACT FROM AUTHOR]

In Network Function Virtualization (NFV), a multicast data flow must be traversed through a Service Function Chain (SFC) that is a predefined sequence of Virtual Network Functions (VNFs). In this letter, we formulate the problem of optimal embedding of NFV-Enabled multicast service chains as a mixed binary linear program. Then to solve the problem in a reasonable time, we use the penalty-based successive upper bound minimization algorithm. Also, a heuristic solution based on the decomposition of the problem into smaller sub-problems that can be solved iteratively and sequentially, is proposed. Simulation results demonstrate the effectiveness of the proposed solution methods. [ABSTRACT FROM AUTHOR]

Recently, many video-on-demand (VoD) providers have begun storing multiple versions of the same video to offer multiple-quality video services with different bitrates to users, called multi-version VoD. To improve users’ quality of experience (QoE), it is a good idea to cache videos at edge servers in multi-version VoD systems. However, determining which versions of which videos should be cached or replaced in an edge server is still a major challenge for a multi-version VoD system because of its limited cache storage. In this paper, we propose a popularity-based and version-aware caching scheme (PVCS) at edge servers for multi-version VoD systems. First, based on video popularity, we formulate cache placement as a knapsack problem under constraints such as the cache storage and transcoding computation of the edge server, which aims to maximize the cache hit ratio. Second, we use the transcoding relations among versions to calculate a version-aware caching profit when caching a certain version or multiple versions of a video. The version-aware caching profit is the basis for the subsequent cache replacement algorithm. Third, we propose two algorithms, the video cache placement (VCP) algorithm and the video cache replacement (VCrP) algorithm, to solve the cache placement and replacement problems respectively. VCP utilizes the Lagrangian relaxation algorithm to decide which video files should be cached initially, and VCrP decides which video files cached at the edge server will be replaced dynamically based on the version-aware profit. In this way, the PVCS can improve the cache hit ratio and decrease the average start-up delay. Our simulation results have shown that the PVCS outperforms the other schemes in terms of the cache hit ratio and the average start-up delay. [ABSTRACT FROM AUTHOR]

This article presents a hysteretic-current-controlled buck converter with constant-frequency-controlled and active-current-sensing (ACS) techniques. This converter used phase–frequency-locked techniques to achieve constant switching frequency. Even if the input voltage or output load current changes, the switching frequency will be as stable as possible at 1 MHz. The proposed ACS circuit will not generate sparks, so the current feedback loop does not need a sample-and-hold circuit, and that will reduce the transient response time. The proposed buck converter has been fabricated with TSMC 0.35 μm CMOS 2P4M technology; the total area of the chip is 1.5 mm × 1.5 mm. The measurement results of this buck converter show that the maximum power efficiency is 90% when the output voltage is 2.5 V and the load current is 300 mA. The output voltage range is 2.5–1 V, and the maximum load current is 600 mA. When the load current varies between 100 and 500 mA, the load transient response is 2.6 μs/2.2 μs and undershoot/overshoot is 20 mV/30 mV. The switching frequency of this buck converter is locked at 1 MHz and the voltage error is within 1%. [ABSTRACT FROM AUTHOR]

The energy consumption of the nodes is limited in wireless sensor networks (WSNs). Since the sink node takes up most of the data forwarding, the energy consumption is maximum and it is easily formed around the energy hole. The network lifetime is short; so how to improve the network effective node energy and prolong the network lifetime have become a hot issue in the application of WSNs. In this article, our aim is to construct an optimal spanning tree of maximum lifetime as a research object. We propose a kind of accurately distributed data gathering algorithm-based tree. Compared with the existing local minimum spanning tree (LMST) distributed algorithm and random routing algorithm, our proposed constructing method based on spanning tree can prolong the lifetime of WSNs. [ABSTRACT FROM AUTHOR]

This article considers the problem of resource sharing in a virtual mobile network with energy-harvesting base stations (BSs), where several virtual mobile operators (VMOs) lease radio resources (e.g., radio channels and green BSs) from a mobile network owner (MNO). The VMOs want to provide subscribed users with the best performance while ensuring minimal leasing costs. We aim to find the optimal resource leasing scheme for a VMO in order to maximize utility within the uncertainties of harvested energy, request arrivals, and resource prices. We first formulate the problem as a Markov decision process, during which the VMOs compete with each other for the radio resources by dynamically announcing their resource requirements to the MNO. We, then, employ a deep Q-learning algorithm so the VMO can find the optimal solution by interacting with the environment. With this algorithm, artificial neural networks are used to approximate the Q-value function, which can work effectively with large state and action spaces. We further employ the idea of transfer learning, which exploits the strategies learned in historical periods to speed up the learning process of the target task. Finally, we present comprehensive simulations to evaluate the performance of the proposed scheme under various configurations. [ABSTRACT FROM AUTHOR]

A Service Function Chain (SFC) is an ordered sequence of network functions (NFs). With the emerging Network Function Virtualization (NFV) paradigm, NFs can be deployed as software instances on commodity servers, leading to a more flexible provision of network service. However, the flexibility of NFV comes with considerable compromises since virtual network functions (VNFs) introduce significant processing latency overheads. In this article, we design a flexible SFC parallel system called FlexChain, enabling the parallelism among VNFs to reduce the processing latency of SFCs. To leverage the benefits of parallelism, we study the problem of joint optimization over SFC parallelism and placement with the objective of accepting as many requests as possible. Since the problem is proved to be NP-hard, we propose a parallelism-aware approximation placement algorithm with performance guarantees, and an efficient heuristic algorithm for large-scale data center networks. Our simulation results show that FlexChain combined with our placement algorithm can substantially improve the number of accepted flows in the latency-sensitive scenario, and significantly reduce the average latency of accepted flows at the same time. [ABSTRACT FROM AUTHOR]

Coflow is a network abstraction used to represent communication patterns in data centers. The coflow scheduling problem encountered in large data centers is a challenging NP -hard problem. Many previous studies on coflow scheduling mainly focus on the single-core model. However, with the growth of data centers, this single-core model is no longer sufficient. This paper addresses the coflow scheduling problem within heterogeneous parallel networks, which feature an architecture consisting of multiple network cores running in parallel. In this paper, two polynomial-time approximation algorithms are developed for the flow-level scheduling problem and the coflow-level scheduling problem in heterogeneous parallel networks, respectively. For the flow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O (log ⁡ m / log ⁡ log ⁡ m) when all coflows are released at arbitrary times, where m represents the number of network cores. On the other hand, in the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O (m (log ⁡ m / log ⁡ log ⁡ m) 2) when all coflows are released at arbitrary times. Moreover, we propose a heuristic algorithm for the flow-level scheduling problem. Simulation results using synthetic traffic traces validate the performance of our algorithms and show improvements over the previous algorithm. • Algorithm achieves O (log ⁡ m / log ⁡ log ⁡ m) approximation ratio for flow-level scheduling, where m is network cores. • For coflow-level scheduling, algorithm achieves O (m (log ⁡ m / log ⁡ log ⁡ m) 2) approximation ratio. • Moreover, this paper proposes a heuristic algorithm for the flow-level scheduling problem. [ABSTRACT FROM AUTHOR]

X-ray Computed Tomography (CT) is widely used in clinical applications such as diagnosis and image-guided interventions. In this paper, we propose a new deep learning based model for CT image reconstruction with the backbone network architecture built by unrolling an iterative algorithm. However, unlike the existing strategy to include as many data-adaptive components in the unrolled dynamics model as possible, we find that it is enough to only learn the parts where traditional designs mostly rely on intuitions and experience. More specifically, we propose to learn an initializer for the conjugate gradient (CG) algorithm that involved in one of the subproblems of the backbone model. Other components, such as image priors and hyperparameters, are kept as the original design. Since a hypernetwork is introduced to inference on the initialization of the CG module, it makes the proposed model a certain meta-learning model. Therefore, we shall call the proposed model the meta-inversion network (MetaInv-Net). The proposed MetaInv-Net can be designed with much less trainable parameters while still preserves its superior image reconstruction performance than some state-of-the-art deep models in CT imaging. In simulated and real data experiments, MetaInv-Net performs very well and can be generalized beyond the training setting, i.e., to other scanning settings, noise levels, and data sets. [ABSTRACT FROM AUTHOR]

In this article, a mathematical model of a magnetic-wheeled mobile robot (MWMR) used for wall climbing in some special industrial sites is established, and to realize the precise motion control of the robot, an intelligent discrete algorithm for trajectory tracking control of the MWMR is presented. The robot is subjected to nonholonomic constraints when moving on the wall. The discrete mathematical model of the MWMR is established with the description of the kinematics and dynamics, where the dynamics are described by the second-order Lagrange's equations. Improved dual-heuristic dynamic programming (DHP) where the actor-critic structure adopts random vector functional link neural networks (RVFL NNs) is the main configuration of the trajectory tracking control algorithm. Moreover, the tracking control algorithm is supplied by a PD controller and a supervisory element to generate overall control signals. The improved strategy is to optimize the input layer weights of RVFL NNs by a genetic algorithm to improve the approximation performance of DHP. Simulations are performed to test the trajectory tracking control algorithm for this wall-climbing robot, and the results are compared with those of neural network tracking control algorithm. Comparative analysis verifies the effectiveness and advancement of the proposed method. [ABSTRACT FROM AUTHOR]

The problem of detecting communities is one of the essential problems in the study of social networks. To devise the algorithms of community detection, one should first define high-quality communities. In fact, there are no agreed methods to measure the quality of the community. In this paper, we consider a novel objective function of this problem. Our goal is to maximize not only the average of the sum of edge weights within communities (i.e., average-case) but also the sum of edge weights within the minimum community (i.e., worst-case). To balance both the average-case and worst-case problems, we introduce a parameter into our objective function and call it the mixed-cased community detection problem. For the worst-case, we devise several approximation algorithms, such as the Greedy, Semi-Sandwich Approximation, and Local Search algorithms. For the average-case, an efficient Terminal-based algorithm is proposed. We prove that the best solution between the average-case and worst-case problems still can provide an approximate guarantee for any mixed-case community detection problem. Moreover, we devise a heuristic algorithm for our problem. Finally, we conduct the experiments in three networks. The experimental results indicate that our proposed methods can form a high-quality community partition. • A novel objective function of community detection problem is proposed. • The Greedy, Semi-Sandwich Approximation and Local Search algorithms are devised to solve the worst-case problem. • An efficient Terminal-based algorithm is proposed to solve the average-case problem. • An algorithm with the approximate guarantee is proposed for any mixed-case problem. • The experimental results indicate that our proposed methods can form a high-quality community partition. [ABSTRACT FROM AUTHOR]

Skyline queries are important in many application domains. In this paper, we propose a novel structure Skyline Diagram, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. All query points in the same skyline polyomino have the same skyline query results. Similar to $k$ k th-order Voronoi diagram commonly used to facilitate $k$ k nearest neighbor ($k$ k NN) queries, skyline diagram can be used to facilitate skyline queries and many other applications. However, it may be computationally expensive to build the skyline diagram. By exploiting some interesting properties of skyline, we present several efficient algorithms for building the diagram with respect to three kinds of skyline queries, quadrant, global, and dynamic skylines. In addition, we propose an approximate skyline diagram which can significantly reduce the space cost. Experimental results on both real and synthetic datasets show that our algorithms are efficient and scalable. [ABSTRACT FROM AUTHOR]

This article reviews the recent development of adaptive dynamic programming (ADP) with applications in control. First, its applications in optimal regulation are introduced, and some skilled and efficient algorithms are presented. Next, the use of ADP to solve game problems, mainly nonzero-sum game problems, is elaborated. It is followed by applications in large-scale systems. Note that although the functions presented in this article are based on continuous-time systems, various applications of ADP in discrete-time systems are also analyzed. Moreover, in each section, not only some existing techniques are discussed, but also possible directions for future work are pointed out. Finally, some overall prospects for the future are given, followed by conclusions of this article. Through a comprehensive and complete investigation of its applications in many existing fields, this article fully demonstrates that the ADP intelligent control method is promising in today’s artificial intelligence era. Furthermore, it also plays a significant role in promoting economic and social development. [ABSTRACT FROM AUTHOR]

The IP core mapping optimization problem is an NP-hard problem in network-on-chip design. Because of the computational complexity of an IP core mapping, the MPNN-Ptr networks composed of the graph networks and the pointer networks are proposed to model the IP core mapping. The neural network IP core mapping model (NNMM) can effectively evaluate the probability of each mapping solution as the optimal solution to an IP core mapping optimization problem. Then, an IP core mapping algorithm, the neural mapping algorithm (NMA), is proposed. In this algorithm, the global search is realized by sampling the mapping solutions with a high probability evaluated by NNMM. The sampled candidate mapping solutions according to probability can effectively decrease the candidate mapping solution space, which can reduce invalid searches and avoid getting stuck at local minima. Then, the 2-opt algorithm is used as a local search to improve the quality of mapping further. Simulation results show that the MPNN-Ptr networks can effectively model the IP core mapping. Compared with the state-of-the-art mapping algorithms, NMA produces better solutions for both specific applications and random applications. NMA achieves a 7.90% communication cost reduction on average than the classic mapping algorithm: NMAP. [ABSTRACT FROM AUTHOR]

We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall Age of Information (AoI). We call this problem the Min-AoI problem. Several special cases of the problem are known to be solvable in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant ${r} \geq 1$ , every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-AoI problem. Second, we give a randomized 2.619-approximation algorithm, a randomized 3-approximation algorithm, which outperforms the previous one in certain scenarios, and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-AoI problem is NP-hard. [ABSTRACT FROM AUTHOR]

Deferred-acceptance auctions can be seen as heuristic algorithms to solve N P -hard allocation problems. Such auctions have been used in the context of the Incentive Auction by the US Federal Communications Commission in 2017, and they have remarkable incentive properties. Besides being strategyproof, they also prevent collusion among participants. Unfortunately, the worst-case approximation ratio of these algorithms is very low in general, but it was observed that they lead to near-optimal solutions in experiments on the specific allocation problem of the Incentive Auction. In this work, which is inspired by the telecommunications industry, we focus on a strategic version of the minimum Steiner tree problem, where the edges are owned by bidders with private costs. We design several deferred-acceptance auctions (DAAs) and compare their performance to the Vickrey–Clarke–Groves (VCG) mechanism as well as several other approximation mechanisms. We observe that, even for medium-sized inputs, the VCG mechanisms experiences impractical runtimes and that the DAAs match the approximation ratios of even the best strategy-proof mechanisms in the average case. We thus provide another example of an important practical mechanism design problem, where empirics suggest that carefully designed deferred-acceptance auctions with their superior incentive properties need not come at a cost in terms of allocative efficiency. Our experiments provide insights into the trade-off between solution quality and runtime and into the additional premium to be paid in DAAs to gain weak group-strategyproofness rather than just strategyproofness. [ABSTRACT FROM AUTHOR]

Hybrid optical/electrical datacenter networks (HOE-DCNs) build inter-rack networks with both electrical Ethernet switches and optical cross-connects (OXCs), and have been considered as a promising DCN architecture. However, to adapt to the dynamic network environment, the reconfiguration of virtual networks (VNTs) in an HOE-DCN still faces the unique difficulty that the HOE-DCN's topology can change because of the one-to-one connectivity of OXCs. To the best of our knowledge, this problem still has not been fully explored. In this article, we address this problem, and consider how to achieve effective VNT reconfiguration in an HOE-DCN such that the IT resource usages in racks can be re-balanced with the migration of virtual machines (VMs). We first formulate a mixed integer linear programming (MILP) to describe the VNT reconfiguration. Then, we solve the problem with two steps, 1) obtaining the VM migration schemes to balance the loads on racks and 2) determining the reconfiguration schemes of related virtual links (VLs) and the OXC. For the first step, we propose a polynomial-time approximation algorithm by leveraging linear relaxation. Then, we tackle the optimization of the second step by developing an algorithm that involves a linear-time dynamic programming and an integer linear programming (ILP). To solve the ILP time-efficiently, we propose another polynomial-time approximation algorithm based on Lagrangian relaxation. Our simulations confirm the effectiveness of the proposed approximation algorithms and verify that the overall procedure including them outperforms the existing approach. [ABSTRACT FROM AUTHOR]

In network function virtualization, a service function chain (SFC) specifies a sequence of virtual network functions that user traffic has to traverse to realize a network service. The problem of SFC orchestration has been extensively studied in the literature. However, most existing works assume deterministic demands and resort to costly runtime resource reprovisioning to deal with dynamic demands. In this work, we formulate the deadline-aware co-located and geo-distributed SFC orchestration with demand uncertainty as robust optimization problems and develop exact and approximate algorithms to solve them. A key feature of our formulation is the consideration of end-to-end delay in service chains by carefully modeling load-independent propagation delay as well as load-dependent queueing and processing delays. To avoid frequent resource reprovisioning, our algorithms utilize uncertain demand knowledge to compute proactive SFC orchestrations that can withstand fluctuations in dynamic service demands. Extensive simulations are conducted to evaluate the performance of our algorithms in terms of ability to cope with demand fluctuations, scalability, and relative performance against other recent algorithms. [ABSTRACT FROM AUTHOR]

Most of existing virtual network embedding (VNE) algorithms only consider how to construct virtual networks more efficiently on a physical infrastructure, without considering the possibility that the constructed virtual networks may be further virtualized to multiple smaller ones. We define the former scenario as single-layer VNE and the later as multi-layer VNE. As the increasing popularity of deploying large datacenter networks and wide area networks with Software Defined Network (SDN) architectures, it becomes a new requirement and possibility to provide multi-layer encapsulated network services for large tenants who have hierarchical organizational structures or need fine-grained service isolation. However, existing VNE algorithm are not specifically designed for the above requirement and not flexible enough to deal with mapping virtual network requirements (VNRs) to a physical network and smaller VNRs to a mapped virtual network. In this paper, we aim to propose a unified and flexible multi-layer VNE algorithm combining with reinforcement learning to solve the embedding of multi-layer VNRs, which can better distinguish the differences between VNRs and physical networks. Simulation results show that our algorithm achieves good performance both in single-layer and multi-layer VNE scenarios. [ABSTRACT FROM AUTHOR]

This article investigates the cache-enabling unmanned aerial vehicle (UAV) cellular networks with massive access capability supported by non-orthogonal multiple access (NOMA). The delivery of a large volume of multimedia contents for ground users is assisted by a mobile UAV base station, which caches some popular contents for wireless backhaul link traffic offloading. In cache-enabling UAV NOMA networks, the caching placement of content caching phase and radio resource allocation of content delivery phase are crucial for network performance. To cope with the dynamic UAV locations and content requests in practical scenarios, we formulate the long-term caching placement and resource allocation optimization problem for content delivery delay minimization as a Markov decision process (MDP). The UAV acts as an agent to take actions for caching placement and resource allocation, which includes the user scheduling of content requests and the power allocation of NOMA users. In order to tackle the MDP, we propose a Q-learning based caching placement and resource allocation algorithm, where the UAV learns and selects action with soft ε-greedy strategy to search for the optimal match between actions and states. Since the action-state table size of Q-learning grows with the number of states in the dynamic networks, we propose a function approximation based algorithm with combination of stochastic gradient descent and deep neural networks, which is suitable for large-scale networks. Finally, the numerical results show that the proposed algorithms provide considerable performance compared to benchmark algorithms, and obtain a trade-off between network performance and calculation complexity. [ABSTRACT FROM AUTHOR]

Nearest neighbor searching systems are an integral part of many online applications, including but not limited to pattern recognition, plagiarism detection, and recommender systems. With increasingly larger data sets, scalability has become an important issue. Many of the most space and running time efficient algorithms are based on locality-sensitive hashing. Here, we view the data set as an $n$ n by $|U|$ | U | matrix where each row corresponds to one of $n$ n users and the columns correspond to items drawn from a universe $U$ U . The de-facto standard approach to quickly answer nearest neighbor queries on such a data set is usually a form of min-hashing. Not only is min-hashing very fast, but it is also space efficient and can be implemented in many computational models aimed at dealing with large data sets such as MapReduce and streaming. However, a significant drawback is that minhashing and related methods are only able to handle insertions to user profiles and tend to perform poorly when items may be removed. We initiate the study of scalable locality-sensitive hashing (LSH) for fully dynamic data-streams. Specifically, using the Jaccard index as similarity measure, we design (1) a collaborative filtering mechanism maintainable in dynamic data streams and (2) a sketching algorithm for similarity estimation. Our algorithms have little overhead in terms of running time compared to previous LSH approaches for the insertion only case, and drastically outperform previous algorithms in case of deletions. [ABSTRACT FROM AUTHOR]

Reachability analysis aims at identifying states reachable by a system within a given time horizon. This task is known to be computationally expensive for linear hybrid systems. Reachability analysis works by iteratively applying continuous and discrete post operators to compute states reachable according to continuous and discrete dynamics, respectively. In this article, we enhance both of these operators and make sure that most of the involved computations are performed in low-dimensional state space. In particular, we improve the continuous-post operator by performing computations in high-dimensional state space only for time intervals relevant for the subsequent application of the discrete-post operator. Furthermore, the new discrete-post operator performs low-dimensional computations by leveraging the structure of the guard and assignment of a considered transition. We illustrate the potential of our approach on a number of challenging benchmarks. [ABSTRACT FROM AUTHOR]

This article presents a novel event-driven guaranteed cost control method for nonlinear systems subject to actuator faults. For the purpose of handling the problem of actuator faults and obtaining the event-driven approximate optimal guaranteed cost control approach for general nonlinear dynamics, the reinforcement learning (RL) algorithm is utilized to develop a sliding-mode control (SMC) strategy. To begin with, the unknown faults can be estimated by designing a fault observer. Meanwhile, an SMC technique is presented aiming at countering the effect of abrupt faults. In addition, the optimal performance of the equivalent sliding mode dynamics is considered, then an event-driven guaranteed cost control mechanism is implemented by using RL principle. In the control process, a general cost function, which has a simpler structure, is given to reduce the computation complexity. At the same time, a modified cost function is approximated to obtain optimal guaranteed cost control by using a single critic neural network (NN). In addition, a modified weight update law for critic NN is presented to relax the persistence of excitation (PE) condition. Moreover, a newly triggering condition, which is easy to be implemented, is designed, and the critic NN update law makes sure that the system states are stable. Furthermore, in light of the Lyapunov analysis, it is demonstrated that the developed event-driven control method guarantees the uniformly ultimately bounded (UUB) property of all the signals. Finally, three simulation results are given to validate the designed control method. [ABSTRACT FROM AUTHOR]

In this paper, a novel adaptive dynamic programming (ADP) algorithm is developed for the infinite-horizon ($H_{\infty}$) optimal control problems with unknown continuous-time (CT) nonlinear systems subject to external disturbances. To facilitate the implementation of the algorithm, generalized fuzzy hyperbolic models (GFHMs) are utilized to establish an identifier–critic architecture, where the identifier is designed to reconstruct the unknown system dynamics, and the GFHM-based critic network is employed to approximate the value functions. The CT $H_{\infty}$ optimal control issue is converted into a two-player zero-sum game and the corresponding Hamilton–Jacobi–Isaacs equation is derived. The learning procedure of the critic design is adaptively implemented with the help of the reconstructed model, thus the requirement of the complete system dynamics is relaxed. Furthermore, by the means of Lyapunov direct method, the uniform ultimate boundedness stability analysis of the closed-loop control system is explicitly provided. Finally, to compare the control performances and disturbance attenuation properties of the proposed method and the existing ADP algorithms, two numerical examples are given. [ABSTRACT FROM AUTHOR]

Along with Network Function Virtualization (NFV), Mobile Edge Computing (MEC) is becoming a new computing paradigm that enables accommodating innovative applications and services with stringent response delay and resource requirements, including autonomous vehicles and augmented reality. Provisioning reliable network services for users is the top priority of most network service providers, as unreliable services or severe service failures can result in tremendous losses of users, particularly for their mission-critical applications. In this paper, we study reliability-aware VNF instances provisioning in an MEC, where different users request different network services with different reliability requirements through paying their requested services with the aim to maximize the network throughput. To this end, we first formulate a novel reliability-aware VNF instance placement problem by provisioning primary and secondary VNF instances at different cloudlets in MEC for each user while meeting the specified reliability requirement of the user request. We then show that the problem is NP-hard and formulate an Integer Linear Programming (ILP) solution. Due to the NP-hardness of the problem, we instead devise an approximation algorithm with a logarithmic approximation ratio for the problem. Moreover, we also consider two special cases of the problem. For one special case where each request only requests one primary and one secondary VNF instances, the problem is still NP-hard, and we devise a constant approximation algorithm for it. For another special case where different VNFs have the same amounts of computing resource demands, we show that it is polynomial-time solvable by developing a dynamic programming solution for it. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and the empirical results of the algorithms outperform their analytical counterparts as theoretical estimations usually are very conservative. [ABSTRACT FROM AUTHOR]

Optimization underpins many of the challenges that science and technology face on a daily basis. Recent years have witnessed a major shift from traditional optimization paradigms grounded on batch algorithms for medium-scale problems to challenging dynamic, time-varying, and even huge-size settings. This is driven by technological transformations that converted infrastructural and social platforms into complex and dynamic networked systems with even pervasive sensing and computing capabilities. This article reviews a broad class of state-of-the-art algorithms for time-varying optimization, with an eye to performing both algorithmic development and performance analysis. It offers a comprehensive overview of available tools and methods and unveils open challenges in application domains of broad range of interest. The real-world examples presented include smart power systems, robotics, machine learning, and data analytics, highlighting domain-specific issues and solutions. The ultimate goal is to exemplify wide engineering relevance of analytical tools and pertinent theoretical foundations. [ABSTRACT FROM AUTHOR]