ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

A greedy algorithm for solving a certain class of linear programmes (1973)

Dunstan, F. D. J. ; Welsh, D. J. A.

Springer

Mathematical programming 5 (1973), S. 338-353

add to mindlist on the mindlist

Details

ISSN: 1436-4646

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract If is a collection of subsets ofS andw is a nonnegative weight function onS, the problem of selecting a subset belonging to which has maximum weight is solved by a ‘greedy-type’ algorithm forall w if and only if is the set of independent sets of a matroid. This result is then generalised to show that ‘greedy-type’ algorithms select an optimum forall linear functionsc·x; x in some compact set $$U \subseteq R^n $$ andc 〉 0 if and only if the convex closure ofU is essentially a polymatroid. A byproduct of this is a new characterization of polymatroids.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01580137

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit