No label defined (Q3758559)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4008098
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4008098

      Statements

      0 references
      0 references
      1987
      0 references
      threshold graphs
      0 references
      preorders
      0 references
      0-1 programming
      0 references
      minimum cut
      0 references
      rooted tree
      0 references
      linearization of pseudo-Boolean functions
      0 references
      order constraints
      0 references
      set packing
      0 references
      set-covering
      0 references
      Polynomial algorithms
      0 references
      [For the entire collection see Zbl 0599.00013.] Old and some new results concerning two important preorders in the set of variables of a 0-1 programming problem are presented. The first is the ordinary relation \(x_ i\leq x_ j\) which means \(''x_ j\) is 1 when \(x_ i\) is 1''. In connection with this order relation the following topics are discussed: Generation of order constraints which are useful in connection with solution methods; a new reduction of 0-1 linear programs with order constraint to the minimum cut problem and an O(n)- algorithm for the case that the underlying network is a rooted tree; linearization of pseudo-Boolean functions via order constraints. The second order is the preorder \(x_ i\preccurlyeq x_ j\) defined by the property ''every feasible vector x such that \(x_ i=0\) and \(x_ j=1\), remains feasible when \(x_ i\) is replaced by 1, and \(x_ j\) is replaced by 0''. A feasible set is regular if this preorder happens to be linear. A set packing problem or set-covering problem is regular if its feasible set is regular. Polynomial algorithms are given for recognizing and solving regular set packing and set covering problems. Furthermore there is an equivalence between regular set covering problems and 0-1 programs with linear objective function.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references