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"”.
-
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 …
-
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 …
-
A Primal Dual Algorithm On 2-Steiner Graphs
… which we call 2-Steiner instances, via a primal-dual method.
-
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 …
-
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 …
-
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 …
-
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 …
-
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.
-
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 …
-
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. …
-
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, …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
Page 1 of 2