Now showing items 1-20 of 23

    • An Accelerated Interior Point Method Whose Running Time Depends Only on $A$ 

      Vavasis, Stephen A.; Ye, Yinyu (Cornell University, 1993-10)
      We propose a "layered-step" 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, 1993-10)
      We propose a "layered-step" 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, 1997-02-06)
      We consider the weighted least-squares (WLS) problem with a very ill-conditioned weight matrix. Weighted least-squares problems arise in many applications including linear programming, electrical networks, boundary value ...
    • Approximation Algorithms for Concave Quadratic Programming 

      Vavasis, Stephen A. (Cornell University, 1990-12)
      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 d-grid Cut by a Hyperplane 

      Mitchell, Scott A.; Vavasis, Stephen A. (Cornell University, 1995-11)
      We consider the problem of triangulating a d-dimensional uniform grid of d-cubes that is cut by a k-dimensional affine subspace. The goal is to obtain a triangulation with bounded aspect ratio. To achieve this goal, we ...
    • Black-box complexity of local minimization 

      Vavasis, Stephen A. (Cornell University, 1990-06)
      We study the complexity of local minimization in the black-box 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, 1994-12)
      Consider a full-rank weighted least squares problem in which the weight matrix is highly ill-conditioned. Because of the ill-conditioning, standard methods for solving least-squares problems, QR factorization and the ...
    • Complexity Issues in Global Optimization: A Survey 

      Vavasis, Stephen A. (Cornell University, 1993-01)
      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, 1993-11)
      We develop a condition-based complexity analysis for homogenous polyhedra with real number data. We analyze the dependency of primal-dual interior point algorithm efficiency on this condition number for finding a point ...
    • Density Graphs and Separators 

      Miller, Gary L.; Vavasis, Stephen A. (Cornell University, 1990-11)
      We propose a class of graphs that would occur naturally in finite-element problems, and we prove a bound on separators for this class of graphs. For three-dimensional 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, 1994-03)
      (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, 1990-12)
      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 Two-Dimensional Surfaces 

      Vavasis, Stephen A. (Cornell University, 1990-09)
      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 Cross-ratios and Delaunay Triangulation 

      Driscoll, Tobin; Vavasis, Stephen A. (Cornell University, 1996-02)
      We propose a new algorithm for computing the Riemann mapping of the unit disk to a polygon, also known as the Schwarz-Christoffel transformation. The new algorithm, CRDT, is based on cross-ratios of the prevertices, and ...
    • Preconditioning for Boundary Integral Equations (Preliminary Version) 

      Vavasis, Stephen A. (Cornell University, 1990-02)
      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 Polynomial-Time for Sphere-Constrained Quadratic Programming 

      Vavasis, Stephen A.; Zippel, Richard (Cornell University, 1990-12)
      Recently Ye and Karmarkar have proposed similar algorithms for minimizing a nonconvex quadratic function on a sphere. These algorithms are based on trust-region work going back to Levenberg and Marquardt. Although both ...
    • Quadratic Programming is in NP 

      Vavasis, Stephen A. (Cornell University, 1990-02)
      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, 1996-12)
      We consider the problem of triangulating a d-dimensional region. Our mesh generation algorithm, called QMG, is a qradtree-based 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, 1992-02)
      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, 1992-09)
      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. ...