Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 24 for “"primal-dual method"”.

  1. Lp-Based Approximation Algorithms For Scheduling And Inventory Management Problems

    … approximation algorithms: LP-rounding and the primal-dual method. In this thesis, we develop LP-based approximation algorithms for several scheduling and inventory management problems, using both LP-rounding and the primal-dual method. In machine scheduling, we consider a general class of …

    cornell Repository record for Lp-Based Approximation Algorithms For Scheduling And Inventory Management Problems (opens in a new tab)

  2. On the nonnegative least squares

    … document, we study the nonnegative least squares primal-dual method for solving linear programming problems. In particular, we investigate connections between this primal-dual method and the classical Hungarian method for the assignment problem. Firstly, we devise a fast procedure for computing …

    gatech Repository record for On the nonnegative least squares (opens in a new tab)

  3. A Primal Dual Algorithm On 2-Steiner Graphs

    … which we call 2-Steiner instances, via a primal-dual method.

    waterloo Repository record for A Primal Dual Algorithm On 2-Steiner Graphs (opens in a new tab)

  4. The behavior of Newton's method on two equivalent systems from linear and nonlinear programming

    Newton's method is a fundamental technique for approximating solutions of nonlinear equations. However, it is often not fully appreciated that the method can produce significantly different behavior when applied to equivalent systems. In this thesis, we investigate differences in local and global …

    rice Repository record for The behavior of Newton's method on two equivalent systems from linear and nonlinear programming (opens in a new tab)

  5. Algorithms and Theory for Saddle Point Problems with Relaxed Structural Conditions

    … introduces a generalized accelerated primal--dual method that unifies two existing primal--dual algorithms for convex--concave saddle point problems. We also introduce two new curvature conditions, two-sided quadratic functional growth and two-sided quadratic gradient growth, and show …

    arizona-thes Repository record for Algorithms and Theory for Saddle Point Problems with Relaxed Structural Conditions (opens in a new tab)

  6. On primal-dual schema for the minimum satisfiability problem

    … used the concept of linear programming and the primal-dual method to study the problem. We have constructed the Linear program of the MINSAT and its restricted version. We have proposed two combinatorial methods to solve the dual of the restricted primal of the MINSAT. Further to this, these two …

    lethbridge Repository record for On primal-dual schema for the minimum satisfiability problem (opens in a new tab)

  7. STOCHASTIC BREGMAN GRADIENT-TYPE ALGORITHMS FOR NONCONVEX OPTIMIZATION AND CONVEX-CONCAVE SADDLE POINT PROBLEMS

    We explore stochastic Bregman gradient methods for solving nonconvex stochastic optimization and convex-concave saddle point problems, crucial in statistics, image processing, and deep learning. Structured into three parts, we first consider nonconvex composite objective functions without globally …

    nus Repository record for STOCHASTIC BREGMAN GRADIENT-TYPE ALGORITHMS FOR NONCONVEX OPTIMIZATION AND CONVEX-CONCAVE SADDLE POINT PROBLEMS (opens in a new tab) Download file for STOCHASTIC BREGMAN GRADIENT-TYPE ALGORITHMS FOR NONCONVEX OPTIMIZATION AND CONVEX-CONCAVE SADDLE POINT PROBLEMS (opens in a new tab)

  8. Online Algorithms and Optimal Offline Algorithms for Dynamic Optimal Power Flow

    … online algorithm is then tailored based on the primal-dual method. Trace driven simulation studies verify the efficacy of the proposed offline and online algorithms.

    calgary Repository record for Online Algorithms and Optimal Offline Algorithms for Dynamic Optimal Power Flow (opens in a new tab)

  9. Prize-Collecting Network Design

    … connectivity requirement functions using the primal-dual method and extend our algorithm to solve its prize-collecting version. Computational experiments are carried out to compare this online algorithm with the corresponding offline optimal solutions on a set of random generated largescale …

    cornell Repository record for Prize-Collecting Network Design (opens in a new tab)

  10. Robust Airline Fleet Assignment

    … of Station Decomposition by developing a primal-dual method that increases the solution quality and model efficiency. Station Decomposition solutions can be highly fractional; we develop a fix and price heuristic to efficiently find integer solutions to the fleet assignment problem. …

    gatech Repository record for Robust Airline Fleet Assignment (opens in a new tab)

  11. 2-D and 3-D tools for electrical imaging in environmental applications

    … sites via the application of non-invasive methods, such as electrical resistivity and electromagnetic techniques. With the aim of improving the relationships between geophysical parameters and hydro-geological features of the subsoil, some innovative methods are proposed. In particular, …

    poli-torino Repository record for 2-D and 3-D tools for electrical imaging in environmental applications (opens in a new tab)

  12. Optimization problems in network mechanism design

    … approximation algorithms which are based on the primal dual method for network connectivity problems. We then prove that these algorithms are monotone and thus can lead to truthful mechanisms. Finally in Chapter 5 we study the problem of facility location on the real line under non utilitarian …

    greece Repository record for Optimization problems in network mechanism design (opens in a new tab)

  13. Integrated methods and systems for optimization and decision support

    … result. Motivated by the so-called integrated methods for optimization, we study three different optimization problems, and present new algorithms that combine the complementary strengths of the three major types of optimization methods, i.e., Mathematical Programming, Constraint Programming …

    greece Repository record for Integrated methods and systems for optimization and decision support (opens in a new tab)

  14. Signomial programs with equality constraints : numerical solution and applications

    … constraints. However, existing computational methods of signomial programming are applicable to programs with inequality constraints only. In this thesis an algorithm is proposed and implemented to solve signomial programs with mixed inequality and equality constraints. The algorithm requires …

    ubc Repository record for Signomial programs with equality constraints : numerical solution and applications (opens in a new tab) Download PDF for Signomial programs with equality constraints : numerical solution and applications (opens in a new tab)

  15. Fixed Point Iterations for Finite Sum Monotone Inclusions

    This thesis studies two families of methods for finding zeros of finite sums of monotone operators, the first being variance-reduced stochastic gradient (VRSG) methods. This is a large family of algorithms that use random sampling to improve the convergence rate compared to more traditional …

    lund Repository record for Fixed Point Iterations for Finite Sum Monotone Inclusions (opens in a new tab) Download PDF for Fixed Point Iterations for Finite Sum Monotone Inclusions (opens in a new tab)

  16. Linear Programming Algorithms Using Least-Squares Method

    … which aim to overcome degeneracy in the simplex method. We study the following algorithms: the non-negative least squares algorithm, the least-squares primal-dual algorithm, the least-squares network flow algorithm, and the combined-objective least-squares algorithm. All of the four algorithms …

    gatech Repository record for Linear Programming Algorithms Using Least-Squares Method (opens in a new tab)

  17. Cover Small Cuts and Flexible Graph Connectivity Problems

    … problems on strongly pliable families using the primal-dual method of Williamson, Goemans, Vazirani, and Mihail. We compare strongly pliable families to other subfamilies of pliable families, such as uncrossable families. We also study some other cut covering problems. In Flexible Graph …

    waterloo Repository record for Cover Small Cuts and Flexible Graph Connectivity Problems (opens in a new tab)

  18. Robust Exact Algorithms for the Euclidean Bipartite Matching Problem

    … graph. The Hungarian algorithm is a classical method that solves this problem in O(n^3) time. There are many algorithms that have a run time better than that of the Hungarian algorithm if the graphs have non-negative integer edge costs bounded by C. Since the input points have real-valued …

    vt Repository record for Robust Exact Algorithms for the Euclidean Bipartite Matching Problem (opens in a new tab)

Page 1 of 2