  We present two first-order primal-dual algorithms for solving saddle point
formulations of linear programs, namely FWLP (Frank-Wolfe Linear Programming)
and FWLP-P. The former iteratively applies the Frank-Wolfe algorithm to both
the primal and dual of the saddle point formulation of a standard-form LP. The
latter is a modification of FWLP in which regularizing perturbations are used
in computing the iterates. We show that FWLP-P converges to a primal-dual
solution with error $O(1/\sqrt{k})$ after $k$ iterations, while no convergence
guarantees are provided for FWLP. We also discuss the advantages of using FWLP
and FWLP-P for solving very large LPs. In particular, we argue that only part
of the matrix $A$ is needed at each iteration, in contrast to other first-order
methods.
