Annual Symposium on Foundations of Computer Science · 2007 · 28 citations · 0 references
Natural SciencesComputer ScienceAlgorithmsFacility LocationOptimizationCombinatorial OptimizationConstrained OptimizationConvex OptimizationGraph AlgorithmsInteger ProgrammingOptimization TheoryConstraint Optimization ProblemsFacility Location On GraphsGraph OptimizationLocation-allocation ProblemsSubmodular MaximizationSubmodular Optimization
Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.