Blocking and Antiblocking Polyhedra

From MaRDI portal





This paper describes the fundamental aspects of the theory of blocking and antiblocking polyhedra as developed by D. R. Fulkerson. This theory has appeared to be an excellent framework for the discussion of problems of discrete nature as well as problems of continuous origin. It relates the duality theories known from convex analysis and linear programming to equivalent theories for combinatorial problems in a very elegant way. The present paper states the basic results by Fulkerson and mentions later works, based on these results. Although the theory has been motivated by the study of certain problems in combinatorics, the theory itself is modelled over continuous problems. The actual presentation is primarily focused on problems of this last sort, but several references have been given to results in combinatorics. There has been made no attempt to actually unify the blocking theory and the antiblocking theory. They contain many mutual similarities and developments, but there are also dissimilarities, important enough to justify the separate presentation, which has been followed here. The first two sections present the basic material without any proofs, but contain some basic illustrating examples. In Section 3 the relation to similar concepts in convex analysis is discussed, and Section 4 is devoted to the relation towards integer programming and combinatorics. Section 5 mentions very briefly some of the connections between the two theories. For the entire collection see [Zbl 0403.00021].











This page was built for publication: Blocking and Antiblocking Polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4198784)