A new fully polynomial time approximation scheme for the interval subset sum problem

The interval subset sum problem (ISSP) is a generalization of the well-known subset sum problem. Given a set of intervals \(\left\{ [a_{i,1},a_{i,2}]\right\} _{i=1}^n\) and a target integer T, the ISSP is to find a set of integers, at most one from each interval, such that their sum best approximates the target T but cannot exceed it. In this paper, we first study the computational complexity of the ISSP. We show that the ISSP is relatively easy to solve compared to the 0–1 knapsack problem. We also identify several subclasses of the ISSP which are polynomial time solvable (with high probability), albeit the problem is generally NP-hard. Then, we propose a new fully polynomial time approximation scheme for solving the general ISSP problem. The time and space complexities of the proposed scheme are \({{\mathcal {O}}}\left( n \max \left\{ 1 / \epsilon ,\log n\right\} \right) \) and \(\mathcal{O}\left( n+1/\epsilon \right) ,\) respectively, where \(\epsilon \) is the relative approximation error. To the best of our knowledge, the proposed scheme has almost the same time complexity but a significantly lower space complexity compared to the best known scheme. Both the correctness and efficiency of the proposed scheme are validated by numerical simulations. In particular, the proposed scheme successfully solves ISSP instances with \(n=100{,}000\) and \(\epsilon =0.1\%\) within 1 s.     

Deficiency numbers of operators generated by infinite Jacobi matrices

New conditions for minimality, maximality, and nonmaximality of deficiency numbers of the minimal operator generated by the infinite Jacobi matrix with m × m matrix entries in the Hilbert space of mdimensional vectors are presented. Special attention is given to the case m = 1, i.e., to conditions on the elements of a tridiagonal numerical Jacobi matrix under which the determinate case of the classical power moment problem is realized.     

Calculation of stresses in multilayer cylindrical articles made of variously combined composite materials

Both residual and working stresses are analyzed which appear in thick-walled cylindrical articles made of variously combined composite materials. A conservative homogeneous difference scheme is constructed for a "throughway" numerical integration of the resolvent equation in the Lamé problem of a compound cylinder. With the aid of this equation, the stress distribution is analyzed for multilayer structures with various ratios of layer thicknesses and various layer sequences.     

On approximation of the best case optimal value in interval linear programming

Interval linear programming addresses problems with uncertain coefficients and the only information that we have is that the true values lie somewhere in the prescribed intervals. For the inequality constraint problem, computing the worst case scenario and the corresponding optimal value is an easy task, but the best case optimal value calculation is known to be NP-hard. In this paper, we discuss lower and upper bound approximation for the best case optimal value, and propose suitable methods for both of them. We also propose a not apriori exponential algorithm for computing the best case optimal value. The presented techniques are tested by randomly generated data, and also applied in a simple data classification problem.     

Mapping integers and hensel codes onto Farey fractions

The order-N Farey fractions, whereN is the largest integer satisfyingN≦√((p?1)/2), can be mapped onto a proper subset of the integers {0, 1,...,p?1} in a one-to-one and onto fashion. However, no completely satisfactory algorithm for affecting the inverse mapping (the mapping of the integers back onto the order-N Farey fractions) appears in the literature. A new algorithm for the inverse mapping problem is described which is based on the Euclidean Algorithm. This algorithm solves the inverse mapping problem for both integers and the Hensel codes of Krishnamurthy et al.     

Stochastic optimization theory in Hilbert spaces—1

We study a class of stochastic optimization problems in which the state as well as the observation spaces are permitted to be (Hilbert spaces) of non-finite dimension. Although there have been previous attempts in the Hilbert space setting, our results, techniques, as well as applications, are totally different. We initiate the use of Gauss measure on a Hilbert space even though it is only finitely additive; and an associated theory of white noise, in contrast to the Wiener process theory, which is novel even in the finite dimensional case. We only treat time-invariant systems, but no strong ellipticity or coercivity conditions are used; we exploit the theory of semigroups of operators in contrast to the Lions-Magenes theory. A key result involves a far-reaching generalization of the Factorization theorem of Krein. We apply the results to the problem of boundary observation and control for partial differential equations. By the creation of a special state space, we can apply the theory to problems in which the state equations are finitedimensional but the noise does not have a rational spectrum. In a final section, we present a stochastic theory for inverse problems (System Identification) in the Hilbert space setting. The basic theoretical problem is the calculation of R-N derivatives for finitely additive measures. A fundamental result concerns Identifiability; in particular the identifiability of diffusion coefficients from boundary data is treated here for the first time.     

Semi-infinite programming duality for order restricted statistical inference models

The equivalence of multinomial maximum likelihood and the isotonic projection problem: $$\inf \left\{ {\sum\limits_{i = 1}^n {p_i \ln (p_i /r_i )|p \in K,a convex} {\mathbf{ }}subset of the probability vectors{\mathbf{ }}p} \right\}$$ can be established using Fenchel's Duality Theorem and subgradient and complementary slackness relationships of convex analysis, all taking place over the real numbers. In this paper non-Archimedean polynomial subgradients (Jeroslow/Kortanek '71, Blair '74, Borwein '80, and Kortanek/Soyster '81) are employed for the case where some of the observed values of the random vector are zero, corresponding to “zero counts in the traditional multinomial setting.” With an appropriate linear semi-infinite programming dual pair it is shown that a vector solves the multinomial problem if and only if it converts to a solution of the isotonic projection problem. The development parallels the one of Robertson/Wright/Dykstra '88, where for the zero counts case the authors adjoin “-∞” to the real numbers and define ln(0)=-∞.     

A multipoint boundary value problem for systems of linear generalized differential equations with singularities

We study a multipoint boundary value problem for systems of Kurzweil generalized linear differential equations with singularities on a finite closed interval of the real line. We assume that the offdiagonal entries of the matrix function corresponding to the system, as well as the elements of the right-hand side of the system, have bounded variation on the entire interval; however, the diagonal entries of the matrix function are not assumed to have bounded variation on the entire interval. This is what we mean by saying that the system is singular. We study the unique solvability of the problem. We prove a general theorem and use it to we obtain efficient optimal (in particular, spectral) solvability conditions for the problem.     

Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem

The strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given sizes (cardinalities) minimizing the sum (over both clusters) of the intracluster sums of squared distances from the elements of the clusters to their centers is considered. It is assumed that the center of one of the sought clusters is specified at the desired (arbitrary) point of space (without loss of generality, at the origin), while the center of the other one is unknown and determined as the mean value over all elements of this cluster. It is shown that unless P = NP, there is no fully polynomial-time approximation scheme for this problem, and such a scheme is substantiated in the case of a fixed space dimension.     

An integer linear formulation for the file transfer scheduling problem

In this paper, we propose a new integer linear programming (ILP) formulation for solving a file transfer scheduling problem (FTSP), which is to minimize the overall time needed to transfer all files to their destinations for a given collection of various sized files in a computer network. Each computer in this network has a limited number of communication ports. The described problem is proved to be NP-hard in a general case. Our formulation enables solving the problem by standard ILP solvers like CPLEX or Gurobi. To prove the validity of the proposed ILP formulation, two new reformulations of FTSP are presented. The results obtained by CPLEX and Gurobi solvers, based on this formulation, are presented and discussed.     

Structural questions with GERT-networks

LetN be a GERT network with sinks, representing the termination of the project. There are two natural questions to ask: Cans be activated at all? And if so, is the activation ofs sure? After having shown the first question to be NP-complete and the second to be NP-hard, we state some structural results for the bipartite case which can be reduced to a flow problem. From this we derive a theoretical algorithm for the general case, which is — not surprisingly — exponential. Moreover, a connection to reliability analysis is revealed.     

Global regularity for solutions to Dirichlet problem for discontinuous elliptic systems with nonlinearity q > 1 and with natural growth

In this paper we deal with the Hölder regularity up to the boundary of the solutions to a nonhomogeneous Dirichlet problem for second-order discontinuous elliptic systems with nonlinearity q > 1 and with natural growth. The aim of the paper is to clarify that the solutions of the above problem are always global Hölder continuous in the case of the dimension n = q without any kind of regularity assumptions on the coefficients. As a consequence of this sharp result, the singular sets $\Omega_0 \subset \OmegaIn this paper we deal with the H?lder regularity up to the boundary of the solutions to a nonhomogeneous Dirichlet problem for second-order discontinuous elliptic systems with nonlinearity q > 1 and with natural growth. The aim of the paper is to clarify that the solutions of the above problem are always global H?lder continuous in the case of the dimension n = q without any kind of regularity assumptions on the coefficients. As a consequence of this sharp result, the singular sets , are always empty for n = q. Moreover we show that also for 1 < q < 2, but q close enough to 2, the solutions are global H?lder continuous for n = 2.      

Radial deformation of a nonhomogeneous spherically isotropic elastic sphere with a concentric spherical inclusion

The elasticity of a spherically isotropic medium bounded by two concentric spherical surfaces subjected to normal pressures is discussed. The material of the structure is spherically isotropic and, in addition, is continuously inhomogeneous with mechanical properties varying exponentially as the square of the radius. An exact solution of the problem in terms of Whittaker functions is presented. The St. Venant’s solution in the case of homogeneous material and Lamé’s solution in the case of homogeneous isotropic material are derived from the general solution. The problem of a solid sphere of the same medium under the external pressure is also solved as a particular case of the above problem. Finally, the displacements and stresses of a composite sphere consisting of a solid spherical body made of homogeneous material and a nonhomogeneous concentric spherical shell covering the inclusion, both of them being spherically isotropic, are obtained when the sphere is under uniform compression.     

On iterative processes generating dense point sets

Summary The central problem of this paper is the question of denseness of those planar point sets <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"3"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"4"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"5"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>\mathcal{P}$, not a subset of a line, which have the property that for every three noncollinear points in $\mathcal{P}$, a specific triangle center (incenter (IC), circumcenter (CC), orthocenter (OC) resp.) is also in the set $\mathcal{P}$. The IC and CC versions were settled before. First we generalize and solve the CC problem in higher dimensions. Then we solve the OC problem in the plane essentially proving that $\mathcal{P}$ is either a dense point set of the plane or it is a subset of a rectangular hyperbola. In the latter case it is either a dense subset or it is a special discrete subset of a rectangular hyperbola.     

Infinitesimal CR automorphisms of rigid hypersurfaces in C2

In this paper, we describe the space of infinitesimal CR automorphisms of a rigid, real analytic, real hypersurface in C². We use these results to obtain a geometric characterization of the homogeneous hypersurfaces. Here, a hypersurface is called homogeneous if it is equivalent to one given by an equation of the formIm(w) =p wherep is a homogeneous polynomial inz and \(\bar z\) . This gives an answer in dimension 2 to a problem posed by Linda Rothschild. We give another answer, in terms of a normal form for the defining function, in our paper “A normal form for rigid hypersurfaces in C².”     

Splitting scheme for poroelasticity and thermoelasticity problems

Boundary value problems in thermoelasticity and poroelasticity (filtration consolidation) are solved numerically. The underlying system of equations consists of the Lamé stationary equations for displacements and nonstationary equations for temperature or pressure in the porous medium. The numerical algorithm is based on a finite-element approximation in space. Standard stability conditions are formulated for two-level schemes with weights. Such schemes are numerically implemented by solving a system of coupled equations for displacements and temperature (pressure). Splitting schemes with respect to physical processes are constructed, in which the transition to a new time level is associated with solving separate elliptic problems for the desired displacements and temperature (pressure). Unconditionally stable additive schemes are constructed by choosing a weight of a three-level scheme.     

Heuristic methods for single link shared backup path protection

Protecting communication networks against failures is becoming increasingly important as they have become an integrated part of our society. Cable failures are fairly common, but it is unacceptable for a single cable failure to disconnect communication for more than a few seconds—hence protection schemes are employed. In contrast to manual intervention, automatic protection schemes such as shared backup path protection (SBPP) can recover from failure quickly and efficiently. SBPP is a simple but efficient protection scheme that can be implemented in backbone networks with technology available today. In SBPP backup paths are planned in advance for every failure scenario in order to recover from failures quickly and efficiently. Planning SBPP is an NP-hard optimization problem, and previous work confirms that it is time-consuming to solve the problem in practice using exact methods. We present heuristic algorithms and lower bound methods for the SBPP planning problem. Experimental results show that the heuristic algorithms are able to find good quality solutions in minutes. A solution gap of less than \(3.5~\%\) was achieved for 5 of 7 benchmark instances (and a gap of less than \(11~\%\) for the remaining instances.)     

Oscillation theorems for Sturm-Liouville problems with distribution potentials

The Sturm-Liouville problem

$\begin{array}{*{20}c} { - y'' + q(x)y = \lambda y,} \\ {y(0) = y(1) = 0} \\ \end{array} $

is considered with a singular potential q(x) representing the derivative of a real function from the space L ₂[0, 1] in the distributional sense. Two approaches are developed for the study of oscillation properties of eigenfunctions of this problem. The first approach is based on generalization of methods of the Sturm theory. The second one is based on development of variational principles.

     

Solvability of boundary-value problems for nonlinear elliptic equations that are not in the divergence form

One introduces a topological characteristic of general nonlinear elliptic problems, one establishes the solvability of the Dirichlet problem for the Monge-Ampere equations and the solvability of the general nonlinear Dirichlet problem in a thin layer.