Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case

DOI10.1016/0377-2217(95)00205-7zbMath0918.90108OpenAlexW2036948347MaRDI QIDQ1278287

Yinhua Wang, Heesang Lee, Nemhauser, George I.

Publication date: 27 April 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(95)00205-7

zbMATH Keywords

submodular functionvalid inequalitiesmixed-integer programmingnode packing polyhedronquadratic cost partition

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, Hub Location as the Minimization of a Supermodular Set Function, Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem, A two-stage stochastic programming approach for influence maximization in social networks, Maximizing a class of submodular utility functions, Monotone submodular maximization over the bounded integer lattice with cardinality constraints, Maximization of submodular functions: theory and enumeration algorithms, A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem, The maximum capture problem with random utilities: problem formulation and algorithms, Submodular function minimization and polarity

Uses Software

• MINTO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The indefinite zero-one quadratic problem
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Geometric algorithms and combinatorial optimization
• A class of facet producing graphs for vertex packing polyhedra
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• An analysis of approximations for maximizing submodular set functions—I
• On the facial structure of set packing polyhedra