No label defined (Q3337221)
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 3869064
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3869064 |
Statements
1984
0 references
greedy solutions
0 references
set covering
0 references
heuristics
0 references
worst-case bound
0 references
0.8203958868980408
0 references
0.8072290420532227
0 references
0.8041313886642456
0 references
[For the entire collection see Zbl 0536.00021.] Es wird gezeigt, daß die von \textit{V. Chvatal} [Math. Oper. Res. 4, 233-235 (1979; Zbl 0443.90066)] angegebene scharfe Schranke für die relative Überschreitung des Optimalwertes der Lösung von Mengen- Überdeckungsproblemen durch den Wert einer 'kurzsichtigen' Lösung gültig bleibt, wenn für die Überdeckung der einzelnen Elemente beliebige Vielfachheiten vorgegeben werden. Der aufmerksame Leser wird in der Arbeit einige offensichtliche Formulierungsmängel entdecken, so in der Heuristik 'BACK' und in Beispiel 2, in dem die beiden heuristischen Lösungen vertauscht sind.
0 references