JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Vavasis, Stephen A."
Now showing items 120 of 23

An Accelerated Interior Point Method Whose Running Time Depends Only on $A$
Vavasis, Stephen A.; Ye, Yinyu (Cornell University, 199310)We propose a "layeredstep" interior point (LIP) algorithm for linear programming. This algorithm follows the central path, either with short steps or with a new type of step called a "layered least squares" (LLS) step. ... 
An Accelerated Interior Point Method Whose Running Time Depends Only on A
Vavasis, Stephen A.; Ye, Yinyu (Cornell University, 199310)We propose a "layeredstep" interior point (LIP) algorithm for linear programming. This algorithm follows the central path, either with shortsteps or with a new type of step called a "layered least squares" (LLS)step. The ... 
Accurate Solution of Weighted Least Squares by Iterative Methods
Bobrovnikova, Elena Y.; Vavasis, Stephen A. (Cornell University, 19970206)We consider the weighted leastsquares (WLS) problem with a very illconditioned weight matrix. Weighted leastsquares problems arise in many applications including linear programming, electrical networks, boundary value ... 
Approximation Algorithms for Concave Quadratic Programming
Vavasis, Stephen A. (Cornell University, 199012)We consider $\epsilon$approximation schemes for concave quadratic programming. Because the existing definition of $\epsilon$approximation for combinatorial optimization problems is inappropriate for nonlinear optimization, ... 
An Aspect Ratio Bound for Triangulating a dgrid Cut by a Hyperplane
Mitchell, Scott A.; Vavasis, Stephen A. (Cornell University, 199511)We consider the problem of triangulating a ddimensional uniform grid of dcubes that is cut by a kdimensional affine subspace. The goal is to obtain a triangulation with bounded aspect ratio. To achieve this goal, we ... 
Blackbox complexity of local minimization
Vavasis, Stephen A. (Cornell University, 199006)We study the complexity of local minimization in the blackbox model, that is, the model in which the objective function and possibly its gradient are available as external subroutines. This is the model used, for example, ... 
Complete Orthogonal Decomposition for Weighted Least Squares
Hough, Patricia D.; Vavasis, Stephen A. (Cornell University, 199412)Consider a fullrank weighted least squares problem in which the weight matrix is highly illconditioned. Because of the illconditioning, standard methods for solving leastsquares problems, QR factorization and the ... 
Complexity Issues in Global Optimization: A Survey
Vavasis, Stephen A. (Cornell University, 199301)Complexity theory refers to the asymptotic analysis of problems and algorithms. How efficient is an algorithm for a particular optimization problem, as the number of variables gets large? Are there problems for which ... 
Condition Numbers for Polyhedra with Real Number Data
Vavasis, Stephen A.; Ye, Yinyu (Cornell University, 199311)We develop a conditionbased complexity analysis for homogenous polyhedra with real number data. We analyze the dependency of primaldual interior point algorithm efficiency on this condition number for finding a point ... 
Density Graphs and Separators
Miller, Gary L.; Vavasis, Stephen A. (Cornell University, 199011)We propose a class of graphs that would occur naturally in finiteelement problems, and we prove a bound on separators for this class of graphs. For threedimensional graphs, our separator bound is $O(N^{2/3})$. We also ... 
Fast Wavelet Transforms for Matrices Arising from Boundary Element Methods
Bond, David M.; Vavasis, Stephen A. (Cornell University, 199403)(The following contains mathematical formulae and symbols that may become distorted in ASCII text.) For many boundary element methods applied to Laplace's equation in two dimensions, the resulting integral equation has ... 
Nested Dissection for Sparse Nullspace Bases
Stern, Julio M.; Vavasis, Stephen A. (Cornell University, 199012)We propose a nested dissection approach to finding a fundamental cycle basis in a planar graph. the cycle basis corresponds to a fundamental nullspace basis of the adjacency matrix. This problem is meant to model sparse ... 
A Note on Wavelet Bases for TwoDimensional Surfaces
Vavasis, Stephen A. (Cornell University, 199009)Recent work by Beylkin, Coifman and Rokhlin has demonstrated that integral equations for functions on $IR$ can be solved rapidly by expressing the integrands in a wavelet basis. Boundary element methods for solving partial ... 
Numerical Conformal Mapping Using Crossratios and Delaunay Triangulation
Driscoll, Tobin; Vavasis, Stephen A. (Cornell University, 199602)We propose a new algorithm for computing the Riemann mapping of the unit disk to a polygon, also known as the SchwarzChristoffel transformation. The new algorithm, CRDT, is based on crossratios of the prevertices, and ... 
Preconditioning for Boundary Integral Equations (Preliminary Version)
Vavasis, Stephen A. (Cornell University, 199002)We propose new classes of preconditioners for the linear systems arising from a boundary integral equation method. The problem under consideration is Laplace's equation in three dimensions. The system arising in this context ... 
Proving PolynomialTime for SphereConstrained Quadratic Programming
Vavasis, Stephen A.; Zippel, Richard (Cornell University, 199012)Recently Ye and Karmarkar have proposed similar algorithms for minimizing a nonconvex quadratic function on a sphere. These algorithms are based on trustregion work going back to Levenberg and Marquardt. Although both ... 
Quadratic Programming is in NP
Vavasis, Stephen A. (Cornell University, 199002)Quadratic programming is an important example of optimization with applications to engineering design, coombinatorical optimization, game theory, and economics. Garey and Johnson [1979] state that quadratic programming ... 
Quality Mesh Generation in Higher Dimensions
Mitchell, Scott A.; Vavasis, Stephen A. (Cornell University, 199612)We consider the problem of triangulating a ddimensional region. Our mesh generation algorithm, called QMG, is a qradtreebased algorithm that can triangulate any polyhedral region including nonconvexregions with holes. ... 
Quality Mesh Generation in Three Dimensions
Mitchell, Scott A.; Vavasis, Stephen A. (Cornell University, 199202)We show how to triangulate a three dimensional polyhedral region with holes. Our triangulation is optimal in the following two senses: First, our triangulation achieves the best possible aspect ratio up to a constant. ... 
Quality Mesh Generation in Three Dimensions
Mitchell, Scott A.; Vavasis, Stephen A. (Cornell University, 199209)We show how to triangulate a three dimensional polyhedral region with holes. Our triangulation is optimal in the following two senses. First, our triangulation achieves the best possible aspect ratio up to a constant. ...