Global Methods for Combinatorial Isoperimetric Problems
With a focus on global methods, this innovative text employs morphisms to transform new problems into more restricted and easily solvable settings while preserving essential structure.
TABLE OF CONTENTS Global Methods for Combinatorial Isoperimetric Problems
6.2: The MWI Problem
6.2 The MWI Problem
6.2.1 Definitions
Given a poset 
= ( P, ?) (see Section 3.2.7 of Chapter 3) and S ? , then let
If S = 
, then S is an ideal and conversely. Note that 
, so for any S ? , is an ideal, the ideal generated by S. The set of all ideals of ) , (also known as the vertex set of the derived network of , partially ordered by containment, will be denoted 
( ) . Then the maximum weight ideal (MWI) problem on with weight ? : P ? 
, is to compute
? k ? 
+ , where ? has been extended to a set function by additivity.
Dually, let
If S = 
, then S is called a filter. Again, 
, so for any S ? P, is a filter, the filter generated by S. Also, the complement of a filter is an ideal and vice versa.
Lemma 6.4
The minimum weight ideal problem is reducible to the maximum weight ideal problem and vice versa so the two are equivalent.
Proof The complement, P ? S, of an ideal, S ? ( ), is a filter in which is an ideal in *, the dual of . The conclusion follows from the fact that ? ( P ? S) = ? ( P
Copyright Cambridge University Press 2004 under license agreement with Books24x7
