Semigroups Generated by Ordinary Differential Operators in L 1(I)*

In this paper we give necessary and sufficient conditions for the existence of a C> ₀-semigroup in L ¹(I) (I real interval) generated by a second-order differential operator when suitable boundary conditions at the endpoints are imposed.     

Stable determination of an inhomogeneous inclusion by local boundary measurements

We deal with the problem of determining an inclusion within an electrostatic conductor from boundary measurements. Under mild a priori assumptions we establish optimal stability estimates. Measurements are performed on a portion of the boundary of the conductor.     

Packing into the smallest square: Worst-case analysis of lower bounds

We address the problem of packing a given set of rectangles into the minimum size square. We consider three versions of the problem, arising when the rectangles (i) are squares; (ii) have a fixed orientation; (iii) can be rotated by 90. For each case we study lower bounds, and analyze their worst-case performance ratio. In addition, we evaluate through computational experiments their average performance on instances from the literature.     

A remark on Serrin’s Theorem

An approximation theorem for families of weakly coercive convex functions by means of countably many smooth families of convex functions is proved. As a consequence, the classical “three-fold” lower semicontinuity theorem for integral functionals of the Calculus of Variations by James Serrin is unified in one single statement.     

Ab initio path-integral molecular dynamics

A path-integral molecular dynamics technique for strongly interacting atoms using ab initio potentials derived from density functional theory is implemented. This allows the efficient inclusion of nuclear quantum dispersion in ab initio simulations at finite temperatures. We present an application to the quantum cluster H ₅ ⁺ .     

General theorems and fundamental solutions in the dynamical theory of mixtures

This paper is concerned with the dynamic theory of a binary mixture consisting of a gas and an elastic solid. First, we derive general theorems (reciprocal theorem, uniqueness theorem, minimum principle). The, we establish a Galerkin representation and the fundamental solutions in the case of steady vibrations.Work performed under the auspices of G.N.F.M. of the Italian Research Council (C.N.R.), with the grant 60% M.U.R.S.T. (ITALY).     

Integer linear programming models for 2-staged two-dimensional Knapsack problems

 We are given a unique rectangular piece of stock material S, with height H and width W, and a list of m rectangular shapes to be cut from S. Each shape's type i (i = 1, ..., m) is characterized by a height , a width , a profit , and an upper bound ub _i indicating the maximum number of items of type i which can be cut. We refer to the Two-Dimensional Knapsack (TDK) as the problem of determining a cutting pattern of S maximizing the sum of the profits of the cut items. In particular, we consider the classical variant of TDK in which the maximum number of cuts allowed to obtain each item is fixed to 2, and we refer to this problem as 2-staged TDK (2TDK). For the 2TDK problem we present two new Integer Linear Programming models, we discuss their properties, and we compare them with other formulations in terms of the LP bound they provide. Finally, both models are computationally tested within a standard branch-and-bound framework on a large set of instances from the literature by reinforcing them with the addition of linear inequalities to eliminate symmetries. Received: October 17, 2000 / Accepted: December 19, 2001 Published online: September 27, 2002 Key words. packing – cutting – integer linear programming     

The unsatisfiability threshold revisited

The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper, we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for the occupancy problem in schemes of random allocation of balls into bins in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. In order to obtain this value, we establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients). No such bound was previously known, despite the extensive literature on q-binomial coefficients. Finally, to prove our result we had to establish certain relations among the conditional probabilities of an event in various probabilistic models for random formulas. It turned out that these relations were considerably harder to prove than the corresponding ones for unconditional probabilities, which were previously known.