A greedy algorithm for maximizing a linear objective function

DOI10.1016/S0166-218X(02)00311-6MaRDI QIDQ2773612zbMATH OpenFDO

Authors V. V. Shenmajer

Publication date 24 February 2002

Published in Diskretnyĭ Analiz i Issledovanie Operatsiĭ. Seriya 1 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(02)00311-6

zbMATH Keywords

greedoidindependence systemmatroid

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial optimization (90C27)

Review text

The article deals with generalizations of the classical problem of finding a maximum-weight base of a matroid. Three optimization problems are considered: the maximum-weight base for an accessible set system, the maximum-weight maximal vector for an accessible vector system, and the maximum-weight inextensible path for an indexed digraph. The standard greedy algorithm is applied for these problems. Necessary and sufficient conditions are proven for finding an optimal solution by the algorithm. For a set-system over a finite ground set, \textit{B.~Korte} and \textit{L.~Lovász} have shown in [SIAM J. Algebraic Discrete Methods 5, No. 2, 229-238 (1984; Zbl 0538.05027)] that the greedy algorithm finds an optimal solution if and only if a strong exchange property holds. Now this result is generalized for vector-systems. New criteria and sufficient conditions are established for the case of nonmonotone systems.

Recommendations

• scientific article; zbMATH DE number 169611
• Greedoids and Linear Objective Functions
• Problems on independence systems solvable by the greedy algorithm
• A framework for the greedy algorithm
• A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids

Cites work

• scientific article; zbMATH DE number 4137538 (Why is no real title available?)
• scientific article; zbMATH DE number 3341035 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Linear objective functions on certain classes of greedoids
• Matroids and the greedy algorithm
• Note on Independence Functions
• Optimal assignments in an ordered set: An application of matroid theory

Cited in

(9)

• The \(S\)-digraph optimization problem and the greedy algorithm
• Two algorithms for a class of elliptic problems in shape optimization
• New polyhedral and algorithmic results on greedoids
• Problems on independence systems solvable by the greedy algorithm
• Greedy Families for Linear Objective Functions
• scientific article; zbMATH DE number 169611 (Why is no real title available?)
• Algorithm for solving partially - linear optimization problems obtained by getting maximum of functions
• On the generality of the greedy algorithm for solving matroid base problems
• Greedy algorithms for eigenvalue optimization problems in shape design of two-density inhomogeneous materials

This page was built for publication: A greedy algorithm for maximizing a linear objective function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2773612)