Primal-Dual Method
Lists
Only you see this
Abstract
The linear programming primal-dual method has been extensively used to obtain sequential exact algorithms (see for example [Chv79], [PS82]). This algorithm keeps both a primal solution and a dual solution. When the solutions together satisfy the complementary slackness conditions, then they are mutually optimal. Otherwise either the primal solution is augmented or the dual solution is improved. The primal-dual method was originally due to Dantzing, Ford and Fulkerson [DFF56]. Unless P=NP, the primaldual method cannot be used to solve exactly in polynomial time NP-hard problems.
BibTeX
@inproceedings{daz1997primal,
author = {Josep Dı́az and Marı́a Serna and Paul G. Spirakis and Jacobo Torán},
title = {{Primal-Dual Method}},
booktitle = {Cambridge},
year = {1997},
doi = {10.1017/cbo9780511666407.006},
}Loading related content...