Search

This research centers on the application of the discrete-time Taylor–Fourier transform (DTTFT) algorithmic implementation for phasor estimation on a field-programmable gate array board. The system employs a finite impulse response structure of a digital Taylor–Fourier filter to extract amplitude and phase information. The hardware description utilizes a multiply accumulator architecture with only forty embedded 9-bit multiplier elements, achieving an 18-bit input–output resolution. Performance assessment involves signal analysis through FPGA-in-the-loop simulation in MATLAB/Simulink. Findings demonstrate that the DTTFT-based phasor estimator can be effectively characterized using VHDL code and implemented on an Intel D2-115 board. [ABSTRACT FROM AUTHOR]

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ϵ>0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ϵ expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ϵ-kernels of point sets, approximate nearest neighbor searching, polytope approximations, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size nO(n)/ϵ(n-1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the ℓp unit ball, this bound has been improved to 2O(n)/ϵ(n-1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, under the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter ϵ>0, we show that there exists a polytope P consisting of 2O(n)/ϵ(n-1)/2 vertices (facets) such that K⊂P⊂K(1+ϵ). This bound is optimal in the worst case up to factors of 2O(n). As an additional consequence, we obtain the fastest (1+ϵ)-approximate CVP algorithm that works in any norm, with a running time of 2O(n)/ϵ(n-1)/2 up to polynomial factors in the input size, and we obtain the fastest (1+ϵ)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of 2O(n)). [ABSTRACT FROM AUTHOR]

Privacy-preserving neural networks offer a promising solution to train and predict without user privacy leakage, and fully homomorphic encryption (FHE) stands out as one of the key technologies, as it enables homomorphic operations over encrypted data. However, only addition and multiplication homomorphisms are supported by FHE, and thus, it faces huge challenges when implementing non-linear functions with ciphertext inputs. Among the non-linear functions in neural networks, one may refer to the activation function, the argmax function, and maximum pooling. Inspired by using a composition of low-degree minimax polynomials to approximate sign and argmax functions, this study focused on optimizing the homomorphic argmax approximation, where argmax is a mathematical operation that identifies the index of the maximum value within a given set of values. For the method that uses compositions of low-degree minimax polynomials to approximate argmax, in order to further reduce approximation errors and improve computational efficiency, we propose an improved homomorphic argmax approximation algorithm that includes rotation accumulation, tree-structured comparison, normalization, and finalization phases. And then, the proposed homomorphic argmax algorithm was integrated into a neural network structure. Comparative experiments indicate that the network with our proposed argmax algorithm achieved a slight increase in accuracy while significantly reducing the inference latency by 58 % , as the homomorphic sign and rotation operations were rapidly reduced. [ABSTRACT FROM AUTHOR]

We study the problem of computing the p q norm of a matrix A ∈ Rm×n, defined as ∣∣j4∣∣p-g = maxx∈Rn{0}'.||Ax|q/||x|p This problem generalizes the spectral norm of a matrix (p = q = 2) and the Grothendieck problem (p = ∞, q = 1) and has been widely studied in various regimes. When p ≥ q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 ∈ [g,p], and the problem is hard to approximate within almost polynomial factors when 2 [g,p]. The regime when p < q, known as Hypercontractive norms, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by Barak et al. [Proceedings of the 4Ath Annual ACM Symposium on Theory of Computing, 2012, pp. 307--326], who gave subexponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the exponential time hypothesis. However, no NP-hardness of approximation is known for these problems for any p < q. We prove the first NP-hardness result (under randomized reductions) for approximating hypercontractive norms. We show that for any 1 < p < q < ∞ with 2 [p, g], ∣∣√4∣∣p--q is hard to approximate within 2°(log n)1-x) assuming NP g BPTIME(21log n A-). En rθute to the above result, we also prove almost tight results for the case when p > q with 2 ∈ [q, p]. [ABSTRACT FROM AUTHOR]

The finite difference (FD) algorithm is a recently proposed algorithm for single-component polynomial phase signal (PPS) parameter estimation. It can handle high-order PPSs, while being computationally simple. A drawback of the algorithm is that it cannot operate at lower signal-to-noise ratios (SNRs). We propose modifications to allow the FD algorithm to operate at lower SNRs. The modifications are magnitude weighting for phase values, phase difference filtering, and iterating the polynomial refinement step. Simulation shows that these modifications can reduce the algorithm’s SNR threshold by 5 dB, without greatly increasing the computational complexity. [ABSTRACT FROM AUTHOR]

In this article, two new techniques of approximation of the reliability of a two-terminal network are developed based on the constructive theory of functions and related methods. Two methods of generating an approximation cubic spline are used: Lagrange-type interpolation procedures and Bernstein approximation operator. A possibility of minimizing the total error of approximation, based on keeping some properties invariant, is described in case of a large class of pairs of dual two-terminal networks. Simulations are included, showing that the error of approximation is negligible in case of some special initial data. [ABSTRACT FROM AUTHOR]

In this paper, we propose CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices. The objective is to reduce the recovery threshold, defined as the total number of worker nodes that the master node needs to wait for to be able to recover the final result. To exploit the fact that only an approximated result is required, in reducing the recovery threshold, some sorts of pre-compression are required. However, compression inherently involves some randomness that would lose the structure of the matrices. On the other hand, considering the structure of the matrices is crucial to reduce the recovery threshold. In CodedSketch, we use count–sketch, as a hash-based compression scheme, on the rows of the first and columns of the second matrix, and a structured polynomial code on the columns of the first and rows of the second matrix. This arrangement allows us to exploit the gain of both in reducing the recovery threshold. To increase the accuracy of computation, multiple independent count–sketches are needed. This independency allows us to theoretically characterize the accuracy of the result and establish the recovery threshold achieved by the proposed scheme. To guarantee the independency of resulting count–sketches in the output, while keeping its cost on the recovery threshold minimum, we use another layer of structured codes. The proposed scheme provides an upper-bound on the recovery threshold as a function of the required accuracy of computation and the probability that the required accuracy can be violated. In addition, it provides an upper-bound on the recovery threshold for the case that the result of the multiplication is sparse, and the exact result is required. [ABSTRACT FROM AUTHOR]

Filters relying on the Gaussian approximation typically incorporate the measurement linearly, i.e., the value of the measurement is premultiplied by a matrix-valued gain in the state update. Nonlinear filters that relax the Gaussian assumption, on the other hand, typically approximate the distribution of the state with a finite sum of point masses or Gaussian distributions. In this work, the distribution of the state is approximated by a polynomial transformation of a Gaussian distribution, allowing for all moments, central and raw, to be rapidly computed in a closed form. Knowledge of the higher order moments is then employed to perform a polynomial measurement update, i.e., the value of the measurement enters the update function as a polynomial of arbitrary order. A filter employing a Gaussian approximation with linear update is, therefore, a special case of the proposed algorithm when both the order of the series and the order of the update are set to one: it reduces to the extended Kalman filter. At the cost of more computations, the new methodology guarantees performance better than the linear/Gaussian approach for nonlinear systems. This work employs monomial basis functions and Taylor series, developed in the differential algebra framework, but it is readily extendable to an orthogonal polynomial basis. [ABSTRACT FROM AUTHOR]

Three types of orthogonal polynomials (Chebyshev, Chelyshkov, and Legendre) are employed as basis functions in a collocation scheme to solve a nonlinear cubic initial value problem arising in population growth models. The method reduces the given problem to a set of algebraic equations consist of polynomial coefficients. Our main goal is to present a comparative study of these polynomials and to asses their performances and accuracies applied to the logistic population equation. Numerical applications are given to demonstrate the validity and applicability of the method. Comparisons are also made between the present method based on different basis functions and other existing approximation algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks, where a source node communicates to a destination node through a multi-hop path of $N$ relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD $N$ -relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the $N+1$ listen/transmit states (out of the $2^{N}$ possible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed. [ABSTRACT FROM AUTHOR]

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an (1 - g(ε))-fraction of constraints on any (1 - ε )- satisfiable instance, where the loss function g is such that g(ε ) \rightarrow 0 as ε \rightarrow 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterized by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(ε ) = O((log log(1/ε ))/ log(1/ε)). It is natural to ask when a better loss can be achieved, in particular polynomial loss g(ε ) = O(ε 1/k) for some constant k. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called the dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalization of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP [ABSTRACT FROM AUTHOR]

We prove that poly-sized AC0 circuits cannot distinguish a polylogarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [1990]. The only prior progress on the problem was by Bazzi [2007], who showed that O(log2n)-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem. [ABSTRACT FROM AUTHOR]

Stochastic optimization problems attempt to model uncertainty in the data by assuming that the input is specified by a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. We show that for a broad class of 2-stage linear models with recourse, one can, for any ∈ > 0, in time polynomial in 1/∈ and the size of the input, compute a solution of value within a factor (1 + ∈) of the optimum, in spite of the fact that exponentially many second-stage scenarios may occur. In conjunction with a suitable rounding scheme, this yields the first approximation algorithms for 2-stage stochastic integer optimization problems where the underlying random data is given by a "black box" and no restrictions are placed on the costs in the two stages. Our rounding approach for stochastic integer programs shows that an approximation algorithm for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Among the range of applications, we consider are stochastic versions of the multicommodity flow, set cover, vertex cover, and facility location problems. [ABSTRACT FROM AUTHOR]

In this article we present a theoretical analysis of the online Sum-of-Squares algorithm (SS) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s(a) are integral (or can be scaled to be so), and runs in time O(nB). It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O(log n). We also discuss several interesting variants on SS, including a randomized O(nB log B)-time online algorithm SS whose expected behavior is essentially optimal for all discrete distributions. Algorithm SS depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F, just what is the growth rate for the optimal expected waste. [ABSTRACT FROM AUTHOR]

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓp norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2poly(log n)), we show that there is no polynomial-time algorithm with approximation ratio 2(log n)1/2-∈ where n is the dimension of the lattice and ∈ > 0 is an arbitrarily small constant. We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves some constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product, a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2(log n)½-∈. [ABSTRACT FROM AUTHOR]

We study the well-known two-dimensional Strip Packing problem. Given a set of rectangular axis-parallel items and a strip of width W with infinite height, the objective is to find a packing of all items into the strip, which minimizes the packing height. Lately, it has been shown that the lower bound of 3/2 of the absolute approximation ratio can be beaten when we allow a pseudo-polynomial running-time of type (n W) f (1 / ε). If W is polynomially bounded by the number of items, this is a polynomial running-time. The currently best pseudo-polynomial approximation algorithm by Nadiradze and Wiese achieves an approximation ratio of 1.4 + ε. We present a pseudo-polynomial algorithm with improved approximation ratio 4 / 3 + ε. Furthermore, the presented algorithm has a significantly smaller running-time as the 1.4 + ε approximation algorithm. [ABSTRACT FROM AUTHOR]

Abstract It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a (non-negatively) weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. In particular, this allows for an effective treatment of polynomials with rational coefficients. In this article, we describe, analyze and compare, from both the theoretical and practical points of view, two algorithms computing such a weighted sum of squares decomposition for univariate polynomials with rational coefficients. The first algorithm, due to the third author, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition, but its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds. The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition, and was introduced for certifying positiveness of polynomials in the context of computer arithmetic. Again, its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds. Finally, we report on our implementations of both algorithms and compare them in practice on several application benchmarks. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better. [ABSTRACT FROM AUTHOR]

Factor graphs are important models for succinctly representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and partition functions, arise naturally when working with factor graphs. Belief propagation is a widely deployed iterative method for solving these problems. However, despite its significant empirical success, several questions regarding the correctness and efficiency of belief propagation remain open. The Bethe approximation is an optimization-based method for approximating the partition functions. While it is known that the stationary points of the Bethe approximation coincide with the fixed points of belief propagation, in general, the relation between the Bethe approximation and the partition function is not well understood. It has been observed that for a few classes of factor graphs, the Bethe approximation gives a lower bound to the partition function, which distinguishes them from the general case, where neither a lower bound nor an upper bound holds universally. This has been rigorously proved for permanents and for attractive graphical models. Here, we consider bipartite factor graphs over binary alphabet and show that if the local constraints satisfy a certain analytic property, the Bethe approximation is a lower bound to the partition function, generalizing an analogous inequality between the permanent and the Bethe permanent of a matrix with non-negative entries. We arrive at this result by viewing the factor graphs through the lens of polynomials, which allows us to reformulate the Bethe approximation as an optimization problem involving polynomials. The sufficient condition for our lower bound property to hold is inspired by the recent developments in the theory of real stable polynomials. We believe that this way of viewing factor graphs and its connection to real stability might lead to a better understanding of belief propagation and factor graphs in general. [ABSTRACT FROM AUTHOR]

We analyze algorithms for approximating a function f (x) = Φ x mapping ℜ d to ℜ d using deep linear neural networks, that is, that learn a function h parameterized by matrices Θ 1 , ... , Θ L and defined by h (x) = Θ L Θ L - 1 ... Θ 1 x. We focus on algorithms that learn through gradient descent on the population quadratic loss in the case that the distribution over the inputs is isotropic. We provide polynomial bounds on the number of iterations for gradient descent to approximate the least-squares matrix Φ , in the case where the initial hypothesis Θ 1 = ... = Θ L = I has excess loss bounded by a small enough constant. We also show that gradient descent fails to converge for Φ whose distance from the identity is a larger constant, and we show that some forms of regularization toward the identity in each layer do not help. If Φ is symmetric positive definite, we show that an algorithm that initializes Θ i = I learns an ε -approximation of f using a number of updates polynomial in L , the condition number of Φ , and log (d / ε). In contrast, we show that if the least-squares matrix Φ is symmetric and has a negative eigenvalue, then all members of a class of algorithms that perform gradient descent with identity initialization, and optionally regularize toward the identity in each layer, fail to converge. We analyze an algorithm for the case that Φ satisfies u ⊤ Φ u > 0 for all u but may not be symmetric. This algorithm uses two regularizers: one that maintains the invariant u ⊤ Θ L Θ L - 1 ... Θ 1 u > 0 for all u and the other that "balances" Θ 1 , ... , Θ L so that they have the same singular values. [ABSTRACT FROM AUTHOR]

Device-to-device (D2D) content sharing helps to accommodate the exponentially surge in mobile data traffic. However, how to cache in mobile users is crucial to ensure the above advantages. There are three issues that have not been fully considered in the previous works. First, the ignorance of mobility cannot depict the random connectivity of mobile users in D2D content sharing. Second, the lack of the diverse and complete information on user interest leads to unsatisfied demands of users. Third, caching a complete content will be wasteful due to the limited cache capacity, which is also not likely to be obtained in one connection. Regarding the three issues, we construct not only a user mobility model, which helps to provide the contact opportunity for the users sharing contents, but also a user interest prediction model, which combines the social proximity and the dynamic content popularity. Moreover, we exploit the maximum distance separable code to encode the contents into smaller partitions. Accordingly, we formulate a mobility-aware and user interest-driven caching problem as a 0–1 multiple knapsack problem. Due to its NP-hard property, we prove that this problem falls into the category of monotone submodular function over one matroid and multiple knapsack constraints. Then, we develop a corresponding algorithm based on a greedy approach, which approximates the optimum within a constant factor in polynomial time. Numerical results demonstrate the performance and the effectiveness of our proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper deals with order reduction in discrete-time systems. The reduction technique is based on utilization of Routh approximation and multiplicative operator. Various combinations of Routh table are used to derive the desired numerator and denominator polynomial of reduced-order model. Numerical examples are presented to verify the proposed algorithm. [ABSTRACT FROM AUTHOR]

The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qmjpj = 1, G = bisubquarticjCmax. The second one is Algorithm 3 which is 4-approximate for the problem Qmjpj = 1, G = bisubquarticjSCj, where m 2 {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper. [ABSTRACT FROM AUTHOR]

In addition to setting price discounts, retailers need to decide how to schedule promotion vehicles, such as flyers and TV commercials. Unlike the promotion pricing problem that received great attention from both academics and practitioners, the promotion vehicle scheduling problem was largely overlooked, and our goal is to study this problem both theoretically and in practice. We model the problem of scheduling promotion vehicles to maximize profits as a nonlinear bipartite matching-type problem, where promotion vehicles should be assigned to time periods, subject to capacity constraints. Our modeling approach is motivated and calibrated using actual data in collaboration with Oracle Retail, leading us to introduce and study a class of models for which the boost effects of promotion vehicles on demand are multiplicative. From a technical perspective, we prove that the general setting considered is computationally intractable. Nevertheless, we develop approximation algorithms and propose a compact integer programming formulation. In particular, we show how to obtain a (1 − ε)-approximation using an integer program of polynomial size, and investigate the performance of a greedy procedure, both analytically and computationally. We also discuss an extension that includes cross-term effects to capture the cannibalization aspect of using several vehicles simultaneously. From a practical perspective, we test our methods on actual data through a case study, and quantify the impact of our models. Under our model assumptions and for a particular item considered in our case study, we show that a rigorous optimization approach to the promotion vehicle scheduling problem allows the retailer to increase its profit by 2% to 9%. The online appendix is available at https://doi.org/10.1287/mnsc.2017.2926. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

We consider a single-machine scheduling problem such that the due dates are assigned not to the jobs but to the position at which the job is processed. We focus on the case with identical due date intervals. The objective is to minimize the weighted number of early and tardy jobs. First, we show that the problem is strongly NP-hard and has no ρ -approximation algorithm for any fixed value ρ > 1. Then, we investigate polynomially solvable cases. Finally, we show that the preemption version is weakly NP-hard through its equivalence to the problem of minimizing the weighted number of tardy jobs. [ABSTRACT FROM AUTHOR]

We study the approximation capabilities of two families of univariate polynomials that arise in applications of quantum signal processing. Although approximation only in the domain [ 0 , 1 ] is physically desired, these polynomial families are defined by bound constraints not just in [ 0 , 1 ] , but also with additional bound constraints outside [ 0 , 1 ]. One might wonder then if these additional constraints inhibit their approximation properties within [ 0 , 1 ]. The main result of this paper is that this is not the case — the additional constraints do not hinder the ability of these polynomial families to approximate arbitrarily well any continuous function f : [ 0 , 1 ] → [ 0 , 1 ] in the supremum norm, provided f also matches any polynomial in the family at 0 and 1. We additionally study the specific problem of approximating the step function on [ 0 , 1 ] (with the step from 0 to 1 occurring at x = 1 2 ) using one of these families, and propose two subfamilies of monotone and non-monotone approximations. For the non-monotone case, under some additional assumptions, we provide an iterative heuristic algorithm that finds the optimal polynomial approximation. [ABSTRACT FROM AUTHOR]

Let Λ ⊂ ℝn be an algebraic lattice coming from a projective module over the ring of integers of a number field K. Let Z ⊂ ℝn be the zero locus of a finite collection of polynomials such that Λ ... Z or a finite union of proper full-rank sublattices of Λ. Let K1 be the number field generated over K by coordinates of vectors in Λ, and let L1, ..., Lt be linear forms in n variables with algebraic coefficients satisfying an appropriate linear independence condition over K1. For each ε > 0 and a ∈ ℝn, we prove the existence of a vector x ∈ Λ \Z of explicitly bounded sup-norm such that ∥Li(x) - ai∥ < ε for each 1 ≤ i ≤ t, where ∥ ∥ stands for the distance to the nearest integer. The bound on sup-norm of x depends on ε, as well as on Λ, K, Z, and heights of linear forms. This presents a generalization of Kronecker's approximation theorem, establishing an effective result on density of the image of Λ\Z under the linear forms L1, ..., Lt in the t-torus ℝt/ℤt. [ABSTRACT FROM AUTHOR]

This letter aims at introducing the framework of polynomial optimization theory to solve fractional polynomial problems (FPPs). Unlike other widely used optimization frameworks, the proposed one applies to a larger class of FPPs, not necessarily defined by concave and/or convex functions. An iterative algorithm that is provably convergent and enjoys asymptotic optimality properties is proposed. Numerical results are used to validate its accuracy in the nonasymptotic regime when applied to the energy efficiency maximization in multiuser multiple-input multiple-output communication systems. [ABSTRACT FROM AUTHOR]

Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for k=2 with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k. [ABSTRACT FROM AUTHOR]

In this paper, we devise a fast encoding algorithm for triply extended Reed–Solomon codes. The proposed approach requires approximately two XORs per bit, which improves the prior result of three XORs per bit established by certain maximum distance separable (MDS) array codes. We also prove that, for MDS codes with two and three parities, the scheduling algorithms require at least two XORs per bit. To the best of our knowledge, this is the first provable scheduling algorithm for the triple-parity MDS codes to approach the theoretical lower bounds. The implementation with SIMD instructions is provided. The simulations show that the proposed approach is competitive, as compared with other cutting edge implementations. [ABSTRACT FROM AUTHOR]

Representations, differentiation formulas, series expansions and other relations for the exponential polynomials are given. [ABSTRACT FROM AUTHOR]

Arising in connection with multiobjective selection and archiving, the hypervolume subset selection problem (HSSP) consists in finding a subset of size k\leq n of a set X\subset \mathbb R^d of n nondominated points in d -dimensional space that maximizes the hypervolume indicator. The incremental greedy approximation to the HSSP has an approximation guarantee of 1-1/e , and is polynomial in n and k , while no polynomial exact algorithms are known for d\geq 3 . The decremental greedy counterpart has no known approximation guarantee, but is potentially faster for large k , and still leads to good approximations in practice. The computation and update of individual hypervolume contributions are at the core of the implementation of this greedy strategy. In this paper, new algorithms for the computation and update of hypervolume contributions are developed. In three dimensions, updating the total hypervolume and all individual contributions under single-point changes is performed in linear time, while in the 4-D case all contributions are computed in O(n^2) time. As a consequence, the decremental greedy approximation to the HSSP can now be obtained in O(n(n-k) + n\log n) and O(n^2(n-k)) time for d=3 and d=4 , respectively. Experimental results show that the proposed algorithms significantly outperform existing ones. [ABSTRACT FROM AUTHOR]

Many applications of finite impulse response (FIR) digital filters impose strict format constraints on the filter coefficients. Such requirements increase the complexity of determining optimal designs for the problem at hand. We introduce a fast and efficient method, based on the computation of good nodes for polynomial interpolation and Euclidean lattice basis reduction. Experiments show that it returns quasi-optimal finite wordlength FIR filters; compared to previous approaches it also scales remarkably well (length 125 filters are treated in $<$ 9 s). It also proves useful for accelerating the determination of optimal finite wordlength FIR filters. [ABSTRACT FROM AUTHOR]

A new kind of filter called Legendre chained-function (LCF) filter with characteristic function given by the product of low-degree Legendre orthogonal polynomials (seed functions) is studied in this paper. LCF filter magnitude response exhibits unequal ripple level in the passband compared to Chebyshev chained-function filter with identical edge ripple factor at the passband edge. A proper combination of seed functions, i.e., a product of them, is used to control the maximum ripple in the passband, which affects the return loss, selectivity and a group delay characteristics of a filter. By selecting one of the possible combinations of seed functions (thus obtaining various degrees of freedom in filter design), filters with improved performances compared to traditional approximation techniques can be obtained. The degrees of freedom increase if the degree of filter increases. Compared to existing Chebyshev chained-function (CCF) filters, whose performances are also presented, and Butterworth function filters as a special case of both LCF and CCF filters, the new family of LCF filters has many advantages. A table summarizing properties of CCF and LCF filters is given for design purpose. [ABSTRACT FROM AUTHOR]

We analyze the computational complexity of the problem of optimally managing a storage device connected to a source of renewable energy, the power grid, and a household (or some other form of energy demand) in the presence of uncertainty. We provide a mathematical formulation for the problem as a Markov decision process following other models appearing in the literature, and study the complexity of determining a policy to achieve the maximum profit that can be attained over a finite time horizon, or simply the value of such profit. We show that if the problem is deterministic, i.e. there is no uncertainty on prices, energy production, or demand, the problem can be solved in strongly polynomial time. This is also the case in the stochastic setting if energy can be sold and bought for the same price on the spot market. If the sale and buying price are allowed to be different, the stochastic version of the problem is #P-hard, even if we are only interested in determining whether there exists a policy that achieves positive profit. Furthermore, no constant-factor approximation algorithm is possible in general unless P = NP. However, we provide a Fully Polynomial-Time Approximation Scheme (FPTAS) for the variant of the problem in which energy can only be bought from the grid, which is #P-hard. [ABSTRACT FROM AUTHOR]

We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the fewest sensors (the "hitting points"). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable. [ABSTRACT FROM AUTHOR]

We deal with a recently proposed method of Chubanov [A polynomial projection algorithm for linear feasibility problems. Math. Program. 153 (2015), pp. 687–713] for solving linear homogeneous systems with positive variables. Some improvements of Chubanov's method and its analysis are presented. We propose a new and simple cut criterion and show that the cuts defined by the new criterion are at least as sharp as in [1]. The new cut criterion reduces the iteration bound for his Basic Procedure by a factor 5, without changing the order of its strongly polynomial complexity. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses our Modified Basic Procedure as a subroutine. It is shown that it hastime complexity, just as in [1]. Some promising computational results are presented, in comparison with the optimization package Gurobi. [ABSTRACT FROM AUTHOR]

BigBand is a technique for wideband spectrum sensing (WSS) that can capture gigahertz of sparse spectrum in real time by using shifted multiple channels without sampling the signal at GS/s. In this paper, we focus on enforcing BigBand with the proposed improved algorithm, namely, AD-BigBand, for efficient and robust computation. AD-BigBand converts the nonlinear process (locating frequency and computing the spectrum value) of sparse WSS into two steps of solving linear equations. In particular, we define an r -degree frequency locator polynomial to rapidly locate nonzero frequencies. The computing complexity of the proposed method decreases from O(K{\log ^2}K ({{{n\log K} \over K}})^{\log K}) of shifted sampling based BigBand to O(K{\log ^2}K)$, where the $K$-sparse signals of bandwitdth $n$ are subsampled with arithmetic time-shifted sensing channels. We implement AD-BigBand on a commercial four-channel acquisition card. Experimental results show that AD-BigBand improves the WSS capabilities and exhibits higher processing speed and lower error spectrum construction rate than BigBand, especially in the case of relative low signal-to-noise ratio. [ABSTRACT FROM AUTHOR]

A central question in information theory is to determine the maximum success probability that can be achieved in sending a fixed number of messages over a noisy channel. This was first studied in the pioneering work of Shannon, who established a simple expression characterizing this quantity in the limit of multiple independent uses of the channel. Here, we consider the general setting with only one use of the channel. We observe that the maximum success probability can be expressed as the maximum value of a submodular function. Using this connection, we establish the following results: 1) There is a simple greedy polynomial-time algorithm that computes a code achieving a (1-e^-1) -approximation of the maximum success probability. The factor (1-e^-1) can be improved arbitrarily close to 1 at the cost of slightly reducing the number of messages to be sent. Moreover, it is NP-hard to obtain an approximation ratio strictly better than (1-e^-1) for the problem of computing the maximum success probability. 2) Shared quantum entanglement between the sender and the receiver can increase the success probability by a factor of at most (1/(1-e^-1)) . In addition, this factor is tight if one allows an arbitrary non-signaling box between the sender and the receiver. 3) We give tight bounds on the one-shot performance of the meta-converse of Polyanskiy-Poor-Verdú. [ABSTRACT FROM AUTHOR]

We study the polynomial time approximation of the NP -hard max k - vertex cover problem in bipartite graphs and propose purely combinatorial approximation algorithms . The main result of the paper is a simple combinatorial algorithm and a computer-assisted analysis of its approximation guarantee giving strong evidence that the worst approximation ratio achieved is bounded below by 0.821. We also study two simpler strategies with provable approximation ratios of 2 3 and 34 47 ≈ 0 . 72 respectively that already beat the only such known algorithm, namely the greedy approach which guarantees ratio ( 1 − 1 e ) ≈ 0 . 632 . Our principal motivation is to bring a satisfactory answer in the following question: to what extent combinatorial methods for max k - vertex cover compete with linear programming ones? [ABSTRACT FROM AUTHOR]

A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed. [ABSTRACT FROM AUTHOR]

Complex polynomial optimization has recently gained more attention in both theory and practice. In this paper, we study optimization of a real-valued general conjugate complex form over various popular constraint sets including the m-th roots of complex unity, the complex unit circle, and the complex unit sphere. A real-valued general conjugate complex form is a homogenous polynomial function of complex variables as well as their conjugates, and always takes real values. General conjugate form optimization is a wide class of complex polynomial optimization models, which include many homogenous polynomial optimization in the real domain with either discrete or continuous variables, and Hermitian quadratic form optimization as well as its higher degree extensions. All the problems under consideration are NP-hard in general and we focus on polynomial-time approximation algorithms with worst-case performance ratios. These approximation ratios improve previous results when restricting our problems to some special classes of complex polynomial optimization, and improve or equate previous results when restricting our problems to some special classes of polynomial optimization in the real domain. The algorithms are based on tensor relaxation and random sampling. Our novel technical contributions are to establish the first set of probability lower bounds for random sampling over the m-th root of unity, the complex unit circle, and the complex unit sphere, and to propose the first polarization formula linking general conjugate forms and complex multilinear forms. Some preliminary numerical experiments are conducted to show good performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is NP -complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path-forests if the number of arms and components, respectively, are fixed. Finally, we describe a polynomial time approximation algorithm with approximation factor 3 for general graphs. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some efficient algorithms are presented and numerical results are reported to show the efficiency of our proposed algorithms. [ABSTRACT FROM AUTHOR]

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, includes planar graphs, and in particular is a subset of the family of graphs that have polynomial expansion. We present efficient (1+ε)-approximation algorithms for polynomial expansion graphs for unweighted Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTASs for these problems are known for subclasses of this graph family. These results have immediate applications in the geometric domain. For example, the new algorithms yield the only PTAS known for covering points by fat triangles (that are shallow). We also prove corresponding hardness of approximation for some of these optimization problems, characterizing their intractability with respect to density. For example, we show that there is no PTAS for covering points by fat triangles if they are not shallow, thus matching our PTAS for this problem with respect to depth. [ABSTRACT FROM AUTHOR]

Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a variation of the known shifting strategy that allows us to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate the applicability of the proposed variation, we obtain results for three well-known optimization problems. Among such results, the proposed method yields linear-time -approximations for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing significant performance improvements when compared to previous algorithms that achieve the same approximation ratios. Finally, we use axis-aligned rectangles to illustrate that the same method may be used to derive linear-time approximations for problems on other geometric intersection graph classes. [ABSTRACT FROM AUTHOR]

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order $O(n\psi \log (n\psi ))$ , where \psi = \sqrt {P\|{\text{h}}\|^{2}+1} depends on the transmission power and the norm of the channel vector. We will then extend our results to integer-forcing and finally introduce a more general class of lattices for which the SVP and the closest vector problem can be approximated within a constant factor. [ABSTRACT FROM PUBLISHER]

We get a formula for all finite Riordan involutions. Using the natural approximation induced by the inverse limit construction, we also describe all infinite Riordan matrices which are involutions in the Riordan group. Finally, we get some consequences. [ABSTRACT FROM AUTHOR]

With mobile devices increasingly able to connect to cloud servers from anywhere, resource-constrained devices can potentially perform offloading of computational tasks to either save local resource usage or improve performance. It is of interest to find optimal assignments of tasks to local and remote devices that can take into account the application-specific profile, availability of computational resources, and link connectivity, and find a balance between energy consumption costs of mobile devices and latency for delay-sensitive applications. We formulate an NP-hard problem to minimize the application latency while meeting prescribed resource utilization constraints. Different from most of existing works that either rely on the integer programming solver, or on heuristics that offer no theoretical performance guarantees, we propose Hermes, a novel fully polynomial time approximation scheme (FPTAS). We identify for a subset of problem instances, where the application task graphs can be described as serial trees, Hermes provides a solution with latency no more than (1+\epsilon) times of the minimum while incurring complexity that is polynomial in problem size and \frac{1}{\epsilon} . We further propose an online algorithm to learn the unknown dynamic environment and guarantee that the performance gap compared to the optimal strategy is bounded by a logarithmic function with time. Evaluation is done by using real data set collected from several benchmarks, and is shown that Hermes improves the latency by 16$ percent compared to a previously published heuristic and increases CPU computing time by only $0.4$ percent of overall latency. [ABSTRACT FROM AUTHOR]

We present a numerical method for polynomial approximation of multivariate functions. The method utilizes Gauss quadrature in tensor product form, which is known to be inefficient in high dimensions. Here we demonstrate that by using a new randomized algorithm and taking advantage of the tensor structure of the grids, a highly efficient algorithm can be constructed. The new method does not require prior knowledge/storage of the entire data set at all the tensor grid points, whose total number of points is excessively large in high dimensions. Instead the method utilizes one data point at a time and iteratively conducts the approximation. This feature allows the use of the method irrespective of the size of the data set. We establish the rate of convergence of this iterative algorithm and show that its operational counts can be lower than the standard methods, when applicable, such as least squares. Numerical examples in up to hundreds of dimensions are presented to verify the theoretical analysis and demonstrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]