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
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
0.7966884970664978
0 references
0.7720600366592407
0 references
0.7591261863708496
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