An extended collocation method

Given an approximate solutionx _n of a linear operator equation obtained by a collocation method, an improved solutionx ^* _n+m is obtained fromx _n by an «extended collocation method» which consists in solving a further (m)-order linear system instead of an (n+m)-order one, diminishing the effects of rounding error in carrying out the calculations. For a suitable choice of the knot, the method may be recursively performed both by spline approximation and by algebraic and trigonometric polynomial approximation. A numerical example with a two point boundary value problem confirms the advantages of the extended method with respect to the direct one.     

Efficient uncertainty quantification with the polynomial chaos method for stiff systems

The polynomial chaos (PC) method has been widely adopted as a computationally feasible approach for uncertainty quantification (UQ). Most studies to date have focused on non-stiff systems. When stiff systems are considered, implicit numerical integration requires the solution of a non-linear system of equations at every time step. Using the Galerkin approach the size of the system state increases from n to S × n, where S is the number of PC basis functions. Solving such systems with full linear algebra causes the computational cost to increase from O(n³) to O(S³n³). The S³-fold increase can make the computation prohibitive. This paper explores computationally efficient UQ techniques for stiff systems using the PC Galerkin, collocation, and collocation least-squares (LS) formulations. In the Galerkin approach, we propose a modification in the implicit time stepping process using an approximation of the Jacobian matrix to reduce the computational cost. The numerical results show a run time reduction with no negative impact on accuracy. In the stochastic collocation formulation, we propose a least-squares approach based on collocation at a low-discrepancy set of points. Numerical experiments illustrate that the collocation least-squares approach for UQ has similar accuracy with the Galerkin approach, is more efficient, and does not require any modification of the original code.     

Algebraic approach to the interval linear static identification,tolerance, and control problems,or one more application of kaucher arithmetic

In this paper, theidentification problem, thetolerance problem, and thecontrol problem are treated for the interval linear equation Ax=b. These problems require computing an inner approximation of theunited solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, of thetolerable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, and of thecontrollable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?b ∈ b)(Ax ∈b)} respectively. Analgebraic approach to their solution is developed in which the initial problem is replaced by that of finding analgebraic solution of some auxiliary interval linear system in Kaucher extended interval arithmetic. The algebraic approach is proved almost always to give inclusion-maximal inner interval estimates of the solutionsets considered. We investigate basic properties of the algebraic solutions to the interval linear systems and propose a number of numerical methods to compute them. In particular, we present the simple and fastsubdifferential Newton method, prove its convergence and discuss numerical experiments.     

Mapping two complete binary trees into the star graph with quick fault recovery

This paper proposes an approach for embedding two complete binary trees (CBT) into ann-dimensional star graph (S _n), and provides a fault-tolerant scheme for the trees. First, aCBT with height Σ _m=2 ⁿ ?logm? is embedded into theS _n with dilation 3. The height of theCBT is very close to ?Σ _m=2 ⁿ logm?, the height of the largest possibleCBT which can be embedded into theS _n. Shifting the firstCBT by generating function productg ₂ g ₃ g ₄ g ₃, anotherCBT with height Σ _m=2 ⁿ ?logm? can also be embedded into theS _n without conflicting with the first one. Moreover, if three-eights of nodes in the firstCBT and all nodes in the secondCBT are faulty, all of them can be recovered. Under the condition that the firstCBT with smaller height (?Σ _m=2 ⁿ logm? ? 1) is embedded, all the replacement nodes will be free. As a consequence, even in the case that all nodes in the two trees are faulty, they can be recovered in the smallest number of recovery steps and only with dilation 5.     

A linear-time algorithm for linearL 1 approximation of points

In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL ₁ norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n ³) naive algorithm can be easily obtained based on some simple characteristics of an optimumL ₁ solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL ₁ approximation of many points in practice. The complexity ofL ₁ linear approximation of a piecewise linear function is also touched upon.     

A note on collocation methods for Volterra integral equations of the first kind

It has been shown that if a Volterra integral equation of the first kind with continuous kernel is solved numerically in a given intervalI by collocation in the space of piecewise polynomials of degreem≧0 and possessing finite discontinuities at their knotsZ _N then a careful choice of the collocation points yields convergence of orderp=m+2 on a certain finite subset ofI (while the global convergence order ism+1; this subset does not contain the knotsZ _N . In this note it will be shown that superconvergence onZ _N can be attained only if some of the collocation points coalesce (Hermite-type collocation).     

Real and complex-exponential describing functions for transient analysis of non-linear control systems†

A real exponential describing function as an analysis tool for studying the transient response of a class of non-linear feedback systems was developed by Bickart (1966). In this paper describing functions are developed for similar analysis more suitable to higher-order non-linear feedback systems. The two classes of describing functions developed are identified as real exponential or complex exponential.

Here, signals in ?₂ ( ? ∞, t] a space of the space of square integrable signals defined on (?∞, t ], are approximated by the sum of n signals in ?₂ ^{1, m} (?∞, t)one-dimensional sub-spaccs of ?₂ ( ? ∞, t] having the mth function from the set of reversed time orthogonalized real or eponential functions as a basis. A system mapping ?₂ ^{1, m}(?∞, t] into itself is associated with a system mapping ?₂ ^{1, m}(?∞, t] into itself; the latter system is characterized by a gain—real or exponential describing function. These multiple one-dimensional system mappings give rise to approximation components of the response whoso addition will represent a better approximation to the actual response than each component by itself. The contraction-mapping fixed point theorem is also used to determine conditions for the existence of a solution prior to the use of the exponential describing functions for obtaining on approximate response.     

The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containingm_ielements of typei, 1⩽i⩽n, are the numbersF_k=∑ⁿ_i=1 m^k_i. We consider the space complexity of randomized algorithms that approximate the numbersF_k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF₀,F₁, andF₂can be approximated in logarithmic space, whereas the approximation ofF_kfork⩾6 requiresn^Ω(1)space. Applications to data bases are mentioned as well.     

On the hardness of approximating Max-Satisfy

Max-Satisfy is the problem of finding an assignment that satisfies the maximum number of equations in a system of linear equations over Q. We prove that unless NP⊂BPP Max-Satisfy cannot be efficiently approximated within an approximation ratio of 1/n1−?, if we consider systems of n linear equations with at most n variables and ?>0 is an arbitrarily small constant. Previously, it was known that the problem is NP-hard to approximate within a ratio of 1/nα, but 0<α<1 was some specific constant that could not be taken to be arbitrarily close to 1.     

Video distribution under multiple constraints

We consider the optimization problem of providing a set of video streams to a set of clients, where each stream has costs in m possible measures (such as communication bandwidth, processing bandwidth, etc.), and each client has its own utility function for each stream. We assume that the server has a budget cap on each of the m cost measures; each client has an upper bound on the utility that can be derived from it, and potentially also upper bounds in each of the m cost measures. The task is to choose which streams the server will provide, and out of this set, which streams each client will receive. The goal is to maximize the overall utility subject to the budget constraints. We give an efficient approximation algorithm with approximation factor of O(m) with respect to the optimal possible utility for any input, assuming that clients have only a bound on their maximal utility. If, in addition, each client has at most m_c capacity constraints, then the approximation factor increases by another factor of O(m_clogn), where n is the input length. We also consider the special case of “small” streams, namely where each stream has cost of at most O(1/logn) fraction of the budget cap, in each measure. For this case we present an algorithm whose approximation ratio is O(logn).     

On the determination of the weights in multi-dimensional numerical quadrature

Using the concept of the generalized inverse of a bounded linear transformation between ? ⁿ andl ₂, a method is given for constructing quadrature rules for integration over an arbitrary boundedm-dimensional regionB?? ^m with the property that the average error over the prescribed familyF of the functions continuous inB as well as the variance of the rounding errors according to Sard [8] are minimal. Then we specializeF to the weighted monomials and treat as an example integration on the surface of them-sphere.     

Pseudospectral methods for solving infinite-horizon optimal control problems

An important aspect of numerically approximating the solution of an infinite-horizon optimal control problem is the manner in which the horizon is treated. Generally, an infinite-horizon optimal control problem is approximated with a finite-horizon problem. In such cases, regardless of the finite duration of the approximation, the final time lies an infinite duration from the actual horizon at t=+∞. In this paper we describe two new direct pseudospectral methods using Legendre–Gauss (LG) and Legendre–Gauss–Radau (LGR) collocation for solving infinite-horizon optimal control problems numerically. A smooth, strictly monotonic transformation is used to map the infinite time domain t∈[0,∞) onto a half-open interval τ∈[−1,1). The resulting problem on the finite interval is transcribed to a nonlinear programming problem using collocation. The proposed methods yield approximations to the state and the costate on the entire horizon, including approximations at t=+∞. These pseudospectral methods can be written equivalently in either a differential or an implicit integral form. In numerical experiments, the discrete solution exhibits exponential convergence as a function of the number of collocation points. It is shown that the map ?:[−1,+1)→[0,+∞) can be tuned to improve the quality of the discrete approximation.     

Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood

LetA=(a _ij ) be the distance matrix of an arbitrary (asymmetric) traveling salesman problem and let τ=τ₁τ₂...τ _m be the optimal solution of the corresponding assignment problem with the subtours τ=τ₁τ₂...τ _m . By choosing (m?1) transpositions (k, l) withk ∈ τ _i?1,l ∈ τ _i (i=2, ...,m) and patching the subtours by using these transpositions in any order, we get a set of cyclic permutations. It will be shown that within this set of cyclic permutations a tour with minimum distance can be found by O(n ²|τ|* operations, where |τ|* is the maximum number of nodes in a subtour of τ. Moreover, applying this result to the case whenA=(a _ij ) is a permuted distribution matrix (Monge-matrix) and thepatching graph G _τ is a multipath, a result of Gaikov can be improved: By combining the above theory with a result of Park alinear algorithm for finding an optimal TSP solution can be derived, provided τ is already known.     

On the independence number and Hamiltonicity of uniform random intersection graphs

In the uniform random intersection graphs model, denoted by G_n,m,λ, to each vertex v we assign exactly λ randomly chosen labels of some label set M of m labels and we connect every pair of vertices that has at least one label in common. In this model, we estimate the independence number α(G_n,m,λ), for the wide range m=⌊n^α⌋,α<1 and λ=O(m^1/4). We also prove the Hamiltonicity of this model by an interesting combinatorial construction. Finally, we give a brief note concerning the independence number of G_n,m,p random intersection graphs, in which each vertex chooses labels with probability p.     

Maximizing the minimum load for selfish agents

We consider the problem of maximizing the minimum load (completion time) for machines that are controlled by selfish agents, who are only interested in maximizing their own profit. Unlike the classical load balancing problem, this problem has not been considered for selfish agents until now. The goal is to design a truthful mechanism, i.e., one in which all users have an incentive to tell the truth about the speeds of their machines. This then allows us to find good job assignments. It is known that this requires monotone approximation algorithms, in which the amount of work assigned to an agent does not increase if its bid (claimed cost per unit work) increases.For a constant number of machines, m, we show a monotone polynomial-time approximation scheme (PTAS) with running time that is linear in the number of jobs. It uses a new technique for reducing the number of jobs while remaining close to the optimal solution. We use an FPTAS for the classical problem, i.e., where no selfish agents are involved, to give a monotone FPTAS.Additionally, we give a monotone approximation algorithm with approximation ratio min(m,(2+ε)s₁/s_m) where ε>0 can be chosen arbitrarily small and s_i is the (real) speed of machine i. Finally we give improved results for two machines.     

An Improved Approximation Algorithm for the Most Points Covering Problem

In this paper we present a polynomial time approximation scheme for the most points covering problem. In the most points covering problem, n points in R ², r>0, and an integer m>0 are given and the goal is to cover the maximum number of points with m disks with radius r. The dual of the most points covering problem is the partial covering problem in which n points in R ² are given, and we try to cover at least p≤n points of these n points with the minimum number of disks. Both these problems are NP-hard. To solve the most points covering problem, we use the solution of the partial covering problem to obtain an upper bound for the problem and then we generate a valid solution for the most points covering problem by a careful modification of the partial covering solution. We first present an improved approximation algorithm for the partial covering problem which has a better running time than the previous algorithm for this problem. Using this algorithm, we attain a \((1 - \frac{{2\varepsilon }}{{1 +\varepsilon }})\)-approximation algorithm for the most points covering problem. The running time of our algorithm is \(O((1+\varepsilon )mn+\epsilon^{-1}n^{4\sqrt{2}\epsilon^{-1}+2}) \) which is polynomial with respect to both m and n, whereas the previously known algorithm for this problem runs in \(O(n \log n +n\epsilon^{-6m+6} \log (\frac{1}{\epsilon}))\) which is exponential regarding m.     

Scheduling two jobs with fixed and nonfixed routes

The shop-scheduling problem with two jobs andm machines is considered under the condition that the machine order is fixed in advance for the first job and nonfixed for the second job. The problems of makespan and mean flow time minimization are proved to be NP-hard if operation preemption is forbidden. In the case of preemption allowance for any given regular criterion theO(n _*) algorithm is proposed. Here,n _* is the maximum number of operations per job.     

Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs

We consider a problem of scheduling n identical nonpreemptive jobs with a common due date on m uniform parallel machines. The objective is to determine an optimal value of the due date and an optimal allocation of jobs onto machines so as to minimize a total cost function, which is the function of earliness, tardiness and due date values. For the problem under study, we establish a set of properties of an optimal solution and suggest a two-phase algorithm to tackle the problem. First, we limit the number of due dates one needs to consider in pursuit of optimality. Next, we provide a polynomial-time algorithm to build an optimal schedule for a fixed due date. The key result is an O(m² log m) algorithm that solves the main problem to optimality.Scope and purpose: To extend the existing research on cost minimization with earliness, tardiness and due date penalties to the case of uniform parallel machines.     

On the almost sure and almost uniform Lp(p ≥ 1) stability

In this paper a class of stochastic non-linear system which can be described by n nun-linear stochastic Volterra integral equation is considered. The problems of almost uniform L_P(R₀)(p≥1) stability and almost sure L_p(R₀) (p≥1) stability of the system arc then considered in detail.

In § 2, the random Banach fixed point theorem is used to show the existence and uniqueness of solution of the system. This result is then used to establish the almost sure L_p(R₀) (p≥1) stability and almost uniform L_p(R₀)(p≥1) stability for the system under consideration.

For illustration, an example of a feedback control system containing a non-linear amplifier with random gain is considered.     

The Tau Method as an analytic tool in the discussion of equivalence results across numerical methods

A Tau Method approximate solution of a given differential equation defined on a compact [a, b] is obtained by adding to the right hand side of the equation a specific minimal polynomial perturbation termH _n(x), which plays the role of a representation of zero in [a,b] by elements of a given subspace of polynomials. Neither discretization nor orthogonality are involved in this process of approximation. However, there are interesting relations between the Tau Method and approximation methods based on the former techniques. In this paper we use equivalence results for collocation and the Tau Method, contributed recently by the authors together with classical results in the literature, to identify precisely the perturbation termH(x) which would generate a Tau Method approximate solution, identical to that generated by some specific discrete methods over a given mesh Π ∈ [a, b]. Finally, we discuss a technique which solves the inverse problem, that is, to find adiscrete perturbed Runge-Kutta scheme which would simulate a prescribed Tau Method. We have chosen, as an example, a Tau Method which recovers the same approximation as an orthogonal expansion method. In this way we close the diagram defined by finite difference methods, collocation schemes, spectral techniques and the Tau Method through a systematic use of the latter as an analytical tool.