Combinatorial Optimization: Networks And Matroids

Combinatorial Optimization: Networks and Matroids EUGENE L. LAWLER University of California at Berkeley HOLT, RINEHART AND New York Chicago Dallas Montreal WINSTON San Francwo Toronto London Atlanta Sydney To my parents, and to my children, Stephen and Susan Copyright 0 1976 by Holt, Rinehart and Wins.on All rights reserved Library of Congress Cataloging in Publication Data Lawler, Eugene L Combinatorial optimization. Includes bibliographical references. 1. Mathematical optimization. 2. Matroids. 3. Network analysis (Planning). 4. Computalional complexity. 5. Algorithms. I. Title. 76-13516 QA402.5.L39 519.7 ISBN 0 -03-084866-o Printed in the United States of America 8 9 038 9 8 7 6 5 4 3 2 Preface Combinatorial optimization problems arise everywhere, and certainly in all areas of technology and industrial management. A growing awareness of the importance of these problems has been accompanied by a combinatorial explosion In proposals for their solution. This, book is concerned with combinatorial optimization problems which can be formulated in terms of networks and algebraic structures known as matroids. My objective has been to present a unified and fairly comprehensive survey 01‘ solution techniques for these problems, with emphasis on “augmentation” algorithms. Chapters 3 through 5 comprise the material in one-term courses on network flow theory currently offered in many university departments of operations research and industrial engineering. In most cases, a course in linear programming is designated as a prerequisite. However, this is not essential. Chapter 2 contains necessary background material on linear programming, and graph theory as well. Chapters 6 through 9 are suitable for a second course, presumably at the graduate level. The instructor may wish to omit certain sections, depending upon the orientation