Stabilization through viscoelastic boundary damping: a semigroup approach

The undamped linear wave equation on a bounded domain in ℝ ⁿ with C ² boundary is considered. The interaction of the interior waves and the viscoelastic boundary material is modeled by convolution boundary conditions. It is assumed that the convolution kernel is integrable and completely monotonic. The main result is that the derivatives of all solutions tend to zero. The proof is given by an application of the Arendt-Batty-Lyubic-Vu Theorem. To this end, the model is reformulated as an abstract first order Cauchy problem in an appropriate Hilbert space, including the memory of the boundary as a state component. It is shown that the differential operator of the Cauchy problem is the generator of a contraction semigroup on the state space by establishing the range condition for the Lumer-Phillips Theorem using a generalized Lax-Milgram argument and Fredholm’s alternative. Furthermore, it is shown that neither the generator nor its adjoint have purely imaginary eigenvalues.     

Second-Order Analysis for Control Constrained Optimal Control Problems of Semilinear Elliptic Systems

This paper presents a second-order analysis for a simple model optimal control problem of a partial differential equation, namely, a well-posed semilinear elliptic system with constraints on the control variable only. The cost to be minimized is a standard quadratic functional. Assuming the feasible set to be polyhedric, we state necessary and sufficient second-order optimality conditions, including a characterization of the quadratic growth condition. Assuming that the second-order sufficient condition holds, we give a formula for the second-order expansion of the value of the problem as well as the directional derivative of the optimal control, when the cost function is perturbed. Then we extend the theory of second-order optimality conditions to the case of vector-valued controls when the feasible set is defined by local and smooth convex constraints. When the space dimension n is greater than 3, the results are based on a two norms approach, involving spaces L ² and L ^s , with s>n/2 . Accepted 27 January 1997     

Linear space data structures for two types of range search

This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE ³ and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.This research was conducted while the first author was with Brown University and the second author was with the Technical University of Graz, Austria. The first author was supported in part by NSF Grant MCS 83-03925.     

A Point Balance Algorithm for the Spherical Code Problem

The Spherical Code (SC) problem has many important applications in such fields as physics, molecular biology, signal transmission, chemistry, engineering and mathematics. This paper presents a bilevel optimization formulation of the SC problem. Based on this formulation, the concept of balanced spherical code is introduced and a new approach, the Point Balance Algorithm (PBA), is presented to search for a 1-balanced spherical code. Since an optimal solution of the SC problem (an extremal spherical code) must be a 1-balanced spherical code, PBA can be applied easily to search for an extremal spherical code. In addition, given a certain criterion, PBA can generate efficiently an approximate optimal spherical code on a sphere in the n-dimensional space ⁿ. Some implementation issues of PBA are discussed and putative global optimal solutions of the Fekete problem in 3, 4 and 5-dimensional space are also reported. Finally, an open question about the geometry of Fekete points on the unit sphere in the 3-dimensional space is posed.     

Generating functions and duality for integer programs

We consider the integer program P→max c^′x|Ax=y;xNⁿ . Using the generating function of an associated counting problem, and a generalized residue formula of Brion and Vergne, we explicitly relate P with its continuous linear programming (LP) analogue and provide a characterization of its optimal value. In particular, dual variables λR^m have discrete analogues zC^m, related in a simple manner. Moreover, both optimal values of P and the LP obey the same formula, using z for P and |z| for the LP. One retrieves (and refines) the so-called group-relaxations of Gomory which, in this dual approach, arise naturally from a detailed analysis of a generalized residue formula of Brion and Vergne. Finally, we also provide an explicit formulation of a dual problem P^*, the analogue of the dual LP in linear programming.     

Space complexity of random formulae in resolution

We study the space complexity of refuting unsatisfiable random k-CNFs in the Resolution proof system. We prove that for Δ ≥ 1 and any ϵ > 0, with high probability a random k-CNF over n variables and Δn clauses requires resolution clause space of Ω(n/Δ^1+ϵ). For constant Δ, this gives us linear, optimal, lower bounds on the clause space. One consequence of this lower bound is the first lower bound for size of treelike resolution refutations of random 3-CNFs with clause density Δ ≫ n. This bound is nearly tight. Specifically, we show that with high probability, a random 3-CNF with Δn clauses requires treelike refutation size of exp(Ω(n/Δ^1+ϵ)), for any ϵ > 0. Our space lower bound is the consequence of three main contributions: (1) We introduce a 2-player Matching Game on bipartite graphs G to prove that there are no perfect matchings in G. (2) We reduce lower bounds for the clause space of a formula F in Resolution to lower bounds for the complexity of the game played on the bipartite graph G(F) associated with F. (3) We prove that the complexity of the game is large whenever G is an expander graph. Finally, a simple probabilistic analysis shows that for a random formula F, with high probability G(F) is an expander. We also extend our result to the case of G-PHP, a generalization of the Pigeonhole principle based on bipartite graphs G. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 92–109, 2003     

On optimal polynomial interpolation of analytic functions

This paper discusses the problem of choosing the Lagrange interpolation points T = (t₀, t₁,…, t_n) in the interval −1 t 1 to minimize the norm of the error, considered as an operator from the Hardy space H²(R) of analytic functions to the space C[−1, 1]. It is shown that such optimal choices converge for fixed n, as R → ∞, to the zeros of a Chebyshev polynomial. Asymptotic estimates are given for the norm of the error for these optimal interpolations, as n → ∞ for fixed R. These results are then related to the problem of choosing optimal interpolation points with respect to the Eberlein integral. This integral is based on a probability measure over certain classes of analytic functions, and is used to provide an average interpolation error over these classes. The Chebyshev points are seen to be limits of optimal choices in this case also.     

A continuous method for computing bounds in integer quadratic optimization problems

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x ^T Q x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1} ⁿ . We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in [4]. In this paper, we extend this method by using techniques of differential geometry.     

Optimal regularity for the Signorini problem

We prove under general assumptions that solutions of the thin obstacle or Signorini problem in any space dimension achieve the optimal regularity C ^1,1/2. This improves the known optimal regularity results by allowing the thin obstacle to be defined in an arbitrary C ^1,β hypersurface, β > 1/2, additionally, our proof covers any linear elliptic operator in divergence form with smooth coefficients. The main ingredients of the proof are a version of Almgren’s monotonicity formula and the optimal regularity of global solutions.     

Divergence L 2-Coercivity Inequalities

This paper derives sharp L ²-coercivity inequalities for the divergence operator on bounded Lipschitz regions in ? ⁿ . They hold for fields in H(div,Ω) that are orthogonal to N(div). The optimal constants in the inequality are defined by a variational principle and are identified as the least eigenvalue of a nonstandard boundary value problem for a linear biharmonic type operator. The dependence of the optimal constant under dilations of the region is described and a generalization that involves weighted surface integrals is also proved. When n = 2, this also yields a similar coercivity result for the curl operator.     

The solvability conditions for inverse eigenproblem of symmetric and anti‐persymmetric matrices and its approximation

The problem of generating a matrix A with specified eigen‐pair, where A is a symmetric and anti‐persymmetric matrix, is presented. An existence theorem is given and proved. A general expression of such a matrix is provided. We denote the set of such matrices by ??????_Eⁿ. The optimal approximation problem associated with ??????_Eⁿ is discussed, that is: to find the nearest matrix to a given matrix A* by A∈??????_Eⁿ. The existence and uniqueness of the optimal approximation problem is proved and the expression is provided for this nearest matrix. Copyright © 2002 John Wiley & Sons, Ltd.     

Prescribing scalar curvature on Sn and related problems,part II: Existence and compactness

This is a sequel to [30], which studies the prescribing scalar curvature problem on Sⁿ. First we present some existence and compactness results for n = 4. The existence result extends that of Bahri and Coron [4], Benayed, Chen, Chtioui, and Hammami [6], and Zhang [39]. The compactness results are new and optimal. In addition, we give a counting formula of all solutions. This counting formula, together with the compactness results, completely describes when and where blowups occur. It follows from our results that solutions to the problem may have multiple blowup points. This phenomena is new and very different from the lower-dimensional cases n = 2, 3. Next we study the problem for n ≥ 3. Some existence and compactness results have been given in [30] when the order of flatness at critical points of the prescribed scalar curvature functions K(x) is β ϵ (n − 2, n). The key point there is that for the class of K mentioned above we have completed L^∞ apriori estimates for solutions of the prescribing scalar curvature problem. Here we demonstrate that when the order of flatness at critical points of K(x) is β = n − 2, the L^∞ estimates for solutions fail in general. In fact, two or more blowup points occur. On the other hand, we provide some existence and compactness results when the order of flatness at critical points of K(x) is β ϵ [n − 2,n). With this result, we can easily deduce that C^∞ scalar curvature functions are dense in C^1,α (0 < α < 1) norm among positive functions, although this is generally not true in the C² norm. We also give a simpler proof to a Sobolev-Aubin-type inequality established in [16]. Some of the results in this paper as well as that of [30] have been announced in [29]. © 1996 John Wiley & Sons, Inc.     

On parallel hashing and integer sorting

The problem of sorting n integers from a restricted range [1…m], where m is a superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m) expected time and O(n) space. (Thus, for m = n^polylog(n) we have an O(n log log n) algorithm.) The algorithm is parallelizable. The resulting parallel algorithm achieves optimal speedup. Some features of the algorithm make us believe that it is relevant for practical applications. A result of independent interest is a parallel hashing technique. The expected construction time is logarithmic using an optimal number of processors, and searching for a value takes O(1) time in the worst case. This technique enables drastic reduction of space requirements for the price of using randomness. Applicability of the technique is demonstrated for the parallel sorting algorithm and for some parallel string matching algorithms. The parallel sorting algorithm is designed for a strong and nonstandard model of parallel computation. Efficient simulations of the strong model on a CRCW PRAM are introduced. One of the simulations even achieves optimal speedup. This is probably the first optimal speedup simulation of a certain kind.     

Optimal Error of Analytic Continuation from a Finite Set with Inaccurate Data in Hilbert Spaces of Holomorphic Functions

We consider the problem of analytic continuation with inaccurate data from a finite subset U of a domain D of C ⁿ to a point z ₀D\U for the functions f belonging to a bounded correctness set V in a Hilbert space H(D) of analytic functions in D. In the case when H(D) is a Hilbert space with a reproducing kernel, we find constructive formulas for calculating the optimal error, the optimal function, and the optimal linear algorithm for extrapolation to a point z ₀ for functions in V whose approximate values are given on a set U. Moreover, we study the asymptotics of the optimal error in the case when the errors of initial data vanish.     

Packing up to 50 Equal Circles in a Square

The problem of maximizing the radius of n equal circles that can be packed into a given square is a well-known geometrical problem. An equivalent problem is to find the largest distance d, such that n points can be placed into the square with all mutual distances at least d. Recently, all optimal packings of at most 20 circles in a square were exactly determined. In this paper, computational methods to find good packings of more than 20 circles are discussed. The best packings found with up to 50 circles are displayed. A new packing of 49 circles settles the proof that when n is a square number, the best packing is the square lattice exactly when n≤ 36. Received April 24, 1995, and in revised form June 14, 1995.     

Finding Optimal Shadows of Polytopes

This paper deals with the problem of projecting polytopes in finite-dimensional Euclidean spaces on subspaces of given dimension so as to maximize or minimize the volume of the projection. As to the computational complexity of the underlying decision problems we show that maximizing the volume of the orthogonal projection on hyperplanes is already NP-hard for simplices. For minimization, the problem is easy for simplices but NP-hard for bipyramids over parallelotopes. Similar results are given for projections on lower-dimensional subspaces. Several other related NP-hardness results are also proved including one for inradius computation of zonotopes and another for a location problem. On the positive side, we present various polynomial-time approximation algorithms. In particular, we give a randomized algorithm for maximizing orthogonal projections of CH-polytopes in R ⁿ on hyperplanes with an error bound of essentially . Received February 17, 1999.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

The p-Rank of the Incidence Matrix of Intersecting Linear Subspaces

Let V be a vector space of dimension n+1 over a field of p ^t elements. A d-dimensional subspace and an e-dimensional subspace are considered to be incident if their intersection is not the zero subspace. The rank of these incidence matrices, modulo p, are computed for all n, d, e and t. This result generalizes the well-known formula of Hamada for the incidence matrices between points and subspaces of given dimensions in a finite projective space. A generating function for these ranks as t varies, keeping n, d and e fixed, is also given. In the special case where the dimensions are complementary, i.e., d+e=n+ 1, our formula improves previous upper bounds on the size of partial m-systems (as defined by Shult and Thas).     

The Approximation of the Optimal Control of Vibrations—A Geometrical Approach

In this paper we employ concepts from Banach space geometry in order to examine the problem of approximating the optimal distributed control of vibrating media whose motion is governed by a wave equation with a 2n-order self-adjoint and positive-definite linear differential operator. We show that this geometrical approach, arrived at via duality theory, provides the exact framework in which the approximation problem must be placed in order to get the correct convergence results, for it is here that the necessary and sufficient conditions for the approximate norm or time minimal control can be fully developed. Using the theory of Asplund, we are also able to improve the traditional weak^* convergence results for the more difficult case of L^∞ controls. Finally, we consider certain numerical examples which help illustrate our theoretical results.     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.