# Metadata

- Title: An Analysis of Approximations for Maximizing Submodular Set Functions - I
- Authors: G. L. Nemhauser, L. A. Wolsey, M. L. Fisher
- Year: 1978
- Venue: Mathematical Programming
- Primary group: submodular
- Secondary tags: foundations, maximization, greedy, local-improvement, cardinality
- Problem: approximation algorithms for maximizing submodular set functions, especially under cardinality-type constraints
- Main guarantee: classical greedy and local-improvement approximation analysis, including the landmark greedy bound for monotone submodular maximization
- Key techniques: marginal-gain greedy analysis, worst-case approximation bounds, local search, LP relaxation viewpoint
- Status: processed-deep, foundational-original
- Tags: #submodular #maximization #greedy #approximation #cardinality #foundations
- Inbox source: inbox/AN ANALYSIS OF APPROXIMATIONS FOR.pdf
- Duplicate input files: inbox/sub-modular.pdf