000			nam a22 4500
999			_c32035 _d32035
008			230903b xxu||||| |||| 00| 0 eng d
020			_a9780521189439
082			_a518.26 _bLAU
100			_aLau, Lap Chi
245			_aIterative methods in combinatorial optimization
260			_bCambridge University Press, _c2011 _aCambridge :
300			_axi, 242 p. ; _bill., _c23 cm
365			_b42.99 _cGBP _d110.40
490			_aCambridge texts in applied mathematics
504			_aIncludes bibliographical references and index.
520			_aWith the advent of approximation algorithms for NP-hard combinatorial optimization problems, several techniques from exact optimization such as the primal-dual method have proven their staying power and versatility. This book describes a simple and powerful method that is iterative in essence and similarly useful in a variety of settings for exact and approximate optimization. The authors highlight the commonality and uses of this method to prove a variety of classical polyhedral results on matchings, trees, matroids, and flows. The presentation style is elementary enough to be accessible to anyone with exposure to basic linear algebra and graph theory, making the book suitable for introductory courses in combinatorial optimization at the upper undergraduate and beginning graduate levels. Discussions of advanced applications illustrate their potential for future application in research in approximation algorithms.
650			_aData processing
650			_aCombinatorial optimization
650			_aBipartite Graphs
650			_a Generalized Assignment Problem
650			_aSpanning Trees
650			_aMatroid Intersection
650			_aDuality and Min-Max Theorem
650			_aIntegrality
650			_aGraph Matching
650			_aVertex Cove
650			_aDiscrepancy Theorem
650			_aBin Packing
700			_aRavi, R.
700			_aSingh, Mohit
942			_2ddc _cBK