In this 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 the unrestricted least
squares solution of a bipartite matching problem by exploiting the special
structure of the incidence matrix of a bipartite graph. Moreover, we explain
how to extract a solution for the cardinality matching problem from the
nonnegative least squares solution. We also give an efficient procedure
for solving the cardinality matching problem on general graphs using the
nonnegative least squares approach.
Next we look into some theoretical results concerning the minimization of p-norms,
and separable differentiable convex functions, subject to linear constraints
described by node-arc incidence matrices for graphs.
Our main result is the reduction of the assignment problem to a single
nonnegative least squares problem. This means that the primal-dual
approach can be made to converge in one step for the assignment problem.
This method does not reduce the primal-dual approach to one step for
general linear programming problems, but it appears to give a good
starting dual feasible point for the general problem.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/31768 |
| Date | 19 August 2009 |
| Creators | Santiago, Claudio Prata |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0019 seconds