Search
Now showing items 11-20 of 126
An Almost Linear-Time Algorithm for Graph Realization
(1985-03)
Given a {0,1}-matrix M, the graph realization problem for M is to find a tree such that the columns of M are incidence vectors of paths in T, or to show that no such T exists. An algorithm is presented for this problem ...
An Algorithmic Characterization of Antimatroids
(1987-12)
In an article entitled "Optimal sequencing of a single machine subject to precedence constraints," E.L. Lawler presented a now classical minmax result for job scheduling. In essence, Lawler's proof demonstrated that the properties of partially ordered sets were sufficient to solve the posed scheduling problem. These properties are, in fact, common to a more general class of combinatorial structures known as antimatroids, which have recently received considerable attention in the literature. It is demonstrated that the properties of antimatroids are not only sufficient but necessary to solve the scheduling problem posed by Lawler, thus yielding an algorithmic characterization of antimatroids. Examples of problems solvable by the general result are provided....
Domain Decomposition for Two-Dimensional Elliptic Operators on Vector and Parallel Machines
(1986-04)
The efficient computation of the solution to self-adjoint elliptic operators is the subject of this dissertation. Discretization of this equation by finite differences or finite elements yields a large, sparse, symmetric ...
Mobility Weighting in Numerical Reservoir Simulation
(1983)
The sensitivity of a numerical steamflooding model with respect to mobility weighting is examined in depth. Three numerical discretization procedures are used in this investigation: a new numerical scheme, a five point ...
Weighted Least Squares Estimators on the Frequency Domain for the Parameters of a Time Series
(1986-09)
A procedure for estimating the parameters of a time series is proposed. The estimate minimizes a criterion function which is the weighted sum of squares of the distances between the periodograms and the spectrum of the ...
The Lagrangian as a Primal Cutting Plane Method for Linear Integer Programming Problems
(1988-12)
Lagrangian relaxation and more recently cutting plane techniques have both proven to be powerful methods in the solution of integer problems. This paper explores the relationship between these techniques by interpreting ...
Electromagnetic Propagation and Scattering in Spherically-Symmetric Terrestrial System-Models
(1986-04)
A study of the quantitative solutional approaches to boundary-value problems associated with terrestrial electromagnetic propagation is carried out, with particular attention given to spherical-system models and the frequency ...
Program Specification Testing within an Integrated Programming Environment
(1983-11)
Our research breaks down into three parts. First, we are exploring the mathematical foundations of program specifications and applying the understanding that we gain to the subject of specification language design. The success of a specification and testing system hinges on the quality of the underlying specification language. We are particularly concerned with the special problems posed by floating point arithmetic and concurrency. Second, we are developing more sophisticated methods - employing a judicious combination of verification and testing - for certifying that programs implement their formal specifications. Finally, to test the effectiveness of ideas, we are building an experimental program specification and testing system as an extension of the R^n Programming Environment already under development at Rice....
Computing a Celis-Dennis Tapia Trust Region Step for Equality Constrained Optimization
(1988-12)
We study an approach for minimizing a convex quadratic function subject to two quadratic constraints. This problem stems from computing a trust region step for an SQP algorithm proposed by Celis, Dennis and Tapia (1984) ...