Keywords
Submodular set functionMatroidMathematicsCombinatoricsLinear programming relaxationGreedy algorithmDiscrete mathematicsHeuristicsCombinatorial optimizationFunction (biology)Set functionRelaxation (psychology)HeuristicSet (abstract data type)Linear programmingMathematical optimizationComputer science
Affiliated Institutions
Related Publications
Integer and Combinatorial Optimization
FOUNDATIONS. The Scope of Integer and Combinatorial Optimization. Linear Programming. Graphs and Networks. Polyhedral Theory. Computational Complexity. Polynomial-Time Algorithm...
A Direct Formulation for Sparse PCA Using Semidefinite Programming
Given a covariance matrix, we consider the problem of maximizing the variance explained by a particular linear combination of the input variables while constraining the number o...
Ant system: optimization by a colony of cooperating agents
An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach...
Codes on graphs: normal realizations
A generalized state realization of the Wiberg (1996) type is called normal if symbol variables have degree 1 and state variables have degree 2. A natural graphical model of such...
On coresets for k-means and k-median clustering
In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that gi...
Publication Info
- Year
- 1978
- Type
- article
- Volume
- 14
- Issue
- 1
- Pages
- 265-294
- Citations
- 4301
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
4301
OpenAlex
Cite This
George L. Nemhauser,
Laurence A. Wolsey,
Marshall L. Fisher
(1978).
An analysis of approximations for maximizing submodular set functions—I.
Mathematical Programming
, 14
(1)
, 265-294.
https://doi.org/10.1007/bf01588971
Identifiers
- DOI
- 10.1007/bf01588971