Search

This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks. [ABSTRACT FROM AUTHOR]

Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for relevant computational problems over graphs. However, such methods have some drawbacks: (1) they use the same neural architecture for different combinatorial problems without introducing customizations that reflects the specificity of each problem; (2) they only use a nodes local information to compute the solution; (3) they do not take advantage of common heuristics or exact algorithms. Following this interest, in this research we address these three main points by designing a customized attention-based mechanism that uses both local and global information from the adjacency matrix to find approximate solutions for the Minimum Vertex Cover Problem. We evaluate our proposal with respect to a fast two-factor approximation algorithm and a widely adopted state-of-the-art heuristic both on synthetically generated instances and on benchmark graphs with different scales. Experimental results demonstrate that, on the one hand, the proposed methodology is able to outperform both the two-factor approximation algorithm and the heuristic on the test datasets, scaling even better than the heuristic with harder instances and, on the other hand, is able to provide a representation of the nodes which reflects the combinatorial structure of the problem. [ABSTRACT FROM AUTHOR]

Identifying shortest paths between nodes in a network is a common graph analysis problem that is important for many applications involving routing of resources. An adversary that can manipulate the graph structure could alter traffic patterns to gain some benefit (e.g., make more money by directing traffic to a toll road). This article presents the Force Path Cut problem, in which an adversary removes edges from a graph to make a particular path the shortest between its terminal nodes. We prove that the optimization version of this problem is APX-hard but introduce PATHATTACK, a polynomial-time approximation algorithm that guarantees a solution within a logarithmic factor of the optimal value. In addition, we introduce the Force Edge Cut and Force Node Cut problems, in which the adversary targets a particular edge or node, respectively, rather than an entire path. We derive a nonconvex optimization formulation for these problems and derive a heuristic algorithm that uses PATHATTACK as a subroutine. We demonstrate all of these algorithms on a diverse set of real and synthetic networks, illustrating where the proposed algorithms provide the greatest improvement over baseline methods. [ABSTRACT FROM AUTHOR]

Over the past few decades, there has been a significant increase in the number of Earth observation satellites, and the area of ground targets requiring observation has also been expanding. To effectively utilize the capabilities of these satellites and capture larger areas of ground targets, it has become essential to plan imaging tasks for large regional coverage using multiple satellites. First, we establish a 0-1 integer programming model to accurately describe the problem and analyze the challenges associated with solving the model. Second, we propose a heuristic algorithm based on the triple grids method. This approach utilizes a generated grid to create fewer candidate strips, a calculation grid to determine the effective coverage area more accurately, and a refined grid to solve the issue of repeated coverage of strips. Furthermore, we employ an approximation algorithm to further improve the solutions obtained from the heuristic algorithm. By comparing the proposed method to the traditional greedy heuristic algorithm and three evolutionary algorithms, the results show that our method has better performance in terms of coverage and efficiency. [ABSTRACT FROM AUTHOR]

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 − 4 / k) and a polynomial running time for any fixed constant k ≥ 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k ≥ 2 being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193. The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0193) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0193). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Patient unpunctuality significantly disrupts the operations of healthcare facilities, reduces provider productivity, and increases healthcare costs. To alleviate the negative impact of unpunctual patients, this study addresses the appointment scheduling (AS) in the simultaneous presence of unpunctual patients, multiple servers, and no-shows. To determine the appointment schedule, we propose a two-stage stochastic mixed-integer programming model to minimise the total cost incurred by patient waiting and clinic overtime. It becomes challenging for a standard solver to solve this model due to the dynamic patient-to-server assignment decisions that are proactively anticipated in the determination of appointment times. To deal with this problem, a stochastic approximation algorithm is proposed under unbiased gradient estimators. The effectiveness and efficiency of this algorithm are validated in extensive numerical experiments that compare it with Benders decomposition and a heuristic algorithm. Further, the features of the optimal appointment schedule are analysed: (i) the shape of the appointment intervals relies on the number of servers; (ii) the length of intervals is sensitive to no-shows; (iii) the initial block size is greatly affected by patient unpunctuality. Managerial insights are also provided for hospital managers to schedule unpunctual patients in practice. [ABSTRACT FROM AUTHOR]

The influence are not linked to any footnote in the text. Please check and suggest. maximization problem aims at selecting the k most influential nodes (i.e., seed nodes) from a social network, where the nodes can maximize the number of influenced nodes activated by a certain propagation model. However, the widely used Independent Cascade model shares the same propagation probability among substantial adjacent node pairs, which is too idealistic and unreasonable in practice. In addition, most heuristic algorithms for influence maximization need to update the expected influence of the remaining nodes in the seed selection process, resulting in high computation cost. To address these non-trivial problems, we propose a novel edge propagation probability calculation method. The method first utilizes the triadic closure structure of social networks to precisely measure the closeness between nodes and assigns different propagation probabilities to each edge, deriving a Triadic Closure-based Independent Cascade (TC-IC) model. Then, we further propose a heuristic influence maximization algorithm named Triadic Closure-based Influence Maximization (TC-IM). The algorithm evaluates the expected influence of a node by integrating the triadic closure weighted propagation probability and the triadic closure weighted degree. Especially, in the seed selection process, only the most influential node that has not been updated in the current round needs to be updated, which significantly improves the efficiency. Besides, we further provide theoretical proofs to guarantee the correctness of this updating strategy. Experimental results on nine real datasets and three propagation models demonstrate that: (1) The TC-IC model can set a proper propagation probability for each node pair, where the IM algorithms could easily identify influential nodes; (2) The TC-IM algorithm can significantly reduce the complexity through an efficient updating strategy with a comparable influence spread to the approximation IM algorithms; (3) Besides, the TC-IM algorithm also exhibits stable performance under other IC models including UIC and WIC, exhibiting good stability and generality. [ABSTRACT FROM AUTHOR]

The travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and scheduling. Route optimisation not only improves the overall profitability of a logistic centre but also reduces greenhouse gas emissions by minimising the distance travelled. In this article, we propose a simple and improved heuristic algorithm named 2-Opt++, which solves symmetric TSP problems using an enhanced 2-Opt local search technique, to generate better results. As with 2-Opt, our proposed method can also be applied to the Vehicle Routing Problem (VRP), with minor modifications. We have compared our technique with six existing algorithms, namely ruin and recreate, nearest neighbour, genetic algorithm, simulated annealing, Tabu search, and ant colony optimisation. Furthermore, to allow for the complexity of larger TSP instances, we have used a graph compression/candidate list technique that helps in reducing the computational complexity and time. The comprehensive empirical evaluation carried out for this research work shows the efficacy of the 2-Opt++ algorithm as it outperforms the other well-known algorithms in terms of the error margin, execution time, and time of convergence. [ABSTRACT FROM AUTHOR]

Clustering is one of the most important problems in the fields of data mining, machine learning, and biological population division, etc. Moreover, robust variant for k -means problem, which includes k -means with penalties and k -means with outliers, is also an active research branch. Most of these problems are NP-hard even the most classical problem, k -means problem. For the NP-hard problems, the heuristic algorithm is a powerful method. When the quality of the output can be guaranteed, the algorithm is called an approximation algorithm. In this paper, combining two types of robust settings, we consider k -means problem with penalties and outliers (k -MPO). In the k -MPO, we are given an n -point set U ⊂ ℝ d , a penalty cost p v ≥ 0 for each v ∈ U , an integer k ≤ n , and an integer z ≤ n. The target is to find a center subset S ⊆ ℝ d with | S | ≤ k , a penalty subset P ⊆ U and an outlier subset Z ⊆ U with | Z | ≤ z , such that the sum of the total costs, including the connection cost and the penalty cost, is minimized. We offer an approximation algorithm using a heuristic local search scheme. Based on a single-swap manipulation, we obtain 2 7 4 -approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper deals with an analysis of three algorithms for the graph vertex cover problem. Certain methods for solving this problem are analyzed. In addition, different studies on the problem and some approaches to its solution are discussed as well. An exact algorithm (based on the backtracking approach) is presented. Calculating the average time for execution of this algorithm is consistent with the multitasking way of work of the operating system. For this purpose, four different starts of the algorithm are made and then the average time of all of them is calculated. The exact algorithm found the optimal solutions for all analyzed graphs. Besides this algorithm, two other heuristic algorithms for solving the problem are discussed. For this study, an interactive application is developed to visualize the performance of the three algorithms and display the obtained results. The results show that for small graphs with no more than 25 vertices, the exact algorithm can be used to solve optimally the graph vertex cover problem. For the largest graphs, none of the two heuristic algorithms found the optimal solutions, but these algorithms generated solutions that are very close to the optimal ones. In summary, when the size of the graph increases linearly, the execution time of the heuristic algorithms increases linearly, while the execution time of the exact algorithm increases exponentially. [ABSTRACT FROM AUTHOR]

This article deals with nonconvex stochastic optimization problems in deep learning. Appropriate learning rates, based on theory, for adaptive-learning-rate optimization algorithms (e.g., Adam and AMSGrad) to approximate the stationary points of such problems are provided. These rates are shown to allow faster convergence than previously reported for these algorithms. Specifically, the algorithms are examined in numerical experiments on text and image classification and are shown in experiments to perform better with constant learning rates than algorithms using diminishing learning rates. [ABSTRACT FROM AUTHOR]

This article proposes robust inverse $Q$ -learning algorithms for a learner to mimic an expert’s states and control inputs in the imitation learning problem. These two agents have different adversarial disturbances. To do the imitation, the learner must reconstruct the unknown expert cost function. The learner only observes the expert’s control inputs and uses inverse $Q$ -learning algorithms to reconstruct the unknown expert cost function. The inverse $Q$ -learning algorithms are robust in that they are independent of the system model and allow for the different cost function parameters and disturbances between two agents. We first propose an offline inverse $Q$ -learning algorithm which consists of two iterative learning loops: 1) an inner $Q$ -learning iteration loop and 2) an outer iteration loop based on inverse optimal control. Then, based on this offline algorithm, we further develop an online inverse $Q$ -learning algorithm such that the learner mimics the expert behaviors online with the real-time observation of the expert control inputs. This online computational method has four functional approximators: a critic approximator, two actor approximators, and a state-reward neural network (NN). It simultaneously approximates the parameters of $Q$ -function and the learner state reward online. Convergence and stability proofs are rigorously studied to guarantee the algorithm performance. [ABSTRACT FROM AUTHOR]

Provisioning reliable network services for mobile users in edge computing environments is the top priority of network service providers, as unreliable services will result in tremendous losses of revenues and customers. In this paper, we study a novel service reliability augmentation problem in a mobile edge computing (MEC) network, where mobile users request network services with service function chain (SFC) and reliability expectation requirements. To enhance the service reliability of user requests, it is a common practice to make use of redundant virtualized network function (VNF) instance placement in case the primary VNF instance fails. We aim to augment the service reliability of each admitted request to its specified reliability expectation, subject to computing capacity on each cloudlet. To this end, we first formulate a novel service reliability augmentation problem for each request with an SFC and a reliability expectation requirement, by augmenting its reliability through redundant VNF instance deployment. We then show that the problem is NP-hard, and provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets. We then deal with the service reliability augmentation problem of an admitted request under the assumption that all secondary VNF instances of each primary VNF instance must be placed into the cloudlets no more than $l$ l hops from the cloudlet of its primary VNF instance for a fixed $l$ l with $1\leq l \leq n-1$ 1 ≤ l ≤ n - 1 , where $n$ n is the number of cloudlets in the network, for which we formulate an integer linear program solution, and develop a randomized algorithm with a good approximation ratio and high probability, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We third study the service reliability augmentation problem for a set of admitted requests by extending the proposed algorithm for the service reliability augmentation problem for a single request admission. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts. [ABSTRACT FROM AUTHOR]

Multi-scale exposure fusion (MEF) is an efficient way to fuse differently exposed low dynamic range (LDR) images of a high dynamic range (HDR) scene into an information enriched LDR image. In this paper, a new MEF algorithm is proposed to merge the differently exposed LDR images by introducing novel content adaptive edge-preserving smoothing (CAS) pyramids for the weight maps of all the LDR images. With the proposed CAS pyramids, details in the brightest and darkest regions of the HDR scene are preserved better than existing MEF algorithms on top of the Gaussian pyramids and edge-preserving smoothing pyramids. Comparisons experimentally demonstrate the effectiveness of the proposed algorithm to nine state-of-the-art MEF algorithms from both subjective and objective points of view regardless the image sizes. [ABSTRACT FROM AUTHOR]

In the phase retrieval problem one seeks to recover an unknown $n$ dimensional signal vector $\mathbf {x}$ from $m$ measurements of the form $y_{i} = |(\mathbf {A} \mathbf {x})_{i}|$ , where $\mathbf {A}$ denotes the sensing matrix. Many algorithms for this problem are based on approximate message passing. For these algorithms, it is known that if the sensing matrix $\mathbf {A}$ is generated by sub-sampling $n$ columns of a uniformly random (i.e., Haar distributed) orthogonal matrix, in the high dimensional asymptotic regime ($m,n \rightarrow \infty, n/m \rightarrow \kappa $), the dynamics of the algorithm are given by a deterministic recursion known as the state evolution. For a special class of linearized message-passing algorithms, we show that the state evolution is universal: it continues to hold even when $\mathbf {A}$ is generated by randomly sub-sampling columns of the Hadamard-Walsh matrix, if the signal is drawn from a Gaussian prior. [ABSTRACT FROM AUTHOR]

This article studies the mean standard deviation (mean-std) Canadian traveller problem (CTP). Different from the canonical CTP, which aims at minimizing the traveller's expected travel time, while considering edge breakdown probabilities, we introduce the reliability version of CTP, which tries to find a routing policy with the minimal linear combination of the travel time's mean and standard deviation. With the recent development of internet-of-things (IoT) technology, the transportation network's edges' travel-time statistics, i.e., mean and standard deviation, as well as the traversal probabilities, are available to the end users. With those information, we propose a dual dynamic programming (DDP) method, which simultaneously estimates the first-order and the second-order moments of a given decision-list (DL) policy, and thereby makes improvements towards to the optimal one through the generalized policy iteration (GPI) scheme. We construct an open source benchmark environment to evaluate the performance of different mean-std CTP solutions, and show that the DDP method outperforms state of the arts in a range of transportation networks. [ABSTRACT FROM AUTHOR]

Subgraph queries are routinely used to search for entities in richly attributed graphs e.g., social networks and knowledge graphs. With little knowledge of underlying data, users often need to rewrite queries multiple times to reach desirable answers. Why-questions are studied to clarify missing or unexpected query results. This paper makes a first step to answer Why-questions for entity search in attributed graphs. We consider three common types of Why-questions: Why-not, Why, and Why-rank, which suggest query manipulations that are responsible for user-specified missing, unexpected, and undesirably ranked entities, respectively. (1) We approach a general query rewriting paradigm that suggests to identify desired entities that are specified by Why-questions. We introduce measures that characterize good query rewrites by incorporating both query editing cost and answer closeness. (2) While computing optimal query rewrites is intractable, we develop feasible algorithms, from approximation to fast heuristics, and provide query rewrites with (near) optimality guarantees whenever possible, for Why, Why-not and Why-rank questions. We further show that our results remain intact for Why questions that (1) request a single query rewrite to clarify multiple types of entities, and (2) variants such as Why-empty and Why-so-many, by providing the matching algorithms. Using real-world graphs, we experimentally verify that our algorithms are effective and feasible for large graphs. Our case study also verifies their application in e.g., knowledge exploration. [ABSTRACT FROM AUTHOR]

Fog networks facilitate ultra-low latency through the use of data availability near the network edge in fog servers. Existing work in fog networks considers the objective of energy efficiency and low latency for internet-of-things (IoT) for resource allocation. These works provide solutions to energy efficiency and low latency resource allocation problem without consideration of secure communication. This article investigates the benefits of fog architecture from the perspective of three promising technologies namely device-to-device (D2D) communication, caching, and physical layer security. We propose security provisioning followed by mode selection for D2D-assisted fog networks. The secrecy rate maximization problem is formulated first, which belongs to mixed-integer nonlinear programming (MINLP) problem. It is NP-hard, that is why an exhaustive search for finding the solution is complex. Keeping in view the complexity, a nonlinear technique namely outer approximation algorithm (OAA) is applied. OAA is a traditional algorithm, whose results are compared with the proposed heuristic algorithm, namely the security heuristic algorithm (SHA). Performance of the network is observed for the different numbers of eavesdroppers, IoT nodes, and fog nodes. [ABSTRACT FROM AUTHOR]

In this article, we discuss a sequential algorithm for the computation of a minimum-time speed profile over a given path, under velocity, acceleration, and jerk constraints. Such a problem arises in industrial contexts, such as automated warehouses, where LGVs need to perform assigned tasks as fast as possible in order to increase productivity. It can be reformulated as an optimization problem with a convex objective function, linear velocity and acceleration constraints, and nonconvex jerk constraints, which, thus, represent the main source of the difficulty. While existing nonlinear programming (NLP) solvers can be employed for the solution of this problem, it turns out that the performance and robustness of such solvers can be enhanced by the sequential line-search algorithm proposed in this article. At each iteration, a feasible direction, with respect to the current feasible solution, is computed, and a step along such direction is taken in order to compute the next iterate. The computation of the feasible direction is based on the solution of a linearized version of the problem, and the solution of the linearized problem, through an approach that strongly exploits its special structure, represents the main contribution of this work. The efficiency of the proposed approach with respect to existing NLP solvers is proven through different computational experiments. Note to Practitioners—This article was motivated by the needs of LGV manufacturers. In particular, it presents an algorithm for computing the minimum-time speed law for an LGV along a preassigned path, respecting assigned velocity, acceleration, and jerk constraints. The solution algorithm should be: 1) fast, since speed planning is made continuously throughout the workday, not only when an LGV receives a new task but also during the execution of the task itself, since conditions may change, e.g., if the LGV has to be halted for security reasons and 2) reliable, i.e., it should return solutions of high quality, because a better speed profile allows to save time and even small percentage improvements, say a 5% improvement, has a considerable impact on the productivity of the warehouse, and, thus, determines a significant economic gain. The algorithm that we propose meets these two requirements, and we believe that it can be a useful tool for LGV manufacturers and users. It is obvious that the proposed method also applies to the speed planning problem for vehicles other than LGVs, e.g., road vehicles. [ABSTRACT FROM AUTHOR]

We study a class of generic charging path optimization problems arising from emerging networking applications, where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We show that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design quasi-polynomial-time algorithms achieving logarithmic approximation to the optimum charging path. Our approximation algorithms can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget. [ABSTRACT FROM AUTHOR]

This article focuses on developing a static output feedback (SOF) control scheme for Takagi–Sugeno fuzzy systems. The proposed SOF controller does not share the same premise membership functions with the model, which permits enhancing the flexibility in controller design and implementation. By contrast with the state feedback case, the SOF control generally results in nonconvex design conditions. To circumvent this problem, we develop a successive convex optimization algorithm, which is based on solving a sequence of more tractable convex optimization problems obtained by approximating the nonconvex constraints with some convex ones. As a heuristic algorithm, the validity of the developed successive convex optimization algorithm is highly affected by initial conditions, and, recognizing this, we put forward an iterative procedure for determining the feasible initial condition. Finally, two illustrative examples are presented to validate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

We study stable instances of the k -means problem with penalties in fixed-dimensional Euclidean space. An instance of the problem is called α -stable if this instance exists a sole optimal solution and the solution keeps unchanged when distances and penalty costs are scaled by a factor of no more than α. Stable instances of clustering problem have been used to explain why certain heuristic algorithms with poor theoretical guarantees perform quite well in practical. For any fixed ϵ > 0 , we show that when using a common multi-swap local-search algorithm, a (1 + ϵ) -stable instance of the k -means problem with penalties in fixed-dimensional Euclidean space can be solved accurately in polynomial time. [ABSTRACT FROM AUTHOR]

With the integration of Mobile Edge Computing (MEC) and Network Function Virtualization (NFV), service providers are able to provide low-latency services to mobile users for profit. In this paper, we study the online service placement and request assignment problem in an MEC network, where service requests arrive one by one without the knowledge of future arrivals, and each arrived request demands a specific service with a tolerable service delay requirement with the aim to maximize the profit of the service provider, through admitting as many service requests as possible for a given monitoring period. This optimization objective is achieved by assigning service requests to appropriate cloudlets in the MEC network, pre-installing service instances into cloudlets to shorten service delays, and accommodating new services by revoking some idle service instances from cloudlets due to limited computing resources in MEC networks. In this paper, we first show that the problem is NP-hard. We then devise an efficient deep reinforcement learning algorithm for the online service placement and request assignment problem that consists of a deep reinforcement learning-based prediction mechanism for dynamic service placement, followed by a dynamic request assignment procedure to assign requests to cloudlets. We finally evaluate the performance of the proposed algorithms by conducting experiments through simulations. Simulation results demonstrate that the proposed algorithm is promising, improving performance by 46.8% compared with that of the comparison algorithms. [ABSTRACT FROM AUTHOR]

In this article, we consider the optimal coordination of automated vehicles at intersections under fixed crossing orders. We formulate the problem using direct optimal control and exploit the structure to construct a semidistributed primal-dual interior-point algorithm to solve it by parallelizing most of the computations. Differently from standard distributed optimization algorithms, where the optimization problem is split, in our approach we split the linear algebra steps, such that the algorithm takes the same steps as a fully centralized one, while still performing computations in a distributed fashion. We analyze the communication requirements of the algorithm, and propose an approximation scheme which can significantly reduce the data exchange. We demonstrate the effectiveness of the algorithm in hard but realistic scenarios, which show that the approximation leads to reductions in communicated data of almost 99% of the exact formulation, at the expense of less than 1% suboptimality. [ABSTRACT FROM AUTHOR]

In this study, macroscopic properties of the vector approximate message passing (VAMP) algorithm for inference of generalized linear models are investigated using a non-rigorous heuristic method of statistical mechanics when the true posterior cannot be used and the measurement matrix is a sample from rotation-invariant random matrix ensembles. The focus is on the correspondence between the non-rigorous replica analysis of statistical mechanics and the performance assessment of VAMP in the model-mismatched setting. The correspondence of this kind is well-known when the measurement matrix has independent and identically distributed entries. However, when the measurement matrix follows a general rotation-invariant matrix ensemble, the correspondence has been validated only under limited cases, such as the Bayes optimal inference or the convex empirical risk minimization. The result presented in this paper is to extend the scope of such correspondence. Herein, we heuristically derive the explicit formula of state-evolution equations, which macroscopically describe VAMP dynamics for the current model-mismatched case, and show that their fixed point is generally consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, which indicates that message variables continue to move by VAMP while their macroscopically summarized quantities converge to fixed values. The critical condition the for microscopic instability agrees with that for breaking the replica symmetry that is derived within the non-rigorous replica analysis. The results of the numerical experiments cross-check our findings. [ABSTRACT FROM AUTHOR]

This article investigates optimal control problem for a class of discrete-time (DT) nonlinear systems with unknown dynamics. With the help of a broad learning system (BLS), a novel online adaptive dynamic programming (ADP) controller is presented. First, to approximate the unknown system dynamics, an approximator based on BLS is presented. The connection weights are calculated by the data of the system by using the ridge regression algorithm. Then, two BLSs are adopted to approximate the optimal cost function and optimal control law, respectively. The connection weights of these two BLSs are updated using the given weights tuning law at each sampling instant. The proposed optimal controller is proved to ensure that all the system states and estimation errors are uniform ultimate bounded. Finally, simulation examples are carried out to further demonstrate the effectiveness of the proposed BLS-based approximator and optimal controller. [ABSTRACT FROM AUTHOR]

We consider decentralized large-scale continuous submodular constrained optimization problems over networks, where the goal is to maximize a sum of nonconvex functions with diminishing returns property. However, the computations of the projection step and the whole gradient can become prohibitive in high-dimensional constrained optimization problems. For this reason, a decentralized randomized block-coordinate Frank-Wolfe algorithm is proposed for submoduar maximization over networks by local communication and computation, which adopts the randomized block-coordinate descent and the Frank-Wolfe technique. We also show that the proposed algorithm converges to an approximation fact $(1-e^{-p_{\max }/p_{\min }})$ of the global maximal points at a rate of $\mathcal {O}(1/T)$ by choosing a suitable stepsize, where $T$ is the number of iterations. In addition, we confirm the theoretical results by experiments. [ABSTRACT FROM AUTHOR]

Network slicing is a promising approach for enabling low latency computation offloading in edge computing systems. In this paper, we consider an edge computing system under network slicing in which the wireless devices generate latency sensitive computational tasks. We address the problem of joint dynamic assignment of computational tasks to slices, management of radio resources across slices and management of radio and computing resources within slices. We formulate the Joint Slice Selection and Edge Resource Management (JSS-ERM) problem as a mixed-integer problem with the objective to minimize the completion time of computational tasks. We show that the JSS-ERM problem is NP-hard and develop an approximation algorithm with bounded approximation ratio based on a game theoretic treatment of the problem. We use extensive simulations to provide insight into the performance of the proposed solution from the perspective of the whole system and from the perspective of individual slices. Our results show that the proposed slicing policy can achieve significant gains compared to the equal slicing policy, and that the computational complexity of the proposed task placement algorithm is approximately linear in the number of devices. [ABSTRACT FROM AUTHOR]

Emerging virtual network functions (VNFs) bring new opportunities to network services on the edge within customers’ premises. Network services are realized by chained up VNFs, which are called service function chains (SFCs). These services are deployed on commercial edge servers for higher flexibility and scalability. Despite such promises, it is still unclear how to provide highly available and cost-effective SFCs under edge resource limitations and time-varying VNF failures. In this paper, we propose a novel Reliability-aware Adaptive Deployment scheme named RAD to efficiently place and back up SFCs over both the edge and the cloud. Specifically, RAD first deploys SFCs to fully utilize edge resources. It then uses both static backups and dynamic ones created on the fly to guarantee the availability under the resource limitation of edge networks. RAD does not assume failure rates of VNFs but instead strives to find the sweet spot between the desired availability of SFCs and the backup cost. Theoretical performance bounds, extensive simulations, and small-scale experiments highlight that RAD provides significantly higher availability with lower backup costs compared with existing baselines. [ABSTRACT FROM AUTHOR]

5G communication network is vital to the intelligent and unmanned technology of open-pit mine, but the high cost of 5G base station deployment will bring huge cost increases to mining enterprises. Thus, this article proposes an improved sparrow search algorithm (SSA) using random walk strategy (RWSSA) to optimization the distribution and signal coverage of 5G base stations in open-pit mine. In order to verify the performance of the algorithm, the SSA, the modified ant lion optimizer, the particle swarm optimization, and the RWSSA were used to compare and analyze the accuracy and speed of the algorithm in solving high dimensionality benchmark functions, respectively. The dimensions used in the test are 30, 100, and 500 dimensions. After that, four algorithms were applied to a real example to optimize the deployment of 5G base stations, including macrobase stations and microbase stations. RWSSA has very good performance in terms of performance and practical application. Therefore, RWSSA is more suitable for the application of 5G base station distribution optimization in open-pit mines. [ABSTRACT FROM AUTHOR]

Static and dynamic clustering algorithms are a fundamental tool in any machine learning library. Most of the efforts in developing dynamic machine learning and data mining algorithms have been focusing on the sliding window model or more simplistic models. However, in many real-world applications one might need to deal with arbitrary deletions and insertions. For example, one might need to remove data items that are not necessarily the oldest ones, because they have been flagged as containing inappropriate content or due to privacy concerns. Clustering trajectory data might also require to deal with more general update operations. We develop a $(2+\epsilon)$ (2 + ε) -approximation algorithm for the $k$ k -center clustering problem with “small” amortized cost under the fully dynamic adversarial model. In such a model, points can be added or removed arbitrarily, provided that the adversary does not have access to the random choices of our algorithm. The amortized cost of our algorithm is poly-logarithmic when the ratio between the maximum and minimum distance between any two points in input is bounded by a polynomial, while $k$ k and $\epsilon$ ε are constant. Furthermore, we significantly improve the memory requirement of our fully dynamic algorithm, although at the cost of a worse approximation ratio of $4 +\epsilon$ 4 + ε . Our theoretical results are complemented with an extensive experimental evaluation on dynamic data from Twitter, Flickr, as well as trajectory data, demonstrating the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

The Recently proposed Vector Approximate Message Passing (VAMP) algorithm demonstrates a great reconstruction potential at solving compressed sensing related linear inverse problems. VAMP provides high per-iteration improvement, can utilize powerful denoisers like BM3D, has rigorously defined dynamics and is able to recover signals measured by highly undersampled and ill-conditioned linear operators. Yet, its applicability is limited to relatively small problem sizes due to the necessity to compute the expensive LMMSE estimator at each iteration. In this work we consider the problem of upscaling VAMP by utilizing Conjugate Gradient (CG) to approximate the intractable LMMSE estimator. We propose a rigorous method for correcting and tuning CG withing CG-VAMP to achieve a stable and efficient reconstruction. To further improve the performance of CG-VAMP, we design a warm-starting scheme for CG and develop theoretical models for the Onsager correction and the State Evolution of Warm-Started CG-VAMP (WS-CG-VAMP). Additionally, we develop robust and accurate methods for implementing the WS-CG-VAMP algorithm. The numerical experiments on large-scale image reconstruction problems demonstrate that WS-CG-VAMP requires much fewer CG iterations compared to CG-VAMP to achieve the same or superior level of reconstruction. [ABSTRACT FROM AUTHOR]

We study the resilient scheduling of moldable parallel jobs on high-performance computing (HPC) platforms. Moldable jobs allow for choosing a processor allocation before execution, and their execution time obeys various speedup models. The objective is to minimize the overall completion time or the makespan, when jobs can fail due to silent errors and hence may need to be re-executed after each failure until successful completion. Our work generalizes the classical scheduling framework for failure-free jobs. To cope with silent errors, we introduce two resilient scheduling algorithms, Lpa-List and Batch-List, both of which use the List strategy to schedule the jobs. Without knowing a priori how many times each job will fail, Lpa-List relies on a local strategy to allocate processors to the jobs, while Batch-List schedules the jobs in batches and allows only a restricted number of failures per job in each batch. We prove approximation ratios for the two algorithms under several prominent speedup models (e.g., roofline, communication, Amdahl, power, monotonic, and a mix model). An extensive set of simulations is conducted to evaluate different variants of the two algorithms, and the results show that they consistently outperform some baseline heuristics. Overall, our best algorithm is within a factor of 1.6 of a lower bound on average over the entire set of experiments, and within a factor of 4.2 in the worst case. [ABSTRACT FROM AUTHOR]

Tandem repeats are repetitive structures present in some DNA sequences, consisting of many repeated copies of a single motif. They can serve as important markers for phylogenetic and population genetic studies, due to the high polymorphism in the number of motif copies as well as variations in the motif. The first step in using tandem repeats for phylogenetic studies is to estimate the evolutionary distance between a pair $D_1$ D 1 and $D_2$ D 2 of tandem repeat sequences with homologous motifs. This problem can be broken into two sub-problems: 1) Construct the most recent common ancestor of the sequences. 2) Calculate the evolutionary distance between each sequence and the hypothesised common ancestor. We present an algorithm that estimates the solution to the second problem. This takes the form of an asymmetric alignment algorithm to estimate the evolutionary distance between two tandem repeat sequences $A$ A and $D$ D , where $D$ D is assumed to have descended from $A$ A , under a model that allows block duplication, deletion, and variant substitution. The algorithm is asymmetric in the sense that the two input sequences $A$ A and $D$ D play different roles in the calculations, reflecting the assumption that $D$ D descends from $A$ A . Our model assumes static motif boundaries, meaning that motif duplication and deletion events must respect the motif boundaries. The algorithm may also be applied without modification to more complex repetitive structures with two or more motifs, such as nested tandem repeats. [ABSTRACT FROM AUTHOR]

This article is concerned with the problem of computing the approximate preinverses of a fuzzy matrix with max-product composition. Employing the weighted $L_1$ distance, a variety of evaluation functions are defined according to the preselected weights, and then, an analytical method is proposed to determine all approximate preinverses of equal quality by minimizing the preselected evaluation function. Since only the approximate preinverses with fewer or preferably no zeros are acceptable for many practical applications, a criterion for selecting weights is established to ensure that the determined approximate preinverses are desirable. Some examples are given to illustrate our results. [ABSTRACT FROM AUTHOR]

We formulate and analyze a generic task scheduling problem: a set of tasks need to be executed on a pool of continuous resource such as spectrum and memory, each requiring a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource. We seek an optimal resource allocation and the related scheduling policy maximizing the overall system utility. This problem, termed as the contiguous-resource batching task scheduling problem, arises in a variety of engineering fields, where communication and storage resources are potential bottlenecks and thus need to be carefully scheduled. Two motivating examples are the spectrum bonding problem in dynamic spectrum access systems and the dynamic storage allocation problem in computer systems. In this paper, we investigate both offline and online scheduling settings. We first establish the NP-hardness of the offline setting and the inapproximability of the online setting in its generic form. Given the theoretical performance limit, we then develop approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios for the offline and online settings. [ABSTRACT FROM AUTHOR]

Network function virtualization (NFV) is a promising technology that decouples network functions from hardware. Connecting virtual network functions (VNFs) in series to form a service function chain (SFC) can flexibly orchestrate and expand network functions. However, there are higher availability requirements for SFCs. This paper aims to solve the SFC placement problem under availability and resource constraints. This paper proposes the sideway cross (SC) backup model, which considers the availability of both VNFs and physical machines (PMs) in a data center. The SC model cross-arranges the backup instances of VNFs to guarantee availability and optimize resource consumption. Then, this paper proposes the heuristic meteor shower optimization (MSO) algorithm to place SFCs. Compared to traditional heuristic algorithms, MSO can improve the execution time by approximately 200%. Combined with the SC backup model, MSO can effectively improve the availability and resource overhead. The evaluation results show that the proposed approach can guarantee higher availability and consumes fewer resources. The proposed approach only needs 75% of the resources to achieve the same availability as the state-of-the-art models. [ABSTRACT FROM AUTHOR]

Online social network has deeply changed our lives, such as the style of communication and business, and hence promotes a lot of researches in social influence. The prior works in social influence mainly consider the influence from the view of individuals. However, in many cases, influencing the most of members of an important group such as the board of directors in a company can bring bigger profit than directly influencing the individuals of the company. We call such high profit group which obeys the vote rule as an union, different from existed targeted influence model, we consider such scenarios to make union acceptable and propose the union acceptable profit problem (UAPM) to choose seeds to maximize the union-acceptable profit, i.e., maximize the probability of the union being acceptable. The objective of profit in UAPM is #P-hard, and not submodularity or supmodularity. To solve the problem, we propose an efficient estimation method for the objective and design a heuristic algorithm and further a data-driven β (1 − 1 ϵ) -approximation algorithm where β is the data-driven parameter which is related to the input data. At last we evaluate the performance of the algorithms we proposed on effectiveness and efficiency by the experiments in real-world social network datasets. • We formulate a new problem of UAPM which proved to be hard to solve. • An efficient estimation method for the objective is proposed based on an optimized sampling algorithm. • We propose a heuristic algorithm and a data-driven approximation algorithm respectively to solve the problem. • Experiments with the real-world databases validate the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

Shortest path query in road network is pervasive in various location-based services nowadays. As the business expands, the scalability issue becomes severer and more servers are deployed to cope with it. Moreover, as the traffic condition keeps changing over time, the existing index-based approaches can hardly adapt to the real-life dynamic environment. Therefore, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this work, we assume the traffic condition is stable over a short period and treat the issued queries within that period as a stream of query sets. Specifically, we first propose three query set decomposition methods to cluster one query set into multiple query subsets: Zigzag that considers the 1-N shared computation; Co-Clustering that considers the source and target's spatial locality; and Search-Space-Aware that further incorporates search space estimation. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering: R2R that finds a set of approximate shortest paths from one region to another with bounded error; and Local Cache that improves the existing Global Cache with higher cache hit ratio. Finally, we design three efficient stream processing methods for intra-batch shared computation. The experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider a distributed joint sensing and communication (DJSC) system in which each radar sensor as a JSC node is equipped with a sensing function and a communication function. Deploying multiple JSC nodes may require a large amount of bandwidth. Therefore, we investigate the bandwidth allocation problem for the DJSC system. In particular, we aim to optimize the bandwidth allocation to the sensing function and the communication function of the JSC nodes. To improve the allocation efficiency while benefiting the spatial diversity advantage of the DJSC systems, the objective is to maximize the sum of sensing performances, i.e., estimation rates, communication performances, i.e., communication data rates, and fairness of all the users. The optimization problem is non-convex and difficult to be solved. For this, we propose a fully polynomial time approximation algorithm, and we prove that the approximation algorithm can guarantee a near-optimal solution with an accuracy bound of $\epsilon$. Furthermore, we propose to use a heuristic algorithm with lower complexity. The simulation results show that both the proposed algorithms are able to achieve the solutions close to the optimum in a computationally efficient fashion. [ABSTRACT FROM AUTHOR]

The Internet of Things (IoT) technology provisions unprecedented opportunities to evolve the interconnection among human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated Mobile Edge Computing (MEC) with remote clouds is a promising platform to enable delay-sensitive service provisioning for IoT applications, where edge-clouds (cloudlets) are co-located with wireless access points in the proximity of IoT devices. Thus, computation-intensive and sensing data from IoT devices can be offloaded to the MEC network immediately for processing, and the service response latency can be significantly reduced. In this paper, we first formulate two novel optimization problems for delay-sensitive IoT applications, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction on the use of the services provided by the MEC, and show the NP-hardness of the defined problems. We then devise efficient approximation and online algorithms with provable performance guarantees for the problems in a special case where the bandwidth capacity constraint is negligible. We also develop efficient heuristic algorithms for the problems with the bandwidth capacity constraint. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising in reducing service delays and enhancing user satisfaction, and the proposed algorithms outperform their counterparts by at least 10.8 percent. [ABSTRACT FROM AUTHOR]

Multi-access edge computing (MEC) is a promising computing paradigm that incorporates computing capability into a radio access network (RAN) nearby user equipment (UE) to improve the quality of experience. However, MEC also encounters many challenges inherent in RANs, such as mobility management. In this letter, we develop a novel computation offloading scheme utilizing non-orthogonal multiple access (NOMA) and dual connectivity (DC) and focus on jointly optimizing task segmentation and power allocation to minimize the total energy consumption. Specifically, the joint optimization problem is formulated as a mixed-integer nonlinear programming (MINLP) problem that is non-deterministic polynomial hard (NP-hard). To solve this problem, we propose a new heuristic algorithm to obtain a sub-optimal solution. We then propose an online learning algorithm based on a twin delayed deep deterministic policy gradient (TD3) to meet user mobility requirements. The numerical results show that the proposed scheme outperforms other schemes, and the TD3-based algorithm has comparable energy consumption performance and dramatically reduces the execution time compared with the heuristic algorithm. [ABSTRACT FROM AUTHOR]

In the massive grant-free orthogonal frequency division multiple access (OFDMA), the timing and frequency offsets between users impose new challenges on joint active user detection (AUD) and channel estimation (CE) for the subsequent data recovery. In the asynchronous OFDMA, the timing and frequency offset effects can be modeled as the phase-shifting on the pilot matrix. As such, by constructing the measurement matrix with timing and frequency offsets, the joint estimation problem can be formulated as a multiple measurement vector (MMV) recovery problem with structured sparsity. However, such structured sparsity cannot be tackled by the existing compressed sensing (CS) techniques. To address this issue, we develop an efficient structured generalized approximate message passing (S-GAMP) algorithm, which includes the parallel AMP-MMV algorithm as a particular case. To deal with the high dimensionality of the measurement matrix, we propose the dynamic S-GAMP algorithm with a dynamic measurement matrix to reduce the computational complexity. Simulation results confirm the superiority of the proposed algorithms in grant-free OFDMA with both timing and frequency offsets. [ABSTRACT FROM AUTHOR]

The maximum clique problem (MCP) has various applications to reveal the structure and function of graphs. Graphs are constantly updated in the real life. However, no algorithm is specifically designed for dynamic graph. Although MCP in dynamic graphs can be solved by simply invoking a state-of-the-art static approach, such as PMC, when the graph is updated, such an approach of simply re-calculating from scratch is inefficient. The key issue with MCP algorithm is to find a large clique, namely a seed, as fast as possible. Thus, search space can be pruned based on the seed. Size of the seed greedily found by PMC cannot be guaranteed, as it fluctuates considerably. Moreover, the time required to find a seed under PMC is up to $O(| E| \cdot \Delta (G))$ O (| E | · Δ (G)) , where $\Delta (G)$ Δ (G) is the highest degree in G. In this article, we intend to find a sizable seed by updating the previous maximum clique with the incident vertices of the inserted/deleted edge. Size of the seed now is guaranteed to be no less than $\omega (G^{\prime})\; - \;1$ ω (G ') - 1 , where $\omega (G^{\prime})$ ω (G ') is the size of the maximum clique on the updated graph. Moreover, the seed can be found in a time complexity of $O(\Delta (G)^{2})$ O (Δ (G) 2) . Two other crucial issues related to the MCP in dynamic graphs are refreshing rate and refreshing overhead. After a tight upper bound is imposed on $\omega (G^{\prime})$ ω (G ') , the necessity of refreshing is evaluated by comparing the seed with its largest challenger, then unnecessary refreshing is wiped out effectively. The size of the largest challenger is judiciously estimated using a lazy growth strategy. Subsequently, the search space in refreshing is confined on a much smaller subgraph using a local refreshing strategy. Extensive experiments indicate that the proposed approach outperforms the baseline algorithm by approximately one order of magnitude. [ABSTRACT FROM AUTHOR]

The $K$ K -means algorithm is one of the most popular clustering methods. However, it is a well-known fact that its performance, in terms of quality of the obtained solution and computational load, highly depends upon its initialization phase. For this reason, different initialization techniques have been developed throughout the years to enable its fast convergence to competitive solutions. In this sense, it is common practice to re-start the $K$ K -means algorithm several times via one of these techniques and keep the solution with the lowest error. Unfortunately, such a choice is still likely to be a poor approximation of the optimal set of centroids. In this article, we introduce a cheap Split-Merge step that can be used to re-start the $K$ K -means algorithm after reaching a fixed point. Under some settings, one can show that this approach reduces the error of the given fixed point without requiring any further iteration of the $K$ K -means algorithm. Moreover, experimental results show that this strategy is able to generate approximations with an associated error that is hard to reach for different multi-start methods, such as multi-start Forgy $K$ K -means, $K$ K -means++ and Hartigan $K$ K -means, while also computing a lower amount of distances than the previous algorithms. [ABSTRACT FROM AUTHOR]

Modern search services often provide multiple options to rank the search results, e.g., sort "by relevance", "by price" or "by discount" in e-commerce. While the traditional rank by relevance effectively places the relevant results in the top positions of the results list, the rank by attribute could place many marginally relevant results in the head of the results list leading to poor user experience. In the past, this issue has been addressed by investigating the relevance-aware filtering problem, which asks to select the subset of results maximizing the relevance of the attribute-sorted list. Recently, an exact algorithm has been proposed to solve this problem optimally. However, the high computational cost of the algorithm makes it impractical for the Web search scenario, which is characterized by huge lists of results and strict time constraints. For this reason, the problem is often solved using efficient yet inaccurate heuristic algorithms. In this article, we first prove the performance bounds of the existing heuristics. We then propose two efficient and effective algorithms to solve the relevance-aware filtering problem. First, we propose OPT-Filtering, a novel exact algorithm that is faster than the existing state-of-the-art optimal algorithm. Second,we propose an approximate and even more efficient algorithm, ∈-Filtering, which, given an allowed approximation error ∈, finds a (1-∈)--optimal filtering, i.e., the relevance of its solution is at least (1-∈) times the optimum. We conduct a comprehensive evaluation of the two proposed algorithms against state-of-the-art competitors on two real-world public datasets. Experimental results show that OPT-Filtering achieves a significant speedup of up to two orders of magnitude with respect to the existing optimal solution, while ∈-Filtering further improves this result by trading effectiveness for efficiency. In particular, experiments show that ∈-Filtering can achieve quasi-optimal solutions while being faster than all state-of-the-art competitors in most of the tested configurations. [ABSTRACT FROM AUTHOR]

This article presents a data-driven method for computing reachable sets where active learning (AL) is used to reduce the computational burden. Set-based methods used to estimate reachable sets typically do not scale well with the state-space dimension, or rely heavily on the existence of a model. If such a model is not available, it is simple to generate state trajectory data by numerically simulating black-box oracles of systems (whose dynamics are unknown) from sampled initial conditions. Using these data samples, the estimation of reachable sets can be posed as a classification problem, wherein AL can intelligently select samples that are most informative and least similar to previously labeled samples. By exploiting submodularity, the actively learned samples can be selected efficiently, with bounded suboptimality. Our proposed framework is illustrated by estimating the domains of attractions of model predictive controllers (MPCs) and reinforcement learners. We also consider a scenario where there are two oracles that differ with respect to evaluation costs and labeling accuracy. We propose a framework to reduce the dependency of the expensive oracle in labeling samples using disagreement-based AL (DBAL). The potential of the DBAL algorithm is demonstrated on a solver selection problem for real-time MPC. [ABSTRACT FROM AUTHOR]

This article presents an event-sampled integral reinforcement learning algorithm for partially unknown nonlinear systems using a novel dynamic event-triggering strategy. This is a novel attempt to introduce the dynamic triggering into the adaptive learning process. The core of this algorithm is the policy iteration technique, which is implemented by two neural networks. A critic network is periodically tuned using the integral reinforcement signal, and an actor network adopts the event-based communication to update the control policy only at triggering instants. For overcoming the deficiency of static triggering, a dynamic triggering rule is proposed to determine the occurrence of events, in which an internal dynamic variable characterized by a first-order filter is defined. Theoretical results indicate that the impulsive system driven by events is asymptotically stable, the network weight is convergent, and the Zeno behavior is successfully avoided. Finally, three examples are provided to demonstrate that the proposed dynamic triggering algorithm can reduce samples and transmissions even more, with guaranteed learning performance. [ABSTRACT FROM AUTHOR]