Rewarding Maps: On Greedy Optimization of Set Functions

Dress A, Terhalle W (1995)
Advances in Applied Mathematics 16(4): 464-483.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Dress, AndreasUniBi; Terhalle, Walter
Abstract / Bemerkung
Given a set function, that is, a map f:P(E) --> (R) over bar = R boolean OR (-infinity) from the set P(E) of subsets of a finite set E into the reals including -infinity, the standard greedy algorithm (GA) for optimizing f starts with the empty set and then proceeds by enlarging this set greedily, element by element. A set function f is said to be tractable if in this way a sequence x(0) = empty set, x(1),...,x(N) = E (N = #E) of subsets with max(f) is an element of {f(x(0)), f(x(1)),...,f(x(N))} will always be found. In this note, we will reinterpret and transcend the traditions of classicaI GA-theory (cf., e.g., KLS ) by establishing necessary and sufficient conditions for a set function f not just to be tractable as it stands, but to give rise to a whole family of tractable set functions f(eta):P(E) --> (R) over bar:x --> f(x) + Sigma(e is an element of x)eta(e), where eta runs through all real valued weighting schemes eta:E --> R, in which case f will be called rewarding. In addition, we will characterize two important subclasses of rewarding maps, viz. truncatably rewarding (or well-layered) maps, that is, set functions f such that f((i)):P(E) --> (R) over bar:x --> GRAPHICS is rewarding for every i = 1,..., N, and matroidal maps, that is, set functions f such that for every eta:E --> R and every f(eta)-greedy sequence x(0),x(1),...,x(N) as above, one has max(f(eta)) = f(eta)(x(i)) for the unique i is an element of {0,...,N} with f(eta)(x(0)) < f(eta)(x(1))<...< f(eta)(x(i))greater than or equal to f(eta)(x(i+1)). (C) 1995 Academic Press, Inc.
Erscheinungsjahr
1995
Zeitschriftentitel
Advances in Applied Mathematics
Band
16
Ausgabe
4
Seite(n)
464-483
ISSN
0196-8858
Page URI
https://pub.uni-bielefeld.de/record/1629159

Zitieren

Dress A, Terhalle W. Rewarding Maps: On Greedy Optimization of Set Functions. Advances in Applied Mathematics. 1995;16(4):464-483.
Dress, A., & Terhalle, W. (1995). Rewarding Maps: On Greedy Optimization of Set Functions. Advances in Applied Mathematics, 16(4), 464-483. https://doi.org/10.1006/aama.1995.1022
Dress, A., and Terhalle, W. (1995). Rewarding Maps: On Greedy Optimization of Set Functions. Advances in Applied Mathematics 16, 464-483.
Dress, A., & Terhalle, W., 1995. Rewarding Maps: On Greedy Optimization of Set Functions. Advances in Applied Mathematics, 16(4), p 464-483.
A. Dress and W. Terhalle, “Rewarding Maps: On Greedy Optimization of Set Functions”, Advances in Applied Mathematics, vol. 16, 1995, pp. 464-483.
Dress, A., Terhalle, W.: Rewarding Maps: On Greedy Optimization of Set Functions. Advances in Applied Mathematics. 16, 464-483 (1995).
Dress, Andreas, and Terhalle, Walter. “Rewarding Maps: On Greedy Optimization of Set Functions”. Advances in Applied Mathematics 16.4 (1995): 464-483.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar