文档介绍：This page intentionally left blankIterative Methods binatorial OptimizationWith the advent of approximation algorithms for NP-binatorial optimizationproblems, several techniques from exact optimization such as the primal-dual methodhave proven their staying power and versatility. This book describes a simple and pow-erful method that is iterative in essence and similarly useful in a variety of settings forexact and approximate optimization. The authors highlight monality and usesof this method to prove a variety of classical polyhedral results onmatchings, trees,matroids, and ? presentation style is elementary enough to be accessible to anyone with expo-sure to basic linear algebra and graph theory, making the book suitable for introductorycourses binatorial optimization at the upper undergraduate and beginning grad-uate levels. Discussions of advanced applications illustrate their potential for futureapplicationinresearch chi lauis an Assistant Professor in the Department puter Science andEngineering at The Chinese University of Hong Kong. Lap Chi’s main research inter-ests are binatorial optimizationand graph algorithms. His paper onSteiner treepacking was given the Machtey award in the IEEE Foundations puter ScienceConference. His . thesis was awarded the doctoral prize from the Canadian Mathe-matical Society anda doctoral prize fromthe Natural Sciences andEngineering ResearchCouncil of . raviis Carnegie Bosch Professor of Operations Research puter Science atCarnegie Mellon University. Ravi’s main research interests are binatorial opti-mization(particularly inapproximationalgorithms), computational molecular biology,and singhis an Assistant Professor in the School puter Science, McGill Uni-versity. pleted his . in 2008 at the Tepper School of Business, CarnegieMellonUniversity, where his advisor was Professor R. Ravi. His thesis was awardedthe Tucker prize by the Mathematical Programming Society. Hi