作者：Chudak, FA; Roughgarden, T; Williamson, DP
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Berkeley; International Business Machines (IBM); IBM USA
摘要：Garg [10] gives two approximation algorithms for the minimum-cost tree spanning k vertices in an undirected graph. Recently Jain and Vazirani [15] discovered primal-dual approximation algorithms for the metric uncapacitated facility location and k-median problems. In this paper we show how Garg's algorithms can be explained simply with ideas introduced by Jain and Vazirani, in particular via a Lagrangean relaxation technique together with the primal-dual method for approximation algorithms. We...
作者：Ulbrich, M; Ulbrich, S; Vicente, LN
作者单位：University of Hamburg; University of Munich; Universidade de Coimbra; Rice University; Rice University
摘要：In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters. The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes are controlled by a trust-region type parameter. Each entry in the filter is a pair of coordinates: one re...
