Scheduling on parallel identical machines to minimize total tardiness

This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

Homogenization of Linear Elastic Properties of Silicon Nitride

The effective linear elastic properties of silicon nitride (Si₃N₄) are estimated based on first–, third–, and fifth–order bounds of the strain energy density. This specific type of material is a mixture of two linear elastic materials with different material symmetries. The β-Si₃N₄ grains have a hexagonal symmetry with significant amount of anisotropy, whereas the glassy phase is approximately isotropic. The results are as follows: i) The fifth–order upper and lower bounds are almost identical. Therefore, these bounds are sufficient for estimating the effective elastic properties. ii) For fixed elastic constants of the hexagonal β-Si₃N₄ grains, the effective properties of Si₃N₄ are determined as a function of properties of the glassy phase and its volume fraction. The corresponding diagrams allow for the inverse identification of the elastic properties of the glassy phase. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Modular equations and distortion functions

Modular equations occur in number theory, but it is less known that such equations also occur in the study of deformation properties of quasiconformal mappings. The authors study two important plane quasiconformal distortion functions, obtaining monotonicity and convexity properties, and finding sharp bounds for them. Applications are provided that relate to the quasiconformal Schwarz Lemma and to Schottky’s Theorem. These results also yield new bounds for singular values of complete elliptic integrals.      

Packing vertices and edges in random regular graphs

In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239–298]. The upper bounds are proved by direct combinatorial means. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

GUARANTEED BOUNDS FOR THE SOLUTION OF THE WAVE EQUATION

Abstract

Numerical solution of the wave equation in the form of close lower and upper bounds provides a secure a posteriori error estimate that can be used for efficient accuracy control. The method considered in this paper uses some monotone properties of the differential operator in the wave equation to construct bounds for the solution in the form of trigonometric polynomials of x. Aspects of the numerical implementation, the accuracy of the computed bounds and some numerical examples are discussed.     

Bounds and Numerical Results for Homogenized Degenerated p-Poisson Equations

In this paper we derive upper and lower bounds on the homogenized energy density functional corresponding to degenerated p-Poisson equations. Moreover, we give some non-trivial examples where the bounds are tight and thus can be used as good approximations of the homogenized properties. We even present some cases where the bounds coincide and also compare them with some numerical results.     

Agard’s η-distortion function and Schottky’s theorem

The monotoneity properties of certain functions defined in terms of the η-distortion function ηκ(t) in quasiconformal theory are studied and asymptotically sharp bounds are obtained for ηκ(t), thus proving some properties of the upper bound functionK(t, r) in Schottky’s theorem on analytic functions and improving the known explicit bounds forK (t, r).     

Eigenvalue bounds for independent sets

We derive bounds on the size of an independent set based on eigenvalues. This generalizes a result due to Delsarte and Hoffman. We use this to obtain new bounds on the independence number of the Erdős–Rényi graphs. We investigate further properties of our bounds, and show how our results on the Erdős–Rényi graphs can be extended to other polarity graphs.     

Banach space properties sufficient for normal structure

In this paper we establish lower bounds for the weakly convergent sequence coefficient WCS(X) of a Banach space X, in terms of some well known moduli and coefficients. By mean of these bounds we identify several properties, of geometrical nature, which imply normal structure. We show that these properties are strictly more general than other previously known sufficient conditions for normal structure.     

Existence and bounds for the half-moment entropy approximation to radiative transfer

We establish existence, uniqueness and a priori bounds for the half-moment entropy approximation to radiative heat transfer. The bounds are physically reasonable and underline the approximation properties of the system. We show numerical results to illustrate the bounds.     

Bounds for non‐periodic mixtures of infinitely many materials

We prove bounds on the homogenized coefficients for general non‐periodic mixtures of an arbitrary number of isotropic materials, in the heat conduction framework. The component materials and their proportions are given through the Young measure associated to the sequence of coefficient functions. Upper and lower bounds inequalities are deduced in terms of algebraic relations between this Young measure and the eigenvalues of the H‐limit matrix. The proofs employ arguments of compensated compactness and fine properties of Young measures. When restricted to the periodic case, we recover known bounds. Copyright © 2005 John Wiley & Sons, Ltd.     

Implementing bounds-based approximations in convex-concave two-stage stochastic programming

This paper is concerned with implementational issues and computational testing of bounds-based approximations for solving two-stage stochastic programs with fixed recourse. The implemented bounds are those derived by the authors previously, using first and cross moment information of the random parameters and a convex-concave saddle property of the recourse function. The paper first examines these bounds with regard to their tightness, monotonic behavior, convergence properties, and computationally exploitable decomposition structures. Subsequently, the bounds are implemented under various partitioning/refining strategies for the successive approximation. The detailed numerical experiments demonstrate the effectiveness in solving large scenario-based two-stage stochastic optimization problems throughsuccessive scenario clusters induced by refining the approximations.     

Bounds on the largest root of the matching polynomial

We use properties of the dependence polynomial to prove several new bounds on the largest root of the matching polynomial. These bounds are compared with earlier bounds.     

Fast enclosure for the minimum norm least squares solution of the matrix equation AXB = C

Fast algorithms for enclosing the minimum norm least squares solution of the matrix equation AXB = C are proposed. To develop these algorithms, theories for obtaining error bounds of numerical solutions are established. The error bounds obtained by these algorithms are verified in the sense that all the possible rounding errors have been taken into account. Techniques for accelerating the enclosure and obtaining smaller error bounds are introduced. Numerical results show the properties of the proposed algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

Some upper and lower bounds on PSD-rank

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.     

Uniform bounds from bounded Lp-functionals in reaction-diffusion equations

To prove global existence of classical or mild solutions of reaction-diffusion equations, a priori bounds in the uniform norm are needed. But for interesting examples, often one can only derive bounds for some L_p-norms. Using the structure of the reaction term they can be used to obtain uniform bounds. Two propositions are stated which give conditions for this procedure. The proofs use the smoothing properties of analytic semigroups and the multiplicative Gagliardo-Nirenberg inequality. To illustrate the method, we prove global existence of solutions for the Brusselator and a Volterra-Lotka system with one diffusing and one sedentary species.     

Recurrent dimensions of quasi-periodic solutions for nonlinear evolution equations

In this paper we introduce recurrent dimensions of discrete dynamical systems and we give upper and lower bounds of the recurrent dimensions of the quasi-periodic orbits. We show that these bounds have different values according to the algebraic properties of the frequency and we investigate these dimensions of quasi-periodic trajectories given by solutions of a nonlinear PDE.

     

Laplace eigenvalues and bandwidth-type invariants of graphs

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min-sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min-sums of random graphs, random regular graphs, and Kneser graphs. © John Wiley & Sons, Inc.     

Computation of bounds for eigenvalues of structures with interval parameters

In this paper, the computation of eigenvalue bounds for generalized interval eigenvalue problem is considered. Two algorithms based on the properties of continuous functions are developed for evaluating upper and lower eigenvalue bounds of structures with interval parameters. The method can provide the tightest bounds within a given precision. Numerical examples illustrate the effectiveness of the proposed method.