×

Some relations between combinatorial min-max equalities and Lagrangian duality, via coupling functions. II: Further results. (English) Zbl 0687.90070

Summary: We apply the Lagrangian duality approach of the first part [ibid., No.5, 455-491 (1989; Zbl 0676.90057)] to some combinatorial min-max equalities which are not of the “all-cardinality covering-packing” type studied in part I, namely, to min-max equalities for “B-colourings”, “A-cover packings”, “weighted B-packings” and “weighted A-covers” in incidence triples (A, B, \(\rho)\), non-bipartite matchings, flows in networks and matroid intersections. Introducing some new coupling functions, we give some results on the “hyper-Lagrangian” types of these min-max equalities and some characterizations of a primal-dual pair of optimal solutions.

MSC:

90C27 Combinatorial optimization
90B10 Deterministic network models in operations research
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0676.90057
PDFBibTeX XMLCite