Integer programming and combinatorial optimization

En savoir plus sur le livre

The book covers a range of topics in combinatorial optimization and graph theory. It begins with matrices and matroids, exploring the packing property and characterizing weakly bipartite graphs. The discussion includes bipartite designs and noninteger polyhedra with 0–1 constraints, along with a theorem of Truemper. It delves into the generalized stable set problem for claw-free bidirected graphs and presents a min-max theorem of cacti, addressing edge connectivity and edge-splitting in planar graphs. The text offers a new bound for the 2-edge connected subgraph problem and an improved approximation algorithm for minimum size 2-edge connected spanning subgraphs. It also examines multicuts in unweighted graphs with bounded degree and tree-width, and discusses greedy algorithms for disjoint-path problems. The book presents approximation algorithms for the mixed postman problem and for uncapacitated facility location. Integer programming applications are explored, including polyhedral combinatorics related to benzenoid problems and solving linear Diophantine equations. The text addresses knapsack polyhedra intersections and introduces new lower bounds for bin packing problems. It also covers network flows, detailing algorithms for minimum cuts and maximum flow problems, as well as multicommodity flow. Scheduling issues are tackled with non-approximability results and efficient approximation algorithms for various scheduling pr