A Decade of Combinatorial Optimization
KI Karen Aardal, van Cpm Stan Hoesel, JK Jan Karel Lenstra, Leen Stougie, Klein Haneveld, W.K., Vrieze, O.J., Kallenberg, L.C.M. · TU/e Research Portal · 1997
This paper o ers a brief overview of the developments in combinatorial optimization during the past decade. We discuss improvements in polynomialtime algorithms for problems on graphs and networks, and review the methodological and computational progress in linear and integer optimization. Some of the more prominent software packages in these areas are mentioned. With respect to obtaining approximate solutions to NP-hard problems, we survey recent positive and negative results on polynomial-time approximability and summarize the advances in local search.