# Combinatorial Optimization

Language: English

Pages: 368

ISBN: 047155894X

Format: PDF / Kindle (mobi) / ePub

A complete, highly accessible introduction to one of today's most exciting areas of applied mathematics

One of the youngest, most vital areas of applied mathematics, combinatorial optimization integrates techniques from combinatorics, linear programming, and the theory of algorithms. Because of its success in solving difficult problems in areas from telecommunications to VLSI, from product distribution to airline crew scheduling, the field has seen a ground swell of activity over the past decade.

Combinatorial Optimization is an ideal introduction to this mathematical discipline for advanced undergraduates and graduate students of discrete mathematics, computer science, and operations research. Written by a team of recognized experts, the text offers a thorough, highly accessible treatment of both classical concepts and recent results. The topics include:

* Network flow problems

* Optimal matching

* Integrality of polyhedra

* Matroids

* NP-completeness

Featuring logical and consistent exposition, clear explanations of basic and advanced concepts, many real-world examples, and helpful, skill-building exercises, Combinatorial Optimization is certain to become the standard text in the field for many years to come.

Linear Algebra and Its Applications (4th Edition)

The Arrow Impossibility Theorem

Introduction to the Theory of Sets (Dover Books on Mathematics)

means that there is no (explicit) upper bound on xe. One remark: We use "u is integral" to mean that the finite components of u are integers. 40 MAXIMUM FLOW PROBLEMS We remark that the decomposition of integral flows into paths described above can be extended to nonintegral flows. We define a path flow to be a vector x € R e such that, for some (r, s)-dipath P and some nonnegative real number a, xe = a for each arc e of P, and xe = 0 for every other arc of G. A circuit flow is defined in the

formerly in T2 U T4 will now satisfy c e = 0. That is, after the change R will no longer block the search for an augmenting path of equality arcs. Thus we should choose σ = πιιη(σι, σ2), where σ\ — min(c e : e € S(R), ce > 0) and σ2 = m i n ( - c e : e € S(R), ce < 0). (In the example, σ = min(c,d, —ctq) = min(8,1) = 1, and tq becomes an equality arc.) One small difficulty must be handled here: What if σ = oo, that is, T2 = T4 = 0? Actually, this is impossible, because (4.1) would have no

that M C M'UE(C) and the number of M-exposed nodes of G is the same as the number of M'exposed nodes of G'. 132 m OPTIMAL MATCHINGS Figure 5.6. Extending a matching Proof: Choose a node w € V(C) as follows. If C is covered by e € M', then choose w to be the node in V(C) that is an end of e, and otherwise, choose w arbitrarily. Now deleting w from C results in a subgraph having a perfect matching M". Take M = M' U M". It is easy to check that M has the required properties. | Proposition 5.4

with P. Use this idea to prove Theorem 5.23 and to give an algorithm that constructs an Euler tour of G. 5.41. Prove that if every node of G has even degree, then its edge-set is the union of edge-disjoint circuits. 5.42. Let J be a T-join, and define the weight we of edge e to be ce if e € J and to be — ce if e £ J. Show that J is of minimum cost with respect to c if and only if G has no circuit of positive weight with respect to w. 5.43. Consider the maximum cut problem for (G, c) where at most

in the past decade. We set out to describe the material in an elementary text, suitable for a one semester course. The urge to include advanced topics proved to be irresistible, however, and the manuscript, in time, grew beyond the bounds of what one could reasonably expect to cover in a single course. We hope that this is a plus for the book, allowing the instructor to pick and choose among the topics that are treated. In this way, the book may be suitable for both graduate and undergraduate