Search

Online social networks have become major battlegrounds for political campaigns, viral marketing, and the dissemination of news. As a consequence, “bad actors” are increasingly exploiting these platforms, which is a key challenge for their administrators, businesses and society in general. The spread of fake news is a classical example of the abuse of social networks by these bad actors. While some have advocated for stricter policies to control the spread of misinformation in social networks, this often happens in detriment of their democratic and organic structure. In this paper, we aim to limit the influence of a target group in a social network via the removal of a few users/links. We formulate the influence limitation problem in a data-driven fashion, by taking into account past propagation traces. More specifically, our algorithms find critical edges to be removed in order to decrease the influence of a target group based on past data. The idea is to control the diffusion processes while minimizing the amount of disturbance in the network structure. Moreover, we consider two types of constraints over edge removals, a budget constraint and also a, more general, set of matroid constraints. These problems lead to interesting challenges in terms of algorithm design. For instance, we are able to show that influence limitation is APX-hard and propose deterministic and probabilistic approximation algorithms for the budgeted and the matroid version of the problem, respectively. Experiments show that the proposed approaches outperform several baselines. [ABSTRACT FROM AUTHOR]

Problems in scientific computing, such as distributing large sparse matrix operations, have analogous formulations as hypergraph partitioning problems. A hypergraph is a generalization of a traditional graph wherein “hyperedges” may connect any number of nodes. As a result, hypergraph partitioning is an NP-Hard problem to both solve or approximate. State-of-the-art algorithms that solve this problem follow the multilevel paradigm, which begins by iteratively “coarsening” the input hypergraph to smaller problem instances that share key structural features. Once identifying an approximate problem that is small enough to be solved directly, that solution can be interpolated and refined to the original problem. While this strategy represents an excellent trade off between quality and running time, it is sensitive to coarsening strategy. In this work we propose using graph embeddings of the initial hypergraph in order to ensure that coarsened problem instances retrain key structural features. Our approach prioritizes coarsening within self-similar regions within the input graph, and leads to significantly improved solution quality across a range of considered hypergraphs. Reproducibility: All source code, plots and experimental data are available at https://sybrandt.com/2019/partition. [ABSTRACT FROM AUTHOR]

Influence maximization (IM) aims at maximizing the spread of influence by offering discounts to influential users (called seeding). In many applications, due to user’s privacy concern, overwhelming network scale etc., it is hard to target any user in the network as one wishes. Instead, only a small subset of users is initially accessible. Such access limitation would significantly impair the influence spread, since IM often relies on seeding high degree users, which are particularly rare in such a small subset due to the power-law structure of social networks. In this paper, we attempt to solve the limited IM in real-world scenarios by the adaptive approach with seeding and diffusion uncertainty considered. Specifically, we consider fine-grained discounts and assume users accept the discount probabilistically. The diffusion process is depicted by the independent cascade model. To overcome the access limitation, we prove the set-wise friendship paradox (FP) phenomenon that neighbors have higher degree in expectation, and propose a two-stage seeding model with the FP embedded, where neighbors are seeded. On this basis, for comparison we formulate the non-adaptive case and adaptive case, both proven to be NP-hard. In the non-adaptive case, discounts are allocated to users all at once. We show the monotonicity of influence spread w.r.t. discount allocation and design a two-stage coordinate descent framework to decide the discount allocation. In the adaptive case, users are sequentially seeded based on observations of existing seeding and diffusion results. We prove the adaptive submodularity and submodularity of the influence spread function in two stages. Then, a series of adaptive greedy algorithms are proposed with constant approximation ratio. Extensive experiments on real-world datasets show that our adaptive algorithms achieve larger influence spread than non-adaptive and other adaptive algorithms (up to a maximum of 116 percent). [ABSTRACT FROM AUTHOR]

In this article, a new comprehensive system for distributed multisensor multitarget tracking is proposed. All of its functions, including track initiation, confirmation, maintenance and termination, and track-to-track association and fusion, are built around the concept of the probability of target existence (PTE). A new track maintenance algorithm is composed of the correction part, with data association requiring computations linearly depending on the number of measurements and tracks, and the prediction part, containing an adaptive consensus scheme, coping with limited sensor observability. A new track-to-track association and fusion algorithm based on an approximation of track association probability is also proposed, ensuring consistency and continuity of individual tracks. Track initiation and termination algorithms are derived on the basis of local PTEs. Stability of the proposed system is studied for the steady state and time-varying regimes. The system as a whole achieves high performance close to the centralized solution, outperforming all the comparable existing state-of-the-art approaches, keeping much lower communication and computation requirements. [ABSTRACT FROM AUTHOR]

This article proposes a learning-based adaptive sliding-mode control for the underactuted deployment of tethered space robot with limited input. The reduced-order system on the sliding surface is optimized by the critic neural network-based nearly optimal approximation algorithm, and both the linear and nonlinear situations are taken into account. To remove the assumption that the state-dependent disturbance is vanishing, the behavior of state synchronization on the sliding surface is revealed for the first time, and the nearly optimal solution of limited input for generating stable trajectory can be approximated by the actor neural network-based adaptive dynamic programming. The hyperbolic tangent of desired input is synthesized into the optimal value function, and it can be obtained by the actor-critic neural network-based reinforcement learning algorithm solving the corresponding Hamilton–Jacobi–Bellman equation. The numerical simulation takes the numerical example of the deployment of tethered space robot to verify the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper studies a general framework for high-order tensor SVD. We propose a new computationally efficient algorithm, tensor-train orthogonal iteration (TTOI), that aims to estimate the low tensor-train rank structure from the noisy high-order tensor observation. The proposed TTOI consists of initialization via TT-SVD [Oseledets (2011)] and new iterative backward/forward updates. We develop the general upper bound on estimation error for TTOI with the support of several new representation lemmas on tensor matricizations. By developing a matching information-theoretic lower bound, we also prove that TTOI achieves the minimax optimality under the spiked tensor model. The merits of the proposed TTOI are illustrated through applications to estimation and dimension reduction of high-order Markov processes, numerical studies, and a real data example on New York City taxi travel records. The software of the proposed algorithm is available online (https://github.com/Lili-Zheng-stat/TTOI). [ABSTRACT FROM AUTHOR]

Hammerstein model with a static nonlinearity followed by a linear filter is commonly used in numerous applications. This paper focuses on adaptive filtering techniques for parameter identification of Hammerstein systems and output prediction of nonlinear systems. By formulating the underlying filtering problem as a recursive bilinear least-squares optimization with the non-convex feasible region constraint, we develop a recursive non-convex projected least-squares (RncPLS) algorithm based on alternating direction method of multipliers (ADMM). The RncPLS algorithm alternates between implementing ridge regression and projecting on the non-convex feasible set, which successively refines the system parameters. The convergence and accuracy properties of the proposed RncPLS algorithm are theoretically investigated. Moreover, extensive simulation results in the context of system identification, nonlinear predication, and acoustic echo cancellation, are also included to demonstrate the performance characteristics of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Numerical optimization has been playing an increasingly important role in the design of contemporary antenna systems. Due to the shortage of design-ready theoretical models, optimization is mainly based on electromagnetic (EM) analysis, which tends to be costly. Numerous techniques have evolved to abate this cost, including surrogate-assisted frameworks for global optimization, or sparse sensitivity updates for speeding up local search. In the latter, CPU-heavy updates of the system response sensitivity through finite differentiation are suppressed based on, e.g., the magnitude of design variability during the optimization run. Another approach is to incorporate variable-resolution simulations. Recently, a technique exploiting a continuous spectrum of admissible model fidelity levels has been reported, thereby allowing for a considerable reduction of computational expenditures. Seeking further savings, this work introduces an accelerated gradient-based algorithm with sparse sensitivity updates and variable-resolution EM simulations. Our technique is validated using four broadband antennas, and demonstrated to offer substantial (around 80%) savings over the benchmark while maintaining acceptable design quality. [ABSTRACT FROM AUTHOR]

In this article, a decentralized adaptive optimal controller based on the emerging mean-field game (MFG) and self-organizing neural networks (NNs) has been developed for multiagent systems (MASs) with a large population and uncertain dynamics. This design can effectively break the “curse of dimensionality” and reduce the computational complexity by appropriately integrating emerging MFG theory with self-organizing NNs-based reinforcement learning techniques. First, the decentralized optimal control for massive MASs has been formulated into an MFG. To unfold the MFG, the coupled Hamilton–Jacobian–Bellman (HJB) equation and Fokker–Planck–Kolmogorov (FPK) equation needed to be solved simultaneously, which is challenging in real time. Therefore, a novel actor–critic–mass (ACM) structure has been developed along with self-organizing NNs subsequently. In the developed ACM structure, each agent has three NNs, including: 1) mass NN learning the mass MAS’s overall behavior via online estimating the solution of the FPK equation; 2) critic NN obtaining the optimal cost function through learning the HJB equation solution along with time; and 3) actor NN estimating the decentralized optimal control by using the critic and mass NNs along with the optimal control theory. To reduce the NNs’ computational complexity, a self-organizing NN has been adopted and integrated into a developed ACM structure that can adjust the NNs’ architecture based on the NNs’ learning performance and the computation cost. Finally, numerical simulation has been provided to demonstrate the effectiveness of the developed schemes. [ABSTRACT FROM AUTHOR]

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are often also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most $n$ prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We give simple and efficient algorithms to find $n$ rules that generate a partition closest in $L_\infty $ to the desired one. We do the same for a one-sided version of $L_\infty $ which equals to the maximum overload on a server and for a relative version of it. We use our algorithms to evaluate how the expected error changes as a function of the number of rules, the number of servers, and the width of the TCAM. [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]

We formulate and analyze a fundamental downlink transmission scheduling problem in a wireless communication system, composed of a base station and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously due to the broadcast nature of the wireless medium. The base station can choose from a set of transmission strategies, e.g., in terms of combination of data rate and coding scheme, to serve the users. Each request can be served by a subset of transmission strategies. We seek a downlink transmission scheduling algorithm generating maximum aggregated system-wide utility. In this paper, we develop approximation algorithms for the formulated downlink transmission scheduling problem in both offline and online settings. We first establish the NP-hardness of the offline scheduling problem and the approximation hardness and bound of the online scheduling problem in non-preemptive and preemptive-restart models, respectively. We then design approximation algorithms and derive the approximation and competitive ratios of our online and offline scheduling algorithms. Numerical simulations are performed to further evaluate our algorithms in a wide range of network settings. [ABSTRACT FROM AUTHOR]

In multi-tenant clouds, requests need to traverse a set of network functions (NFs) in a specific order, referred to as a service function chain (SFC), for security and business logic issues. Due to workload dynamics, the central controller of a multi-tenant cloud needs to frequently update the SFC routing, so as to optimize various network performance, such as load balancing. To achieve effective SFC routing update, we should consider two critical requirements: system robustness and real-time update. Without considering these two requirements, prior works either result in fragile clouds or suffer from large update delay. In this paper, we propose a robustness-aware real-time SFC routing update (R3-UA) scheme which takes both requirements into consideration. R3-UA pursues robustness-aware real-time routing update through two phases: robust NF instance assignment update and real-time SFC routing update. Two algorithms with bounded approximation ratios are proposed for these two phases, respectively. We implement R3-UA on a real testbed. Both small-scale experimental results and large-scale simulation results show the superior performance of R3-UA compared with other alternatives. [ABSTRACT FROM AUTHOR]

We consider a single-unicast networking scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. We study problems of minimizing peak/average Age-of-Information (AoI) subject to throughput requirements based on a stylized deterministic model in this scenario. The consideration of batch generation and multi-path communication differentiates our AoI study from existing ones. We first show that our AoI minimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. We then prove that minimizing AoI and minimizing maximum delay are “roughly” equivalent, in the sense that any optimal solution of the latter is an approximate solution of the former with bounded optimality loss. We leverage this understanding to design a general approximation framework for our problems. It can build upon any $\alpha $ -approximation algorithm of the maximum delay minimization problem to construct an $(\alpha +\mathsf {c})$ -approximate solution for minimizing AoI. Here $\mathsf {c}$ is a constant depending on the throughput requirements. Furthermore, we show that our results can be extended to the multiple-unicast setting. Simulations over various network topologies validate the effectiveness of our approach. Our results make a major advance to optimizing AoI in multi-path communication, and hence can be of broad interest to the networking research community. [ABSTRACT FROM AUTHOR]

In a multi-tenant cloud, cloud vendors provide services (e.g., elastic load-balancing, virtual private networks) on service nodes for tenants. Thus, the mapping of tenants’ traffic and service nodes is an important issue in multi-tenant clouds. In practice, unreliability of service nodes and uncertainty/dynamics of tenants’ traffic are two critical challenges that affect the tenants’ QoS. However, previous works often ignore the impact of these two challenges, leading to poor system robustness when encountering system accidents. To bridge the gap, this paper studies the problem of robust service mapping in multi-tenant clouds (RSMP). Due to traffic dynamics, we take a two-step approach: service node assignment and tenant traffic scheduling. For service node assignment, we prove its NP-Hardness and analyze its problem difficulty. Then, we propose an efficient algorithm with bounded approximation factors based on randomized rounding and knapsack. For tenant traffic scheduling, we design an approximation algorithm based on fully polynomial time approximation scheme (FPTAS). The proposed algorithm achieves the approximation factor of 2+ $\epsilon $ , where $\epsilon $ is an arbitrarily small value. Both small-scale experimental results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives. [ABSTRACT FROM AUTHOR]

One critical issue for wireless power transfer is to avoid human health impairments caused by electromagnetic radiation (EMR) exposure. The existing studies mainly focus on scheduling wireless chargers so that (expected) EMR at any point in the area does not exceed a threshold $R_t$ R t . Nevertheless, they overlook the EMR jitter that leads to exceeding of $R_t$ R t even if the expected EMR is no more than $R_t$ R t . This paper studies the fundamental problem of RObustly SafE charging for wireless power transfer (ROSE), that is, scheduling the power of chargers so that the charging utility for all rechargeable devices is maximized while the probability that EMR anywhere does not exceed $R_t$ R t is no less than a given confidence. We first build our empirical probabilistic charging model and EMR model. Then, we present EMR approximation and area discretization techniques to formulate ROSE into a Second-Order Cone Program. After that, we propose the first redundant second-order cone constraints reduction algorithm to reduce the computational cost, and therefore obtain a $(1-\epsilon)$ (1 - ε) -approximation centralized algorithm. Further, we propose a $(1-\epsilon)$ (1 - ε) -approximation fully distributed algorithm scalable with network size for ROSE. We conduct both simulation and field experiments, and the results show that our algorithms can outperform comparison algorithms by 480.19 percent. [ABSTRACT FROM AUTHOR]

Sparse approximate inverse (SAI) preconditioner is frequently used to speed up the iteration of fast multipole algorithm when solving electrically large problems. However, its efficiency is unsatisfactory when applied to hybrid fast algorithms for electrically large multiscale problems. In this letter, a fast reconstruction SAI (FRSAI) preconditioner is introduced to improve the convergence of linear equation systems for solving electrically large multiscale problems. The performance of the novel FRSAI preconditioner is illustrated using numerical examples of complex electromagnetic scattering and radiation problems. [ABSTRACT FROM AUTHOR]

To extract important information about the nonlinear signals, this letter makes the utmost of the fitting advantages of Gaussian and polynomial functions, and proposes a nonlinear signal model with broader applications. Then we focus on the parameter estimation issues of the proposed models in the presence of noises. The stability factor recursive algorithm is devised based on the increasing noisy data, which makes full use of the information from the nonlinear signals. Applying the hierarchical identification principle, a two-stage recursive algorithm with higher computational efficiency is developed for the nonlinear signals. The simulation results test the effectiveness of the proposed algorithms from the aspects of estimation accuracy and prediction effect. [ABSTRACT FROM AUTHOR]

Due to the rapid development and wide application of mobile devices, mobile edge computing (MEC) technology improves system performance by offloading vehicle computing tasks to the edges of the network. In order to save device power, shorten transmission delay, save network bandwidth, or shorten execution time, many related works have been proposed. Different from these works under the constraints of system resources, we adopt another method to maximize the admission of mobile users' tasks to meet the service requirements. Compared with these works, this method can allocate and utilize all system resources more effectively and admit as many tasks as possible. Further, we prove that the approximate ratio of its solution to the optimal solution of the problem of maximizing task admission in MEC is bounded. The above claim is verified by the conducted simulations and the simulation results show that there is a small difference between its solution and the optimal one. On the other hand, if the system resources can be increased at a bounded rate, another algorithm is proposed to control the compromise between the overall system performance and the robustness of its obtained solution. [ABSTRACT FROM AUTHOR]

Device activity detection is one main challenge in grant-free massive access, which is recently proposed to support massive machine-type communications (mMTC). Existing solutions for device activity detection fail to consider inter-cell interference generated by massive IoT devices or important prior information on device activities and inter-cell interference. In this paper, given different numbers of observations and network parameters, we consider both non-cooperative device activity detection and cooperative device activity detection in a multi-cell network, consisting of many access points (APs) and IoT devices. Under each activity detection mechanism, we consider the joint maximum likelihood (ML) estimation and joint maximum a posterior probability (MAP) estimation of both device activities and interference powers, utilizing tools from probability, stochastic geometry, and optimization. Each estimation problem is a challenging non-convex problem, and a coordinate descent algorithm is proposed to obtain a stationary point. Each proposed joint ML estimation extends the existing one for a single-cell network by considering the estimation of interference powers, together with the estimation of device activities. Each proposed joint MAP estimation further enhances the corresponding joint ML estimation by exploiting prior distributions of device activities and interference powers. The proposed joint ML estimation and joint MAP estimation under cooperative detection outperform the respective ones under non-cooperative detection at the costs of increasing backhaul burden, knowledge of network parameters, and computational complexities. Numerical results show the substantial gains of the proposed designs over well-known existing designs and reveal the importance of explicit consideration of inter-cell interference, the value of prior information, and the advantage of AP cooperation in device activity detection. [ABSTRACT FROM AUTHOR]

We consider a class of non-convex complex modulus constrained problems (CMCPs), which has many important applications in signal processing for wireless communications, including multicast beamforming and multi-input multi-output detection. Due to the non-convex constraints, traditional optimization-based algorithms either obtain sub-optimal solutions or take exponential complexity to reach the optimum. In this paper, we propose a learning based branch-and-bound (LBB) algorithm for solving the considered CMCPs. LBB regards the search procedure of the global optimal argument-cut based branch-and-bound (AC-BB) algorithm as a sequential decision problem in a binary tree and learns the optimal pruning policy via supervised learning. We first propose to apply ensemble learning to train multiple classifiers and then combine them to achieve better performance. To tackle the imbalanced issue, we propose an undersampling-supervised learning method to sample several balanced subsets and train a classifier on each of them. We also show that the computational complexity of LBB is determined by the depth of the binary tree and give its expression in the worst case. Finally, we validate the proposed LBB with two classic problems in wireless communications, i.e., multicast beamforming and MIMO detection. Numerical results show that LBB runs significantly faster than AC-BB while achieving nearly the same optimal performance. [ABSTRACT FROM AUTHOR]

Streaming platforms, like Netflix and YouTube, strive to offer high streaming quality (SQ), in terms of bitrate, delays, etc., to their users. Meanwhile, a significant share of content consumption of these platforms is heavily influenced by recommendations. In this setting, the user’s overall experience is a product of both the user’s interest in a recommended content, i.e., the recommendation quality (RQ), and the SQ of this content. However, network decisions (like caching) that affect the SQ are usually made without considering the recommender’s actions. Likewise, recommendations are chosen independently of the potential delivery quality. In this paper, we define a metric of streaming experience (MoSE) that captures the fundamental tradeoff between the SQ and RQ. We aim to jointly optimize caching and recommendations in a generic network of caches, with the objective of maximizing this metric. This is in line with the recent trend for content providers to simultaneously act as Content Delivery Network owners, implying that the same entity may handle both caching and recommendation decisions. We formulate this joint optimization problem and prove that it can be approximated up to a constant factor. To the best of our knowledge, this is the first polynomial algorithm to achieve a constant approximation ratio for the joint problem. Moreover, our numerical experiments show important performance gains of our algorithm over baseline schemes and existing algorithms in the literature. [ABSTRACT FROM AUTHOR]

Efficient and consistent update of the network routing rules is a challenging task that significantly affects the performance, correctness, and security of Software-Defined Networks (SDN). In this work, we consider the problem of minimizing the makespan of updating the routing rules in SDNs, while guaranteeing three crucial consistency requirements: (1) WayPoint Enforcement, (2) Loop Freedom, and (3) Conflict Freedom. This problem is known to be NP-hard, and thus we focus on designing approximate algorithms that run in polynomial time without incurring TCAM storage overhead. To compute consistent rule-update schedules, we propose two algorithms, called TimeX and RMS. TimeX employs the solution of a linear program (LP) to address the makespan minimization goal systematically. RMS is an LP-independent heuristic that provides higher scalability. We demonstrate and utilize a property of rule-updates, called reversibility, to reduce the makespan in RMS. Extensive simulations show that our algorithms reduce the makespan by 2% to 18% and attain a 4.9 $\times$ speedup compared to previous studies. Moreover, Mininet experiments reveal that the proposed algorithms can mitigate the transient congestion caused by conflicting flows. [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]

To minimize operating expenses (OPEX) and enhance flexibility for network service provisioning, network function virtualization (NFV) is used to chain an ordered sequence of virtualized network functions (VNFs), also known as service function chain (SFC), which can be placed on commodity servers. As a highly complementary to NFV, software-defined networking (SDN) can offer an agile way of VNF orchestration with the capability of fine-granularity network control over flows. However, one-step migration to SDN is impossible in ISP networks. Thus, in this paper we resort to hybrid SDN to implement SFC provisioning. By jointly optimizing SDN deployment that largely determines capital expenditures (CAPEX) and VNF placement that decides OPEX, we manage to make a tradeoff between CAPEX and OPEX, and to find out an appropriate SDN deployment rate for network operator. We first formulate the problem as an integer linear programming (ILP) model $\boldsymbol {P}$ , then, reformulate it with column generation technique and decomposition theory to develop a distributed approximation algorithm CGPD which obtains a tight upper bound of optimal solution to $\boldsymbol {P}$. In order to better decrease CAPEX, a dynamic programming-based heuristic EOES giving importance to effective resource sharing is further designed based on a hidden Markov model. The simulation results indicate that, the difference between $\boldsymbol {P}$ and CGPD is marginal. CGPD outperforms EOES in terms of total cost, average delay and bandwidth utilization, and EOES on the other hand demands 20% SDN deployment rate which is half of that of CGPD. [ABSTRACT FROM AUTHOR]

Generation Expansion Planning (GEP) can inform regulation, electricity market design, and regional system planning by identifying adaptive investment strategies. Relevant uncertainties include hourly variability in load and renewable generation and decadal-scale uncertainty in technology, markets, and regulation. A multi-stage and multi-scale stochastic GEP model that represents these uncertainties at sufficient resolution becomes intractable. We present an approach for representing this multi-scale uncertainty, and compare it to existing methods, applied to a two-stage stochastic GEP model with a cumulative carbon emission target. For long-term uncertainty, we compare partitioning methods, which reduce the number of decision variables but retain all scenarios, to representative scenario methods, which retain only a subset of the original scenarios. For short-term uncertainty, we compare methods that select representative weeks based on distance metrics in the parameter space to methods that use the covariance of outcomes across feasible decisions to select weeks. We find that scenario reduction methods struggle to find the appropriate investment levels for variable renewable generation and consequently produce more costly plans than scenario partitioning methods. While simple approximating methods perform well with larger models, covariance-based approximations have the best performance overall. [ABSTRACT FROM AUTHOR]

Gas-fired generators, with their ability to quickly ramp up and down their electricity production, play an important role in managing renewable energy variability. However, these changes in electricity production translate into variability in the consumption of natural gas, and propagation of uncertainty from the electric grid to the natural gas system. To ensure that both systems are operating safely, there is an increasing need for coordination and uncertainty management among the electricity and gas networks. A challenging aspect of this coordination is the consideration of natural gas dynamics, which play an important role in intra-day operation, but give rise to a set of non-linear and non-convex equations that are hard to optimize even in the deterministic case. Ideally, the problem is formulated as a stochastic problem but many conventional methods for stochastic optimization are numerically intractable because they either incorporate a large number of scenarios directly or require the underlying problem to be convex. To address these challenges, we propose using a Stochastic Hybrid Approximation algorithm to more efficiently solve these problems and investigate the efficacy of several different variants of this algorithm. Our case study demonstrates that the proposed technique is able to quickly obtain high quality solutions and outperforms existing benchmarks such as Generalized Benders Decomposition. We demonstrate that coordinated uncertainty management that accounts for the gas system can significantly reduce both electric and gas system load shed in stressed conditions. [ABSTRACT FROM AUTHOR]

This paper considers a resource allocation problem where several Internet-of-Things (IoT) devices send data to a base station (BS) with or without the help of the reconfigurable intelligent surface (RIS) assisted cellular network. The objective is to maximize the sum rate of all IoT devices by finding the optimal RIS and spreading factor (SF) for each device. Since these IoT devices lack prior information of the RISs or the channel state information (CSI), a distributed resource allocation framework with low complexity and learning features is required to achieve this goal. Therefore, we model this problem as a two-stage multi-player multi-armed bandit (MPMAB) framework to learn the optimal RIS and SF sequentially. Then, we put forth an exploration and exploitation boosting (E2Boost) algorithm to solve this two-stage MPMAB problem by combining the $\epsilon $ -greedy algorithm, Thompson sampling (TS) algorithm, and non-cooperation game method. We derive an upper regret bound for the proposed algorithm, i.e., $\mathcal {O}(\log ^{1+\delta }_{2} T)$ , increasing logarithmically with the time horizon $T$. Numerical results show that the E2Boost algorithm has the best performance among the existing methods and exhibits a fast convergence rate. More importantly, the proposed algorithm is not sensitive to the number of combinations of the RISs and SFs thanks to the two-stage allocation mechanism, which can benefit the high-density networks. [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]

Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP–hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this article, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art. [ABSTRACT FROM AUTHOR]

Despite being commonly used in big-data analytics; the outcome of dimensionality reduction remains a black-box to most of its users. Understanding the quality of a low-dimensional embedding is important as not only it enables trust in the transformed data, but it can also help to select the most appropriate dimensionality reduction algorithm in a given scenario. As existing research primarily focuses on the visual exploration of embeddings, there is still a need for enhancing interpretability of such algorithms. To bridge this gap, we propose two novel interactive explanation techniques for low-dimensional embeddings obtained from any dimensionality reduction algorithm. The first technique LAPS produces a local approximation of the neighborhood structure to generate interpretable explanations on the preserved locality for a single instance. The second method GAPS explains the retained global structure of a high-dimensional dataset in its embedding, by combining non-redundant local-approximations from a coarse discretization of the projection space. We demonstrate the applicability of the proposed techniques using 16 real-life tabular, text, image, and audio datasets. Our extensive experimental evaluation shows the utility of the proposed techniques in interpreting the quality of low-dimensional embeddings, as well as with selecting the most suitable dimensionality reduction algorithm for any given dataset. [ABSTRACT FROM AUTHOR]

Density Peak Clustering (DPC), a popular density-based clustering approach, has received considerable attention from the research community primarily due to its simplicity and fewer-parameter requirement. However, the resultant clusters obtained using DPC are influenced by the sensitive parameter $d_c$ d c , which depends on data distribution and requirements of different users. Besides, the original DPC algorithm requires visiting a large number of objects, making it slow. To this end, this paper investigates index-based solutions for DPC. Specifically, we propose two list-based index methods viz. (i) a simple List Index, and (ii) an advanced Cumulative Histogram Index. Efficient query algorithms are proposed for these indices which significantly avoids irrelevant comparisons at the cost of space. For memory-constrained systems, we further introduce an approximate solution to the above indices which allows substantial reduction in the space cost, provided that slight inaccuracies are admissible. Furthermore, owing to considerably lower memory requirements of existing tree-based index structures, we also present effective pruning techniques and efficient query algorithms to support DPC using the popular Quadtree Index and R-tree Index. Finally, we practically evaluate all the above indices and present the findings and results, obtained from a set of extensive experiments on six synthetic and real datasets. The experimental insights obtained can help to guide in selecting a befitting index. [ABSTRACT FROM AUTHOR]

We analyze the orthogonal greedy algorithm when applied to dictionaries $\mathbb {D}$ whose convex hull has small entropy. We show that if the metric entropy of the convex hull of $\mathbb {D}$ decays at a rate of $O\left({n^{-\frac {1}{2}-\alpha }}\right)$ for $\alpha > 0$ , then the orthogonal greedy algorithm converges at the same rate on the variation space of $\mathbb {D}$. This improves upon the well-known $O\left({n^{-\frac {1}{2}}}\right)$ convergence rate of the orthogonal greedy algorithm in many cases, most notably for dictionaries corresponding to shallow neural networks. These results hold under no additional assumptions on the dictionary beyond the decay rate of the entropy of its convex hull. In addition, they are robust to noise in the target function and can be extended to convergence rates on the interpolation spaces of the variation norm. We show empirically that the predicted rates are obtained for the dictionary corresponding to shallow neural networks with Heaviside activation function in two dimensions. Finally, we show that these improved rates are sharp and prove a negative result showing that the iterates generated by the orthogonal greedy algorithm cannot in general be bounded in the variation norm of $\mathbb {D}$. [ABSTRACT FROM AUTHOR]

With proliferation of fifth generation (5G) new radio (NR) technology, it is expected to meet the requirement of diverse traffic demands. We have designed a coordinated multi-point (CoMP) enhanced flexible multi-numerology (MN) for 5G-NR networks to improve the network performance in terms of throughput and latency. We have proposed a CoMP enhanced joint subcarrier and power allocation (CESP) scheme which aims at maximizing sum rate under the considerations of transmit power limitation and guaranteed quality-of-service (QoS) including throughput and latency restrictions. By employing difference of two concave functions (D.C.) approximation and abstract Lagrangian duality method, we theoretically transform the original non-convex nonlinear problem into a solvable maximization problem. Moreover, the convergence of our proposed CESP algorithm with D.C. approximation is analytically derived with proofs, and is further validated via numerical results. Simulation results have demonstrated that our proposed CESP algorithm outperforms the conventional non-CoMP and single-numerology mechanisms along with other existing benchmarks in terms of lower latency and higher throughput under the scenarios of center and edge users. [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]

Existing wideband beampattern synthesis methods usually require multiple beamformers, each corresponding to one frequency bin, which results in excessive resource consumption in engineering practice. To alleviate the resource consumption of wideband array beamforming, we propose a novel time-domain wideband digital beamformer that can control the beam shape over the whole bandwidth for interference mitigation by using only one set of amplitude–phase weights and integer time delay filters. To tackle the resultant optimization problem, two effective algorithms are introduced, and both can solve the problem within polynomial time. One is an alternating optimization algorithm that decomposes the original problem into multiple tractable subproblems iteratively. The other is the convex approximation algorithm that transforms the original problem into a series of second-order cone programming problems iteratively. The two algorithms exhibit their respective advantages in terms of convergence and computational complexity. Extensive numerical examples are presented to evaluate the proposed time-domain wideband beamforming strategy, highlighting that it can form a deep notch in any interested spatial–spectral region to suppress the strong interferences. [ABSTRACT FROM AUTHOR]