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]

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]

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 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]

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 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]

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]

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]

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]

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]

Feature reduction is an important aspect of Big Data analytics on today’s ever-larger datasets. Rough sets are a classical method widely applied in attribute reduction. Most rough set algorithms use the priori domain knowledge of a dataset to process continuous attributes through using a membership function. Neighborhood rough sets (NRS) replace the membership function with the concept of neighborhoods, allowing NRS to handle scenarios where no a priori knowledge is available. However, the neighborhood radius of each object in NRS is fixed, and the optimization of the radius depends on grid searching. This diminishes both the efficiency and effectiveness, leading to a time complexity of not lower than $O(N^2)$ O (N 2) . To resolve these limitations, granular ball neighborhood rough sets (GBNRS), a novel NRS method with time complexity $O(N)$ O (N) , is proposed. GBNRS adaptively generates a different neighborhood for each object, resulting in greater generality and flexibility in comparison to standard NRS methods. GBNRS is compared with the current state-of-the-art NRS method, FARNeMF, and find that GBNRS obtains both higher performance and higher classification accuracy on public benchmark datasets. All code has been released in the open source GBNRS library at http://www.cquptshuyinxia.com/GBNRS.html. [ABSTRACT FROM AUTHOR]

In order to increase the nonlinear fitting performance of functional link neural network (FLNN), a novel chebyshev functional link spline neural filter (CFLSNF) to apply in system identification is proposed. Compared with the weak nonlinearity and boundedness of the fixed activation function (e.g., $sigmoid$ and $tanh$), CFLSNF has stronger nonlinear approximation ability than FLNN due to the flexible interpolation ability of spline activation function. At the same time, the proposed CFLSNF eliminates the hidden layers by using Chebyshev polynomial to extend the input space into high dimensions, which shows certain computational advantages compared with the artificial neural network (ANN) structures. Moreover, to update the weights of the CFLSNF, the CFLSNF-LMS is also developed. The stability conditions and computational complexity are studied. Besides, in order to make CFLSNF structure suitable for impulsive noise interference environment, a robust algorithm based on maximum versoria criterion is also proposed. Finally, the validity of the proposed architecture and algorithm are verified by experiments. [ABSTRACT FROM AUTHOR]

We suggest a new optimization technique for minimizing the sum $\sum _{i=1}^n g_i(x)$ ∑ i = 1 n g i (x) of $n$ n non-convex real functions that satisfy a property that we call piecewise log-Lipschitz. This is by forging links between techniques in computational geometry, combinatorics and convex optimization. As an example application, we provide the first constant-factor approximation algorithms whose running-times are polynomial in $n$ n for the fundamental problem of Points-to-Lines alignment: Given $n$ n points $p_1,\ldots,p_n$ p 1 ,... , p n and $n$ n lines $\ell _1,\ldots,\ell _n$ ℓ 1 ,... , ℓ n on the plane and $z>0$ z > 0 , compute the matching $\pi :[n]\to [n]$ π : [ n ] → [ n ] and alignment (rotation matrix $R$ R and translation vector $t$ t ) that minimize the sum of euclidean distances $\sum _{i=1}^n \mathrm{dist}(Rp_i-t,\ell _{\pi (i)})^z$ ∑ i = 1 n dist (R p i - t , ℓ π (i)) z between each point to its corresponding line. This problem is non-trivial even if $z=1$ z = 1 and the matching $\pi$ π is given. If $\pi$ π is given, our algorithms run in $O(n^3)$ O (n 3) time, and even near-linear in $n$ n using core-sets that support: streaming, dynamic, and distributed parallel computations in poly-logarithmic update time. Generalizations for handling e.g., outliers or pseudo-distances such as $M$ M -estimators for the problem are also provided. Experimental results and open source code show that our algorithms improve existing heuristics also in practice. A companion demonstration video in the context of Augmented Reality shows how such algorithms may be used in real-time systems. [ABSTRACT FROM AUTHOR]

Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of “semi-connection” that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions. [ABSTRACT FROM AUTHOR]

Recent research has revealed new and unexpected applications of network control science within biomedicine, pharmacology, and medical therapeutics. These new insights and new applications generated in turn a rediscovery of some old, unresolved algorithmic problems. One of these problems is the Structural Target Control optimization problem, known in previous literature also as Structural Output Controllability problem, which is defined as follows. Given a directed network and a target subset of nodes, the task is to select a small (or the smallest) set of nodes from which the target can be independently controlled, i.e., there exists a set of paths from the selected set of nodes (called driver nodes) to the target nodes such that no two paths intersect at the same distance from their targets. Recently, Structural Target Control optimization problem has been shown to be NP-hard, and several heuristic algorithms were introduced and analyzed, both on randomly generated networks, and on biomedical ones. In this paper, we show that the Structural Target Controllability problem is fixed parameter tractable when parameterized by the number of target nodes. We also prove that the problem is hard to approximate at a factor better than O(log n). Taking into consideration the real case formulations of this problem we identify two more parameters which are naturally constrained by smaller bounds: the maximal length of a controlling path and the size of the set of nodes from which the control can start. With these new parameters we provide an approximation algorithm which is of exponential complexity in the size of the set of nodes from which the control can start and polynomial in all the other parameters. [ABSTRACT FROM AUTHOR]

Aggregate nearest neighbor (Ann) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (Fann) problem further generalizes Ann by introducing an extra flexibility parameter $\phi$ ϕ that ranges in $(0, 1]$ (0 , 1 ] . In this article, we focus on Fann on road networks, denoted as Fann $_\mathcal {R}$ R , and its keyword-aware variant, denoted as KFann $_\mathcal {R}$ R . To solve these problems, we propose a series of universal (i.e., suitable for both max and sum) algorithms, including a Dijkstra-based algorithm that enumerates $P$ P instead of $\phi |Q|$ ϕ | Q | -combinations of $Q$ Q , a queue-based approach that processes data points from-near-to-far, and a framework that combines incremental euclidean restriction (IER) and $k$ k NN. We also propose a specific exact solution to max-Fann $_\mathcal {R}$ R and a constant-factor ratio approximate solution to sum-Fann $_\mathcal {R}$ R . These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top- $k$ k and multiple Fann $_\mathcal {R}$ R (resp., KFann $_\mathcal {R}$ R ) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality. [ABSTRACT FROM AUTHOR]

Measuring similarity among data objects is important in data analysis and mining. SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to the unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the SimRank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing and tracking all-pairs SimRank. Furthermore, we develop an iterative parallel two-step framework for local push to take advantage of modern hardwares with multicore CPUs. We show that our algorithms outperform the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The minimum dominating set (MDS) of the network is a node subset of smallest size that every node in the network is either in this subset or is adjacent to one or more nodes of this subset. MDS has found wide applications, ranging from network monitoring, routing, to epidemic control, and text processing. However, the majority of existing studies on MDS problem are confined to single networks. In real world, more and more complex systems consist of a set of elements linked up by different types of connections, which are best modeled as multiplex networks with interacting network layers. Though vastly important, the MDS of the multiplex networks has not yet been formally defined and its application and identification remain open issues. In this article, we present the definition of the MDS of the multiplex network and show some of its possible applications. For solving the MDS problem of the multiplex network, we built a spin-glass model and solve it through the belief-propagation (BP) equations under the replica symmetry mean-field theory. As a consequence, we can predict the relative size of the MDS of the multiplex network theoretically and we can propose a BP-guided decimation algorithm to construct an approximate optimal dominating set in practice. Then the algorithm is improved in both accuracy and efficiency by embedding a novel multiplex network-oriented leaf-removal strategy. The effectiveness of the proposed algorithms is finally verified by comparing with other methods on a number of the multiplex network examples. [ABSTRACT FROM AUTHOR]

Mobile edge computing becomes a promising technology to mitigate the latency of various cloud services. In addition, network function virtualization (NFV) has been shown a great potential in reducing the operational cost of cloud services while enhancing the flexibility of virtual network function deployments, by implementing dedicated hardware network functions as pieces of software in generic servers. Recently, the GPU acceleration has been investigated to speed up flow processing in virtual network functions (VNFs), by leveraging the parallelism of GPUs. VNFs that need accelerations prefer to stay at cloudlets (locations) equipped with GPUs. However, little attention has been paid for the VNF placement that takes into account GPU-affinity in cloudlets of mobile edge clouds. In this paper, we consider the affinity-aware throughput maximization problem in a mobile edge cloud via leveraging the parallelism on GPUs for user requests with VNF requirements. We consider two types of affinities in the VNF placement: The soft-affinity that allows VNFs to be executed by either CPUs or GPUs in cloudlets; and the hard-affinity that only allows VNFs to be placed to the GPUs of a specified set of cloudlets. We formulate two corresponding VNF placement problems in a mobile edge cloud. Specifically, we first propose an exact solution to the soft-affinity throughput maximization problem by formulating an Integer Linear Program (ILP). We then propose an efficient algorithm for the problem, by proposing a randomized algorithm with a provable approximation ratio for the hard-affinity-aware throughput maximization problem and extending the proposed approximation algorithm to the soft-affinity throughput maximization problem. Furthermore, assuming that user requests arrive into the mobile edge cloud one by one without the knowledge of future arrivals, we devise an online algorithm with a good competitive ratio for this dynamic hard-affinity-aware throughput maximization problem. Finally, we evaluate the performance of the proposed algorithms, through simulations and implementations in a real test-bed. Experimental results show that the performance of the proposed algorithms outperform their existing counterparts and achieve higher throughput. [ABSTRACT FROM AUTHOR]

This article investigates the design of self-triggered controllers for networked control systems (NCSs), where the dynamics of the plant are unknown a priori. To deal with the unknown transition dynamics, we employ the Gaussian process (GP) regression in order to learn the dynamics of the plant. To design the self-triggered controller, we formulate an optimal control problem, such that the optimal control and communication policies can be jointly designed based on the GP model of the plant. Moreover, we provide an overall implementation algorithm that jointly learns the dynamics of the plant and the self-triggered controller based on a reinforcement learning framework. Finally, a numerical simulation illustrates the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

Path tracking control of intelligent vehicles has to deal with the difficulties of model uncertainties and nonlinearities. As a class of adaptive optimal control methods, reinforcement learning (RL) has received increasing attention in solving difficult control problems. However, feature representation and online learning ability are two major problems to be solved for learning control of uncertain dynamic systems. In this article, we propose a multi-kernel online RL approach for path tracking control of intelligent vehicles. In the proposed approach, a multiple kernel feature learning framework is designed for online learning control based on dual heuristic programming (DHP) and the new online learning control algorithm is called multi-kernel DHP (MKDHP). In MKDHP, instead of the expert knowledge for selecting and fine-tuning of a suitable kernel function, only a set of basic kernel functions is required to be predefined and the multi-kernel features can be learned for value function approximation in the critic. The simulation studies on path tracking control for intelligent vehicles have been conducted under $S$ -curve and urban road conditions. The results demonstrated that compared with other typical path tracking controllers for intelligent vehicles, such as the linear quadratic regulator (LQR), the pure pursuit controller and the ribbon-based controller, the proposed multi-kernel learning controller can achieve better performance in terms of tracking precision and smoothness. [ABSTRACT FROM AUTHOR]

This article investigates the optimal control problem for nonlinear nonzero-sum differential game in the environment of no initial admissible policies while considering the control constraint. An adaptive learning algorithm is thus developed based on policy iteration technique to approximately obtain the Nash equilibrium using real-time data. A two-player continuous-time system is used to present this approximate mechanism, which is implemented as a critic–actor architecture for every player. The constraint is incorporated into this optimization by introducing the nonquadratic value function, and the associated constrained Hamilton–Jacobi equation is derived. The critic neural network (NN) and actor NN are utilized to learn the value function and the optimal control policy, respectively, in the light of novel weight tuning laws. In order to tackle the stability during the learning phase, two stable operators are designed for two actors. The proposed algorithm is proved to be convergent as a Newton’s iteration, and the stability of this closed-loop system is also ensured by Lyapunov analysis. Finally, two simulation examples demonstrate the effectiveness of the proposed learning scheme by considering different constraint scenes. [ABSTRACT FROM AUTHOR]

In a software defined network, the controller needs to obtain/collect traffic measurement information (i.e., flow statistics) from switches for different applications, such as traffic engineering. Existing solutions seldom consider the per-switch cost, which may lead to heavy statistics collection cost (e.g., high CPU overhead) on some switches. Due to limited computing power on most commodity switches, heavy statistics collection cost on those switches may seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we design and implement efficient flow statistics collection (FSC) with limited interference on the basic rule operations. We formally propose a cooperative flow statistics collection with per-switch cost constraint (CP-FSC) problem. We prove that the CP-FSC problem is NP-hard and present an efficient algorithm with approximation ratio 1/2, based on dynamic programming. To reduce the time complexity, a greedy-based algorithm with approximation ratio 1/3 is also presented. We implement the proposed FSC algorithms on our SDN platform. The experimental results and the extensive simulation results show 36%-59% performance improvement compared with the existing solutions. [ABSTRACT FROM AUTHOR]

The capacitated vehicle routing problem (CVRP) has been extensively investigated in the past years due to their applications in a variety of real-world scenarios. However, it is still very challenging for most existing algorithms to tackle large-scale CVRPs (LSCVRPs), namely, CVRPs with hundreds or thousands of customers. In this article, we propose a heuristic algorithm, called EMRG-HA, to address LSCVRPs based on the framework of divide and conquer, where an evolutionary multiobjective route grouping (EMRG) method is suggested to decompose an LSCVRP into small subcomponents. The suggested EMRG adopts a multiobjective evolutionary algorithm for route grouping by simultaneously optimizing three well-defined objectives, intragroup distance, intergroup distance, and intergroup balance in size, which can obtain a set of promising decompositions of LSCVRPs. Based on the EMRG, a local search method is suggested to improve the quality of routes in groups, where only routes in one group instead of in all groups are improved which is determined according to the average serving cost of routes in each group. The performance of the proposed EMRG-HA is verified on 42 test instances from three popular benchmark suites. The experimental results show that the EMRG-HA is superior over eight existing algorithms on most test instances of LSCVRPs, in terms of both computational efficiency and solution quality. [ABSTRACT FROM AUTHOR]

Since the late 1980s, temporal difference (TD) learning has dominated the research area of policy evaluation algorithms. However, the demand for the avoidance of TD defects, such as low data-efficiency and divergence in off-policy learning, has inspired the studies of a large number of novel TD-based approaches. Gradient-based and least-squares-based algorithms comprise the major part of these new approaches. This paper aims to combine advantages of these two categories to derive an efficient policy evaluation algorithm with ${O}$ (${n} ^{ {2}}$) per-time-step runtime complexity. The least-squares-based framework is adopted, and the gradient correction is used to improve convergence performance. This paper begins with the revision of a previous ${O}$ (${n} ^{ {3}}$) batch algorithm, least-squares TD with a gradient correction (LS-TDC) to regularize the parameter vector. Based on the recursive least-squares technique, an ${O}$ (${n} ^{ {2}}$) counterpart of LS-TDC called RC is proposed. To increase data efficiency, we generalize RC with eligibility traces. An off-policy extension is also proposed based on importance sampling. In addition, the convergence analysis for RC as well as LS-TDC is given. The empirical results in both on-policy and off-policy benchmarks show that RC has a higher estimation accuracy than that of RLSTD and a significantly lower runtime complexity than that of LSTDC. [ABSTRACT FROM AUTHOR]