The primal-dual method for approximation algorithms and its application to network design problems 论文

摘要

Dedicated to the memory of Albert W. Tucker The primal-dual method is a standard tool in the design of algorithms for combinatorial optimization problems. This chapter shows how the primal-dual method can be modified to provide good approximation algorithms for a wide variety of NP-hard problems. We concentrate on results from recent research applying the primal-dual method to problems in network design.