Search

We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks. Such algorithms (most prominently stochastic gradient descent and its variants) are used extensively in the field of deep learning. One of the most important problems in this field concerns the question of whether it is possible to realize theoretically provable neural network approximation rates by such algorithms. We answer this question in the negative by proving hardness results for the problems of approximation and integration on a novel class of neural network approximation spaces. In particular, our results confirm a conjectured and empirically observed theory-to-practice gap in deep learning. We complement our hardness results by showing that error bounds of a comparable order of convergence are (at least theoretically) achievable. [ABSTRACT FROM AUTHOR]

This paper develops novel fast numerical solvers for subdiffusion problems with spatial interfaces. These problems are modeled by partial differential equations that contain both fractional order and conventional first order time derivatives. The former is non-local and approximated by L1 and L2 discretizations along with fast evaluation algorithms based on approximation by sums of exponentials. This results in an effective treatment of the "long-tail" kernel of subdiffusion. The latter is local and hence conventional implicit Euler or Crank-Nicolson discretizations can be used. Finite volumes are utilized for spatial discretization based on consideration of local mass conservation. Interface conditions for mass and fractional uxes are incorporated into these fast solvers. Computational complexity and implementation procedures are briey discussed. Numerical experiments demonstrate accuracy and efficiency of these new fast solvers. [ABSTRACT FROM AUTHOR]

Bayesian optimization algorithms are widely used for solving problems with a high computational complexity in terms of objective function evaluation. The efficiency of Bayesian optimization is strongly dependent on the quality of the surrogate models of an objective function, which are built and refined at each iteration. The quality of surrogate models, and hence the performance of an optimization algorithm, can be greatly improved by selecting the appropriate hyperparameter values of the approximation algorithm. The common approach to finding good hyperparameter values for each iteration of Bayesian optimization is to build surrogate models with different hyperparameter values and choose the best one based on some estimation of the approximation error, for example, a cross-validation score. Building multiple surrogate models for each iteration of Bayesian optimization is computationally demanding and significantly increases the time required to solve an optimization problem. This paper suggests a new approach, called exploratory landscape validation, to find good hyperparameter values with less computational effort. Exploratory landscape validation metrics can be used to predict the best hyperparameter values, which can improve both the quality of the solutions found by Bayesian optimization and the time needed to solve problems. [ABSTRACT FROM AUTHOR]

Conceptual distance refers to the degree of proximity between two concepts within a conceptualization. It is closely related to semantic similarity and relationships, but its measurement strongly depends on the context of the given concepts. DIS-C represents an advancement in the computation of semantic similarity/relationships that is independent of the type of knowledge structure and semantic relations when generating a graph from a knowledge base (ontologies, semantic networks, and hierarchies, among others). This approach determines the semantic similarity between two indirectly connected concepts in an ontology by propagating local distances by applying an algorithm based on the All Pairs Shortest Path (APSP) problem. This process is implemented for each pair of concepts to establish the most effective and efficient paths to connect these concepts. The algorithm identifies the shortest path between concepts, which allows for an inference of the most relevant relationships between them. However, one of the critical issues with this process is computational complexity, combined with the design of APSP algorithms, such as Dijkstra, which is n 3 . This paper studies different alternatives to improve the DIS-C approach by adapting approximation algorithms, focusing on Dijkstra, pruned Dijkstra, and sketch-based methods, to compute the conceptual distance according to the need to scale DIS-C to analyze very large graphs; therefore, reducing the related computational complexity is critical. Tests were performed using different datasets to calculate the conceptual distance when using the original version of DIS-C and when using the influence area of nodes. In situations where time optimization is necessary for generating results, using the original DIS-C model is not the optimal method. Therefore, we propose a simplified version of DIS-C to calculate conceptual distances based on centrality estimation. The obtained results for the simple version of DIS-C indicated that the processing time decreased 2.381 times when compared to the original DIS-C version. Additionally, for both versions of DIS-C (normal and simple), the APSP algorithm decreased the computational cost when using a two-hop coverage-based approach. [ABSTRACT FROM AUTHOR]

We study several two-machine shop scheduling problems, namely flow shop, job shop and open shop scheduling problems under linear constraints. In these problems, the processing times of two stages of jobs are also decision variables and satisfy a system of linear constraints. The goal of each problem is to determine the processing time of each job, and to schedule the jobs to the shop machine such that the makespan, i.e., the completion time of all jobs, is minimized. These problems can find application in various areas, such as industrial production, advertising and automotive maintenance. We study the computational complexity and propose polynomial-time optimal or approximation algorithms for them. In particular, we show that although a two-machine flow shop scheduling problem and a two-machine job shop scheduling problem without recirculation can be solved in polynomial time, the problems where processing times satisfy linear constraints are generally NP-hard in the strong sense. Then, we design algorithms for various settings of these problems. We design polynomial-time algorithms for them when there are a fixed number of constraints. For the general case, we first propose a simple 2-approximation algorithm, and then design a polynomial-time approximation schemes. In contrast to the previous two problems, we show that the two-machine open shop scheduling problem under linear constraints can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Cliqe on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2õ (n²/3 ) for Maximum Cliqe on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for Max Cliqe on disk and unit ball graphs. Max Cliqe on unit ball graphs is equivalent to finding, given a collection of points in R³, a maximum subset of pointswith diameter at most some fixed value. In stark contrast, Maximum Cliqe on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we showthat, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2n1-ε, unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

We propose a novel semi-supervised learning (SSL) assumption—the high separation probability (HSP) assumption—that is complementary to the common low density separation (LDS) assumption, and a highly accurate and efficient SSL algorithm, the transductive minimax probability machine (TMPM). Under the HSP assumption, a preferred classifier should ensure that with high probability the samples are far away from the decision boundary. Similarly, the LDS assumption states that the decision boundary should lie in a low-density region. A remarkable property of HSP is that it provides an elegant theoretical framework for analyzing the generalization performance of SSL, while it remains difficult for the LDS assumption to have a quantitative criterion on how it fits the data. Moreover, it has the same paradigm as the minimax probability machine (MPM) and yields an intractable mixed-integer optimization for solving the transductive label assignment problem. Consequently, we propose TMPM with a label-switching strategy and iterative manner to formalize our approximate solution. Theoretically, we analyze the computational complexity, convergence property, and generalization error bound of TMPM. Empirically, we show that TMPM achieves competitive performance on a wide range of datasets, while being almost one order of magnitude faster than existing SSL approaches. [ABSTRACT FROM AUTHOR]

Residual closeness is recently proposed as a vulnerability measure to characterize the stability of complex networks. Residual closeness is essential in the analysis of complex networks, but costly to compute. Currently, the fastest known algorithms run in polynomial time. Motivated by the fast-growing need to compute vulnerability measures on complex networks, new algorithms for computing node and edge residual closeness are introduced in this paper. Those proposed algorithms reduce the running times to Θ(n3) and Θ (n4) on unweighted networks, respectively, where n is the number of nodes. [ABSTRACT FROM AUTHOR]

In this article, we consider the problem of estimating diffraction attenuation from the approximation of terrain using a multiple bridged knife-edge model. This model can be considered as a generalization of the well-known multiple knife-edge (MKE) one where spaces between knife-edges are bridged by reflecting surfaces. A series-based-standard solution is presented in the literature but suffers from its very high computational complexity. We, thus, propose to generalize the recursive Vogler algorithm developed for the MKE model to tackle this problem. To reduce complexity, the proposed algorithm exploits the recursive form to avoid repeated calculations of the existing solution. Moreover, we provide a complexity analysis of both the standard algorithm and the proposed algorithm based on the number of computed integrals. Both theoretical and numerical results show that our proposed algorithm is faster than the original one while having identical accuracy, hence proving the effectiveness of our solution. [ABSTRACT FROM AUTHOR]

Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four polynomial-time approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed approximation lower bounds are derived for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the efficiency and effectiveness of the proposed algorithms; in particular, serving as initialization procedures, the approximation algorithms can help in improving the solution quality of iterative algorithms while reducing the computational time. [ABSTRACT FROM AUTHOR]

In this article, we propose a fast algorithm to generate a rank-minimized $\mathcal {H}^{2}$ -representation for solving electrically large volume integral equations (VIEs). Unlike existing methods whose complexity is as high as quadratic, the proposed algorithm has linearithmic complexity, and thus, it can handle problems with large electrical sizes. Furthermore, the algorithm is purely algebraic and kernel independent. Numerical experiments on electrically large 3-D arrays of dielectric cubes having over 33 million unknowns demonstrate the efficiency and accuracy of the proposed algorithm. [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]

This article presents a novel Bayesian approach for hyperspectral image unmixing. The observed pixels are modeled by a linear combination of material signatures weighted by their corresponding abundances. A spike-and-slab abundance prior is adopted to promote sparse mixtures and an Ising prior model is used to capture spatial correlation of the mixture support across pixels. We approximate the posterior distribution of the abundances using the expectation-propagation (EP) method. We show that it can significantly reduce the computational complexity of the unmixing stage and meanwhile provide uncertainty measures, compared to expensive Monte Carlo strategies traditionally considered for uncertainty quantification. Moreover, many variational parameters within each EP factor can be updated in a parallel manner, which enables mapping of efficient algorithmic architectures based on graphics processing units (GPUs). Under the same approximate Bayesian framework, we then extend the proposed algorithm to semi-supervised unmixing, whereby the abundances are viewed as latent variables and the expectation-maximization (EM) algorithm is used to refine the endmember matrix. Experimental results on synthetic data and real hyperspectral data illustrate the benefits of the proposed framework over state-of-art linear unmixing methods. [ABSTRACT FROM AUTHOR]

Discrete random variables are essential ingredients in various artificial intelligence problems. These include the estimation of the probability of missing the deadline in a series-parallel schedule and the assignment of suppliers to tasks in a project in a manner that maximizes the probability of meeting the overall project deadline. The solving of such problems involves repetitive operations, such as summation, over random variables. However, these computations are NP-hard. Therefore, we explore techniques and methods for approximating random variables with a given support size and minimal Kolmogorov distance. We examine both the general problem of approximating a random variable and a one-sided version in which over-approximation is allowed but not under-approximation. We propose several algorithms and evaluate their performance through computational complexity analysis and empirical evaluation. All the presented algorithms are optimal in the sense that given an input random variable and a requested support size, they return a new approximated random variable with the requested support size and minimal Kolmogorov distance from the input random variable. Our approximation algorithms offer useful estimations of probabilities in situations where exact computations are not feasible due to NP-hardness complexity. [ABSTRACT FROM AUTHOR]

Nonlinear estimation in robotics and vision is typically plagued with outliers due to wrong data association or incorrect detections from signal processing and machine learning methods. This article introduces two unifying formulations for outlier-robust estimation, generalized maximum consensus ($\text{G}$ - $\text{MC}$) and generalized truncated least squares ($\text{G-TLS}$), and investigates fundamental limits, practical algorithms, and applications. Our first contribution is a proof that outlier-robust estimation is inapproximable: In the worst case, it is impossible to (even approximately) find the set of outliers, even with slower-than-polynomial-time algorithms (particularly, algorithms running in quasi-polynomial time). As a second contribution, we review and extend two general-purpose algorithms. The first, adaptive trimming ($\text{ADAPT}$), is combinatorial and is suitable for $\text{G}$ - $\text{MC}$ ; the second, graduated nonconvexity ($\text{GNC}$), is based on homotopy methods and is suitable for $\text{G-TLS}$. We extend $\text{ADAPT}$ and $\text{GNC}$ to the case where the user does not have prior knowledge of the inlier-noise statistics (or the statistics may vary over time) and is unable to guess a reasonable threshold to separate inliers from outliers (as the one commonly used in RANdom SAmple Consensus $(\text{RANSAC})$. We propose the first minimally tuned algorithms for outlier rejection, which dynamically decide how to separate inliers from outliers. Our third contribution is an evaluation of the proposed algorithms on robot perception problems: mesh registration, image-based object detection (shape alignment), and pose graph optimization. $\text{ADAPT}$ and $\text{GNC}$ execute in real time, are deterministic, outperform $\text{RANSAC}$ , and are robust up to 80–90% outliers. Their minimally tuned versions also compare favorably with the state of the art, even though they do not rely on a noise bound for the inliers. [ABSTRACT FROM AUTHOR]

The ongoing COVID-19 pandemic underscores the importance of developing reliable forecasts that would allow decision makers to devise appropriate response strategies. Despite much recent research on the topic, epidemic forecasting remains poorly understood. Researchers have attributed the difficulty of forecasting contagion dynamics to a multitude of factors, including complex behavioral responses, uncertainty in data, the stochastic nature of the underlying process, and the high sensitivity of the disease parameters to changes in the environment. We offer a rigorous explanation of the difficulty of short-term forecasting on networked populations using ideas from computational complexity. Specifically, we show that several forecasting problems (e.g., the probability that at least a given number of people will get infected at a given time and the probability that the number of infections will reach a peak at a given time) are computationally intractable. For instance, efficient solvability of such problems would imply that the number of satisfying assignments of an arbitrary Boolean formula in conjunctive normal form can be computed efficiently, violating a widely believed hypothesis in computational complexity. This intractability result holds even under the ideal situation, where all the disease parameters are known and are assumed to be insensitive to changes in the environment. From a computational complexity viewpoint, our results, which show that contagion dynamics become unpredictable for both macroscopic and individual properties, bring out some fundamental difficulties of predicting disease parameters. On the positive side, we develop efficient algorithms or approximation algorithms for restricted versions of forecasting problems. [ABSTRACT FROM AUTHOR]

Future cities promise to be more autonomous than ever, largely owing to our ability of coordinating complex systems in real time: fleets of self-driving cars will offer on-demand transportation services, delivery drones will fly parcels in our skies, power plants will provide renewable energy reliably. In many of these systems, there is no single decision-maker with full information and authority. Instead, the system performance greatly depends on the decisions made by interacting entities with local information and limited communication capabilities. Game theory, intended as the study of multi-agent decision-making, is a fitting paradigm to tackle many of the associated challenges. Moving from this observation, in this paper we review how tools and ideas from game theory can be brought to bear on the coordination of multi-agent systems. At the heart of the proposed approach is the design and influence of agents' preferences so that their local optimization induces a desirable system behavior. Its applicability spans a variety of settings irrespective of whether the decision makers are strategic (e.g., drivers in a road network), or not (e.g., delivery drones). Along the way, we also discuss future research directions and connections with related research areas including algorithmic game theory, incentive and mechanism design, economics, computational complexity, and approximation algorithms. [ABSTRACT FROM AUTHOR]

An algorithm for the fast computation of multistatic scattering patterns, produced by low-contrast inhomogeneous volumetric objects, which satisfy the Born approximation assumption, is presented. The algorithm relies on hierarchical interpolation and aggregation of optimally sampled phase-compensated partial contributions to the scattered field integral. The Born approximation enables the efficient simultaneous computation for ranges of incident and observation angles, as well as excitation frequencies. This leads to a reduction in the asymptotic computational complexity by several polynomial orders of the problem’s acoustical size. The algorithm’s error controllability and favorable computation time are demonstrated via representative examples. [ABSTRACT FROM AUTHOR]

We consider the total weighted early work maximization problem on identical machines in parallel such that the weights are identical, or the due date is the same. First, we present an approach to solve the case with a fixed number of machines in pseudo-polynomial time. Then, we develop approximation algorithms for the two cases with identical weights and with a common due date. For the case with identical weights, furthermore, we show that the parallel-machine and a single-machine cases are strongly NP-hard and weakly NP-hard, respectively, even if the due date of each job is equal to the processing time multiplied by a constant. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]