Search

In this paper, we extend the bilinear generalized approximate message passing (BiG-AMP) approach, originally proposed for high-dimensional generalized bilinear regression, to the multi-layer case for the handling of cascaded problem such as matrix-factorization problem arising in relay communication among others. Assuming statistically independent matrix entries with known priors, the new algorithm called ML-BiGAMP could approximate the general sum-product loopy belief propagation (LBP) in the high-dimensional limit enjoying a substantial reduction in computational complexity. We demonstrate that, in large system limit, the asymptotic MSE performance of ML-BiGAMP could be fully characterized via a set of simple one-dimensional equations termed state evolution (SE). We establish that the asymptotic MSE predicted by ML-BiGAMP’ SE matches perfectly the exact MMSE predicted by the replica method, which is well-known to be Bayes-optimal but infeasible in practice. This consistency indicates that the ML-BiGAMP may still retain the same Bayes-optimal performance as the MMSE estimator in high-dimensional applications, although ML-BiGAMP's computational burden is far lower. As an illustrative example of the general ML-BiGAMP, we provide a detector design that could estimate the channel fading and the data symbols jointly with high precision for the two-hop amplify-and-forward relay communication systems. [ABSTRACT FROM AUTHOR]

Novel sparse reconstruction algorithms are proposed for beamspace channel estimation in massive multiple-input multiple-output systems. The proposed algorithms minimize a least-squares objective having a nonconvex regularizer. This regularizer removes the penalties on a few large-magnitude elements from the conventional $\ell _{1}$ -norm regularizer, and thus it only forces penalties on the remaining elements that are expected to be zeros. Accurate and fast reconstructions can be achieved by performing gradient projection updates within the framework of difference of convex functions (DC) programming. A double-loop algorithm and a single-loop algorithm are proposed via different DC decompositions, and these two algorithms have distinct computational complexities and convergence rates. An extension algorithm is further proposed by designing new step sizes for the single-loop algorithm. The extension algorithm has a faster convergence rate and can achieve approximately the same level of accuracy as the proposed double-loop algorithm. Numerical results show significant advantages of the proposed algorithms over existing reconstruction algorithms in terms of reconstruction accuracies and runtimes. Compared with the benchmark channel estimation approaches, the proposed algorithms can achieve smaller channel reconstruction error and higher achievable spectral efficiency. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 , 3 } which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of G with weight h (V) = ∑ p ∈ V h (p) : (C1) For every vertex u ∈ V if h (u) = 0 , then u has m (m ≥ 1) neighbors such that whose sum is at least 3, and if h (u) = 1 , then u has n (n ≥ 1) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph G , the smallest possible weight of a TR3DF of G denoted γ t { R 3 } (G) is known as the total Roman { 3 } -domination number of G. The problem of determining γ t { R 3 } (G) of a graph G is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if G has a TR3DF of weight at most l for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a 3 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for the MTR3DP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless NP ⊆ DTIME (| V | O (log log | V |)). Next, we show that MTR3DP is APX-complete for graphs with Δ = 4. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. [ABSTRACT FROM AUTHOR]

The length of a tree-decomposition of a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of a graph cannot be approximated up to a factor less than 3/2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering the next natural superclass of outerplanar graphs, namely the one of series-parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjoint paths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up to a factor 3/2 in series-parallel graphs. Our main result is a polynomial-time algorithm for deciding whether a series-parallel graph has treelength at most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of infinite families of forbidden isometric subgraphs. [ABSTRACT FROM AUTHOR]

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in contrast to practice where data is inherently dynamic. A temporal graph has an edge set that changes over time. We present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and integers k and Δ, we ask for a coloring sequence with at most k colors for each vertex such that in every time window of Δ consecutive time steps, in which an edge is present, this edge is properly colored at least once. We thoroughly investigate the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. [ABSTRACT FROM AUTHOR]

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability. [ABSTRACT FROM AUTHOR]

Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions ("contigs") are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomial-time and NP -hard special cases like planarity or bounded degree. Finally, we propose two polynomial-time approximation algorithms according to cut/weight score. [ABSTRACT FROM AUTHOR]

In this study, we consider a new customer choice model which we call the single transition choice model. In this model, there is a universe of products and customers arrive at each product with a certain probability. If the arrived product is unavailable, then the seller can recommend a subset of available products and the customer will purchase one of the recommended products or choose not to purchase with certain transition probabilities. The distinguishing features of the model are that the seller can control which products to recommend depending on the arrived product, and each customer either purchases a product or leaves the market after one transition. We study the assortment optimization problem under this model. Particularly, we show that it is NP‐Hard even if the customer can transition from each product to at most two products. Despite the computational complexity, we provide polynomial time algorithms or approximation algorithms for several special cases, such as when the customer can only transition from each product to at most a given number of products and the size of each recommended set is bounded. Our approximation algorithms are developed by invoking the submodularity arguments, or connecting the problem with maximum constraint satisfaction problem and applying randomized rounding techniques to its semidefinite programming relaxation. We also provide a tight worst‐case performance bound for revenue‐ordered assortments. In addition, we propose a compact mixed‐integer program formulation, which is efficient for moderate size problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Directed acyclic graphs are often used to model situations and problems in real life. If we consider the topological ordering of a graph as a process of arranging the vertices in the best possible way considering the constraints caused by the direction of edges, then it makes sense to try to optimize this process by minimizing the distances between vertices in the ordering. For this purpose, we define measures based on distances between vertices in the topological ordering that allow us to construct a graph with optimal topological ordering regarding a specific measure thus minimizing the complexity of the system represented by the graph. We explore minimal and maximal values of the defined measures and comment on the topology of graphs for which maximal and minimal values are obtained. Potentially, the proved bounds could be used to benchmark existing algorithms, devise new approximation algorithms or branch-and-bound schemas for some scheduling problems that are usually of hard computational complexity. [ABSTRACT FROM AUTHOR]

Persuasion, defined as the act of exploiting an informational advantage in order to inuence the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the U.S. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow [Am. Econ. Rev., 101 (2011), pp. 2590-2615]. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with an a priori unknown payoff, and the sender has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. When the payoffs of various actions follow a joint distribution (the common prior), the sender's problem is nontrivial, and its computational complexity depends on the representation of this prior. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are independently and identically distributed (i.i.d.) and given explicitly, we exhibit a polynomial-time (exact) algorithmic solution, and a "simple" (1-1=e)-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but nonidentical with marginal distributions given explicitly, we show that it is #P-hard to compute the optimal expected sender utility. In doing so, we rule out a generalized Border's theorem, in the sense of Gopalan, Nisan, and Roughgarden [Public projects, boolean functions, and the borders of Border's theorem, in Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, ACM, New York, 2015, p. 395], for this setting. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bicriteria guarantee. Our FPTAS is based on Monte Carlo sampling, and its analysis relies on the principle of deferred decisions. Moreover, we show that this result is the best possible in the black-box model for information-theoretic reasons. [ABSTRACT FROM AUTHOR]

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

• The approximability and the computational complexity of the Maximum Happy Set problem (MaxHS) are studied. • A (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ is presented. • The approximation ratio is improved to Δ if the maximum degree Δ is a constant. • The polynomial-time solvability of MaxHS on block/interval graphs is proved. • The NP-hardness of MaxHS on bipartite/cubic graphs is proved. In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard. [ABSTRACT FROM AUTHOR]

We study a single-machine lot-sizing problem, where n types of products need to be scheduled on the machine. Each product is associated with a constant demand rate, maximum production rate and inventory costs per time unit. Every time when the machine switches production between products, sequencing costs are incurred. These sequencing costs depend both on the product the machine just produced and on the product the machine is about to produce. The goal is to find a cyclic schedule minimizing total average costs, subject to the condition that all demands are satisfied. We establish the complexity of the problem, and we prove a number of structural properties largely characterizing optimal solutions. Moreover, we present two algorithms approximating the optimal schedules by augmenting the problem input. Due to the high-multiplicity setting, even trivial cases of the corresponding conventional counterparts become highly non-trivial with respect to the output sizes and computational complexity, even without sequencing costs. In particular, the length of an optimal solution can be exponential in the input size of the problem. Nevertheless, our approximation algorithms produce schedules of a polynomial length and with a good quality compared to the optimal schedules of exponential length. [ABSTRACT FROM AUTHOR]

Sequential attack detection in a distributed sensor network is considered, where each sensor successively produces one-bit quantized samples of a desired deterministic scalar parameter corrupted by additive noise. The unknown parameters in the pre-attack and post-attack models, namely the desired parameter to be estimated and the injected malicious data at the attacked sensors pose a significant challenge for designing a computationally efficient scheme for each sensor to detect the occurrence of attacks by only using local communication with neighboring sensors. The generalized Cumulative Sum (GCUSUM) algorithm is considered, which replaces the unknown parameters with their maximum likelihood estimates in the CUSUM test statistic. For the problem under consideration, a sufficient condition is provided under which the expected false alarm period of the GCUSUM can be guaranteed to be larger than any given value. Next, we consider the distributed implementation of the GCUSUM. We first propose an alternative test statistic which is asymptotically equivalent to that of GCUSUM. Then based on the proposed alternative test statistic and running consensus algorithms, we propose a distributed approximate GCUSUM algorithm which significantly reduce the prohibitively high computational complexity of the centralized GCUSUM. Numerical results show that the proposed distributed approximate GCUSUM algorithm can provide a performance that is comparable to the centralized GCUSUM. [ABSTRACT FROM AUTHOR]

The transportation problem is a fundamental problem in operations research, where items need to be transported from supply nodes (each with a given supply) to demand nodes (each with a given demand) in the cheapest possible way. Here, we are interested in a generalization of the transportation problem where, each supply node has a (possibly empty) set of conflicting pairs of demand nodes, and each demand node a (possibly empty) set of conflicting pairs of supply nodes. Each supply node may only send supply to at most one demand node of each conflicting pair. Likewise, each demand node may only receive supply from at most one supply node of each conflicting pair. We call the resulting problem the transportation problem with conflicts (TPC). We show that the complexity of TPC depends upon the structure of the so-called conflict graph that follows from the conflicting pairs. More concrete, we show that for many graph-classes the corresponding TPC remains NP-hard, and for some special cases we derive constant factor approximation algorithms. [ABSTRACT FROM AUTHOR]

Optimization theory assisted algorithms have received great attention for precoding design in multiuser multiple-input multiple-output (MU-MIMO) systems. Although the resultant optimization algorithms are able to provide excellent performance, they generally require considerable computational complexity, which gets in the way of their practical application in real-time systems. In this work, in order to address this issue, we first propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed in matrix form to better solve the problems in communication systems. Then, we implement the proposed deep-unfolding framework to solve the sum-rate maximization problem for precoding design in MU-MIMO systems. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. Specifically, the iterative WMMSE algorithm is unfolded into a layer-wise structure, where a number of trainable parameters are introduced to replace the high-complexity operations in the forward propagation. To train the network, a generalized chain rule of the IAIDNN is proposed to depict the recurrence relation of gradients between two adjacent layers in the back propagation. Moreover, we discuss the computational complexity and generalization ability of the proposed scheme. Simulation results show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity. [ABSTRACT FROM AUTHOR]

In the Multi-Spreader Crane Scheduling Problem (MSCSP), containers with identical dimensions but variable weights are arranged along a grid. A multi-spreader crane is used to lift all the containers. The crane has m > 1 modes. When it is in the p th mode, the crane can remove p adjacent containers along the same row at the same time as long as the total weight of the containers does not exceed the loading capacity κ p. Such a lift takes h p minutes. It also takes c p , q minutes for the crane to switch from mode p to q when p ≠ q. The goal is to find a crane lift sequence so that the total time it takes to lift all the containers is minimized. This paper investigates the computational complexity of MSCSP. First, we establish a connection between greedy crane lift sequences and supersequences. We then prove that MSCSP is NP-hard when the crane has three or more modes by a reduction from a version of the Shortest Common Supersequence problem. Lastly, we investigate two problems that arise naturally when heuristics are used to solve MSCSP. We show that one can be solved using dynamic programming while the other remains computationally hard. We also provide an approximation algorithm that behaves nicely when the changeover times are not much larger than the lifting times of the crane. [ABSTRACT FROM AUTHOR]

The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments. [ABSTRACT FROM AUTHOR]

The problem of attaining energy efficiency in distributed systems is of importance, but a general, non-domain-specific theory of energy-minimal scheduling is far from developed. In this paper, we classify the problems of energy-minimal scheduling and present theoretical foundations of the same. We derive results concerning energy-minimal scheduling of independent jobs in a distributed system with functionally similar machines with different working and idle power ratings. The machines considered in our system can have identical as well as different speeds. If the jobs can be divided into arbitrary parts, we show that the minimum-energy schedule can be generated in linear time and give exact scheduling algorithms. For the cases where jobs are non-divisible, we prove that the scheduling problems are NP-hard and also give approximation algorithms for the same along with their bounds. [ABSTRACT FROM AUTHOR]

A central problem in graph mining is finding dense subgraphs, with several applications in different fields, a notable example being identifying communities. While a lot of effort has been put in the problem of finding a single dense subgraph, only recently the focus has been shifted to the problem of finding a set of densest subgraphs. An approach introduced to find possible overlapping subgraphs is the Top-k-Overlapping Densest Subgraphs problem. Given an integer k ≥ 1 and a parameter λ > 0 , the goal of this problem is to find a set of k dense subgraphs that may share some vertices. The objective function to be maximized takes into account the density of the subgraphs, the parameter λ and the distance between each pair of subgraphs in the solution. The Top-k-Overlapping Densest Subgraphs problem has been shown to admit a 1 10 -factor approximation algorithm. Furthermore, the computational complexity of the problem has been left open. In this paper, we present contributions concerning the approximability and the computational complexity of the problem. For the approximability, we present approximation algorithms that improve the approximation factor to 1 2 , when k is smaller than the number of vertices in the graph, and to 2 3 , when k is a constant. For the computational complexity, we show that the problem is NP-hard even when k = 3 . [ABSTRACT FROM AUTHOR]

We consider scheduling on identical and unrelated parallel machines with job assignment restrictions. These problems are NP-hard and they do not admit polynomial time approximation algorithms with approximation ratios smaller than 1.5 unless P=NP. However, if we impose limitations on the set of machines that can process a job, the problem sometimes becomes easier in the sense that algorithms with approximation ratios better than 1.5 exist. We introduce a graph framework based on the assignment restrictions and study the computational complexity of the scheduling problem with respect to structural properties of the resulting graphs, in particular, their tree- and cliquewidth. We identify cases that admit polynomial time approximation schemes or FPT algorithms generalizing and extending previous results in this area. [ABSTRACT FROM AUTHOR]

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

When dealing with complex nonlinear signals in intelligent system, by defining the inner product of two data vectors in the feature space, the kernel function can reflect the nonlinear mapping relationship between reproducing kernel Hilbert space (RKHS) and original data space. Therefore, by implementing classical linear adaptive filtering in RKHS space, the filtering operation can be expressed as a special relation of inner product with kernel function, which is referred to as “kernel trick.” As long as these algorithms can be expressed in the form of inner product, not only the convex least squares problem can be solved iteratively, but also the nonlinear adaptive filtering algorithms can be obtained, which have both general approximation characteristics and convexity. Therefore, the combination of kernel method and adaptive filtering algorithm is realized. On the other hand, since the Gram matrix is used, the dimension of kernel adaptive algorithm is determined by the number of data samples. When the number of observation sample point is increasing, the size of the state space increases exponentially with the growth of the dimension. Thereby, the kernel adaptive algorithm should solve the problem of online sparsification to avoid “curse of dimensionality.” As part II, based on online sparse kernel learning and the classical adaptive filtering algorithm, the kernel adaptive algorithms and online sparse algorithms are investigated in this paper. The main works of this paper have two aspects. First, combined with classical adaptive algorithm and kernel feature mapping, this paper investigates the basic concept of kernel adaptive algorithm and the realization mechanism of four kernel adaptive algorithm intensively: 1) kernel least mean squares; 2) kernel recursive least squares; 3) kernel affine projection algorithm; and 4) kernel principal component analysis. Second, in order to reduce the computational complexity, this paper studies some online sparse algorithms which include novel criterion, approximate linear dependency, sliding window, coherence criterion, surprise criterion, and so on. Finally, this paper summarizes the essence of existing conclusions of above algorithms and perspectives the future research direction. [ABSTRACT FROM AUTHOR]

Adaptive exponential functional link network (AEFLN) is a recently introduced linear-in-the-parameters nonlinear filter. In an attempt to improve the performance of AEFLN, an improved AEFLN (IAEFLN) which employs independent decay rates for each exponentially varying sinusoidal basis function, has been proposed in this brief. The update rules for the filter weights as well as the decay parameter vector has been derived. To further reduce the computational complexity of the proposed network, without sacrificing performance, two approximate versions of IAEFLN, namely approximate 1 IAEFLN (Apx1-IAEFLN) and approximate 2 IAEFLN (Apx2-IAEFLN) has been developed and their corresponding update rules have been derived. Bounds on learning rates have also been derived and simulation study shows improved convergence behaviour of the proposed IAEFLN over AEFLN. The approximate versions achieve similar convergence performance as that of IAEFLN, at a lower computational load. [ABSTRACT FROM AUTHOR]

We consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on whether the server eventually needs to return to the origin or not. While online TSP on the line is a very natural online problem that was introduced more than two decades ago, no tight competitive analysis was known to date. We settle this problem by providing tight bounds on the competitive ratios for both the closed and the open variant of the problem. In particular, for closed online TSP, we provide a 1.64-competitive algorithm, thus matching a known lower bound. For open online TSP, we give a new upper bound as well as a matching lower bound that establish the remarkable competitive ratio of 2.04. Additionally, we consider the online Dial-A-Ride problem on the line, where each request needs to be transported to a specified destination. We provide an improved non-preemptive lower bound of 1.75 for this setting, as well as an improved preemptive algorithm with competitive ratio 2.41. Finally, we generalize known and give new complexity results for the underlying offline problems. In particular, we give an algorithm with running time O(n²) for closed offline TSP on the line with release dates and show that both variants of offline Dial-A-Ride on the line are NP-hard for any capacity c ≥ 2 of the server. [ABSTRACT FROM AUTHOR]

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In the conservative case (where all nonnegative unary functions are available), we show that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard to approximate as any problem in #P. Furthermore, we show that any nontrivial functional clone (in a sense that will be made precise) contains the binary function "implies". As a consequence, in the conservative case, all nontrivial counting CSPs are as hard to approximate as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the "implies" clone is equivalent to the clone of lsm functions. We use the Möbius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available. [ABSTRACT FROM AUTHOR]

Block sparse Bayesian learning (BSBL) has been widely used in inverse synthetic aperture radar (ISAR) imaging, which significantly improves the imaging performance by exploiting the sparse pattern information of ISAR images. However, the conventional Bayesian learning algorithm has high computational complexity, which hinders its applications to real-time processing of radar imaging. The approximate message passing (AMP) can be used to obtain a low complexity implementation of sparse Bayesian learning (SBL). However, AMP suffers from performance losses and even diverges in the case of high-Doppler resolution ISAR imaging where the measurement matrix can be highly correlated. To solve this problem, we propose a fast pattern coupled SBL ISAR imaging algorithm based on approximate message passing with unitary transformation (UTAMP). First, the estimates of the hyperparameters of sparse vector are obtained through UTAMP based SBL, and then nearest neighbor hyperparameters are coupled and updated for next iteration. With low complexity, the proposed algorithm can effectively exploit the sparse pattern information of ISAR images, and exhibits excellent convergence and imaging performance. Both simulation and real data experiments are carried out to verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose transmission point selection algorithms to provide lower service time between an application server to end users by selecting the transmission point used by a newly identified metric, i.e., service latency. In particular, the proposed ordered service latency-based transmission point selection algorithm is beneficial in a sense that it does not increase average service time but decrease the maximum service time although it brings additional computational complexity slightly. We also provide the performance bounds with proven approximation ratios and verify that the proposed algorithm achieves lower maximum service time without degrading the average service time as well as waiting time through simulations in practical environments. [ABSTRACT FROM AUTHOR]

This work deals with the robust maximum weighted independent set problem, i.e. finding a subset of graph vertices that are not adjacent to each other and whose sum of weights is as large as possible. Uncertainty in problem formulation is restricted to vertex weights and expressed explicitly by a finite set of scenarios. Three criteria of robustness are considered: absolute robustness (max-min), robust deviation (min-max regret), and relative robustness (relative min-max regret). Since the conventional maximum weighted independent set problem is already NP-hard, finding the exact solution of its robust counterpart should obviously have a prohibitive computational complexity. Therefore, we propose an approximate algorithm for solving the considered robust problem, which is based on evolutionary computing and on various crossover and mutation operators. The algorithm is experimentally evaluated on appropriate problem instances. It is shown that satisfactory solutions can be obtained for any of the three robustness criteria in reasonable time. [ABSTRACT FROM AUTHOR]

Device-to-Device (D2D) communications incorporated with content caching have been regarded as a promising way to offload the cellular traffic data. In this paper, the caching strategy is investigated to maximize the D2D offloading gain with the comprehensive consideration of user collaborative characteristics as well as the physical transmission conditions. Specifically, for a given content, the number of interested users in different groups is different, and users always ask the most trustworthy user in proximity for D2D transmissions. An analytical expression of the D2D success probability is first derived, which represents the probability that the received signal to interference ratio is no less than a given threshold. As the formulated problem is nonconvex, the optimal caching strategy for the special unbiased case is derived in a closed form, and a numerical searching algorithm is proposed to obtain the globally optimal solution for the general case. To reduce the computational complexity, an iterative algorithm based on the asymptotic approximation of the D2D success probability is proposed to obtain the solution that satisfies the Karush-Kuhn-Tucker conditions. The simulation results verify the effectiveness of the analytical results and show that the proposed algorithm outperforms the existing schemes in terms of offloading gain. [ABSTRACT FROM AUTHOR]

A method to find the minimized state machine cover of live and safe Petri nets (PNs) is proposed in this paper. It is required that a cover be obtained in some implementation methods of PN-based control algorithms and other applications such as data mining. Most of the known methods of its computation have at least exponential time and space complexity; this is true not only for the methods which guarantee a minimal cover is obtained but also for some methods of finding approximate solutions. The proposed algorithm is an approximation algorithm and has polynomial computational complexity. The experimental verification shows a very high efficiency of the presented technique. The proposed method is especially valuable in the case of large systems where a solution is obtained hundreds of times quicker than by other methods. [ABSTRACT FROM AUTHOR]

Recently, the gradient based constrained maximum correntropy criterion (GCMCC) algorithm has received considerable attention since it provides superior performance to the traditional methods and is robust to the non-Gaussian noise. However, the convergence of GCMCC algorithm depends on the learning rate. With a large learning rate, GCMCC converges fast but achieves a high steady state mean square deviation (MSD), and vice versa. To balance the convergence rate and the MSD, we propose a novel recursive CMCC (RCMCC) algorithm in this brief by utilizing the matrix inversion lemma. Furthermore, we provide a computationally efficient version of RCMCC (ERCMCC) algorithm by using some approximations. More importantly, we provide the convergence analysis of the RCMCC algorithm, and derive the stability condition and theoretical MSD. The theoretical analysis and superiorities of RCMCC and ERCMCC are validated by simulations. [ABSTRACT FROM AUTHOR]

We introduce the Chinese deliveryman problem where the goal of the deliveryman is to visit every house in his neighborhood such that the average time of arrival is minimized. We show that, in contrast to the well-known Chinese postman problem, the Chinese deliveryman problem is APX-hard in general and NP-hard for planar graphs. We give a simple 2 -approximation for undirected graphs and a 4 / 3-approximation for 2-edge connected graphs. We observe that there is a PTAS for planar graphs and that depth first search is optimal for trees. [ABSTRACT FROM AUTHOR]

Aiming at the dynamic uncertainty and prediction accuracy of security situation prediction in complex cloud network environment, a prediction model of cloud security situation based on evolutionary functional network is proposed. Firstly, the evolutionary functional network model is constructed by combining the evolutionary algorithm with the functional network, which solves the problem of basis function selection and basis function coefficient correction of the prediction model. Secondly, the stochastic approximation algorithm is used to process and comprehend the cloud security situation elements, and the computational complexity of the prediction model is reduced by the dimensionality reduction method. Finally, by constructing the credibility matrix of the uncertain influence relationship of security situation elements, we use the multivariate non-linear regression algorithm to predict the cloud security situation. The simulation results show that compared with BP model and RAN-RBF model, the prediction accuracy of the proposed model is improved by 8.2% and 6.9% respectively, and the convergence efficiency is improved by 12.3% and 10.8% respectively. [ABSTRACT FROM AUTHOR]

Synthesis of unequally spaced arrays with uniform excitation is considered in this article. An iterative method based on second-order cone programming is developed to search the geometry with local optimum peak sidelobe level (PSLL), which is valid for arrays of different scale regardless of geometry constraints like centrosymmetry and minimum separation. By statistical analysis and comparison with other methods, it is verified that the computational complexity of the proposed method is only related to the dimension of optimization variables, and it can further exploit the potential of unequally spaced arrays with uniform excitation under acceptable complexity. [ABSTRACT FROM AUTHOR]

Given a set B of d -dimensional boxes (i.e., axis-aligned hyperrectangles), a minimum coverage kernel is a subset of B of minimum size covering the same region as B. Computing it is NP -hard, but as for many similar NP -hard problems (e.g., Box Cover , and Orthogonal Polygon Covering), the problem becomes solvable in polynomial time under restrictions on B. We show that computing minimum coverage kernels remains NP -hard even when restricting the graph induced by the input to a highly constrained class of graphs. Alternatively, we present two polynomial-time approximation algorithms for this problem: one deterministic with an approximation ratio within O (log ⁡ n) , and one randomized with an improved approximation ratio within O (lg ⁡ OPT) (with high probability). [ABSTRACT FROM AUTHOR]

The bootstrap method is one of the major developments in statistics in the 20th century for computing confidence intervals directly from data. However, the bootstrap method is traditionally approximated with a randomized algorithm, which can sometimes produce inaccurate confidence intervals. In "Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms," Bertsimas and Sturt present a new perspective of the bootstrap method through the lens of counting integer points in a polyhedron. Through this perspective, the authors develop the first computational complexity results and efficient deterministic approximation algorithm (fully polynomial time approximation scheme) for bootstrap confidence intervals, which unlike traditional methods, has guaranteed bounds on its error. In experiments on real and synthetic data sets from clinical trials, the proposed deterministic algorithms quickly produce reliable confidence intervals, which are significantly more accurate than those from randomization. The bootstrap is a nonparametric approach for calculating quantities, such as confidence intervals, directly from data. Since calculating exact bootstrap quantities is believed to be intractable, randomized resampling algorithms are traditionally used. In this paper, we present a new perspective on the bootstrap method through the lens of counting integer points in polyhedra. Through this new perspective, we make several advances for the bootstrap method, both theoretically and algorithmically. First, we establish several computational complexity results for the exact bootstrap method in the case of the sample mean. Second, we present the first efficient deterministic approximation algorithm (fully polynomial time approximation scheme) for producing exact bootstrap confidence intervals which, unlike traditional methods, has guaranteed bounds on the approximation error. Third, we develop a simple exact algorithm for exact bootstrap confidence intervals based on polynomial multiplication. We provide empirical evidence on real and synthetic data sets with several hundreds of data points that the proposed deterministic algorithms can quickly produce confidence intervals that are substantially more accurate than those from randomized methods, and thus are practical alternatives in applications such as clinical trials. [ABSTRACT FROM AUTHOR]

This paper investigates UAV-to-UAV (unmanned aerial vehicle) communications with a turning angle constraint, in which the information transmission time is minimized by joint UAV flight path planning and transmit power control. Considering the communication throughput requirement, peak transmit power, energy consumption, UAV flight speed, collision avoidance, and turning angle constraints, the joint UAV flight path planning and transmit power control problem is formulated as a non-convex optimization. Different from majority of prior studies that separately optimize the UAV flight path and transmit power, we develop a successive convex approximation based time minimization algorithm that simultaneously updates the UAV path and transmit power. We further prove that the proposed algorithm is guaranteed to converge. In addition, an initialization scheme is designed to start the proposed time minimization algorithm by solving an energy minimization problem. Simulation results verify that the proposed time minimization algorithm can shorten the completion time length and reduce the computational complexity compared with state of the art methods. [ABSTRACT FROM AUTHOR]

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than $\eta $ nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results. [ABSTRACT FROM AUTHOR]

Motivated by various delay sensitive applications, we address the problem of coordinating the offloading decisions of wireless devices that periodically generate computationally intensive tasks. We consider autonomous devices that aim at minimizing their own cost by choosing when to perform their tasks and whether or not to offload their tasks to an edge cloud through one of the multiple wireless links. We develop a game theoretical model of the problem, prove the existence of pure strategy Nash equilibria and propose a polynomial complexity algorithm for computing an equilibrium. Furthermore, we characterize the structure of the equilibria, and by providing an upper bound on the price of anarchy of the game we establish an asymptotically tight bound on the approximation ratio of the proposed algorithm. Our simulation results show that the proposed algorithm achieves significant performance gain compared to uncoordinated computation offloading at a computational complexity that is on average linear in the number of devices. [ABSTRACT FROM AUTHOR]

We introduce a problem called minimum shared‐power edge cut (MSPEC). The input to the problem is an undirected edge‐weighted graph with distinguished vertices s and t, and the goal is to find an s‐t cut by assigning "powers" at the vertices and removing an edge if the sum of the powers at its endpoints is at least its weight. The objective is to minimize the sum of the assigned powers. MSPEC is a graph generalization of a barrier coverage problem in a wireless sensor network: given a set of unit disks with centers in a rectangle, what is the minimum total amount by which we must shrink the disks to permit an intruder to cross the rectangle undetected, that is, without entering any disk. This is a more sophisticated measure of barrier coverage than the minimum number of disks whose removal breaks the barrier. We develop a fully polynomial time approximation scheme for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and matching problems, its computational complexity (in P or NP‐hard) remains open. [ABSTRACT FROM AUTHOR]

Kriging or Gaussian Process Regression is applied in many fields as a non-linear regression model as well as a surrogate model in the field of evolutionary computation. However, the computational and space complexity of Kriging, that is cubic and quadratic in the number of data points respectively, becomes a major bottleneck with more and more data available nowadays. In this paper, we propose a general methodology for the complexity reduction, called cluster Kriging, where the whole data set is partitioned into smaller clusters and multiple Kriging models are built on top of them. In addition, four Kriging approximation algorithms are proposed as candidate algorithms within the new framework. Each of these algorithms can be applied to much larger data sets while maintaining the advantages and power of Kriging. The proposed algorithms are explained in detail and compared empirically against a broad set of existing state-of-the-art Kriging approximation methods on a well-defined testing framework. According to the empirical study, the proposed algorithms consistently outperform the existing algorithms. Moreover, some practical suggestions are provided for using the proposed algorithms. [ABSTRACT FROM AUTHOR]

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability pi: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP‐complete. [ABSTRACT FROM AUTHOR]