Well-layered maps—A class of greedily optimizable set functions

Dress A, Terhalle W (1995)
Applied Mathematics Letters 8(5): 77-80.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Dress, AndreasUniBi; Terhalle, Werner
Abstract / Bemerkung
Given a finite set E of cardinality, say, N and a map f : P(E) --> ($) over bar R := RU{-infinity}, we define a sequence e(1),...,e(N) of elements of E to be f-greedy if e(i) is not an element of {e(1),...,e(i)-1} and f({e(1),...,e(i)}) greater than or equal to f({e(1),...,e(i-1} boolean OR {e}) for all i is an element of {1,...,N} and all e is an element of E\{e(1),...,e(i-1)}. In addition, for any map eta : E --> R we put f(eta)(x) := f(x) + sigma(e is an element of x) eta(e) for all x subset of or equal to E, and we define f to be a well-layered map if for every eta : E --> R, every f(eta)-greedy sequence e(1),...,e(N) is an element of E and every layer p(i)(E) := {y subset of or equal to E parallel to #y = i} (i = 0,..., N) we have f(eta)({e(1),...,e(i)}) = max{f(eta)(y) parallel to y is an element of p(i)(E)}. In this note, we characterize well-layered maps by some appropriate quantified version of the greedoid exchange condition or-quivalently-by some appropriate greedoidal version of the quantitative relations defining valuated matroids and valuated Delta-matroids, respectively.
Stichworte
VALUATED DELTA-MATROIDS; GREEDOIDS; GREEDY; ALGORITHMS; MATROIDS; VALUATED MATROIDS
Erscheinungsjahr
1995
Zeitschriftentitel
Applied Mathematics Letters
Band
8
Ausgabe
5
Seite(n)
77-80
ISSN
0893-9659
Page URI
https://pub.uni-bielefeld.de/record/1640158

Zitieren

Dress A, Terhalle W. Well-layered maps—A class of greedily optimizable set functions. Applied Mathematics Letters. 1995;8(5):77-80.
Dress, A., & Terhalle, W. (1995). Well-layered maps—A class of greedily optimizable set functions. Applied Mathematics Letters, 8(5), 77-80. https://doi.org/10.1016/0893-9659(95)00070-7
Dress, A., and Terhalle, W. (1995). Well-layered maps—A class of greedily optimizable set functions. Applied Mathematics Letters 8, 77-80.
Dress, A., & Terhalle, W., 1995. Well-layered maps—A class of greedily optimizable set functions. Applied Mathematics Letters, 8(5), p 77-80.
A. Dress and W. Terhalle, “Well-layered maps—A class of greedily optimizable set functions”, Applied Mathematics Letters, vol. 8, 1995, pp. 77-80.
Dress, A., Terhalle, W.: Well-layered maps—A class of greedily optimizable set functions. Applied Mathematics Letters. 8, 77-80 (1995).
Dress, Andreas, and Terhalle, Werner. “Well-layered maps—A class of greedily optimizable set functions”. Applied Mathematics Letters 8.5 (1995): 77-80.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar