Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
From MaRDI portal
Publication:3923934
DOI10.1016/S0304-0208(08)73471-6zbMATH Open0469.90052MaRDI QIDQ3923934FDOQ3923934
Authors: G. L. Nemhauser, Laurence A. Wolsey 
Publication date: 1981
Published in: North-Holland Mathematics Studies (Search for Journal in Brave)
branch-and-bound algorithmlocationlogisticsgreedy heuristicsmaximization of submodular functions0-1 quadratic programconstraint generation algorithm
Cited In (only showing first 100 items - show all)
- Real-time freight locomotive rescheduling and uncovered train detection during disruption
- Solving sequential knapsack problems
- The \(k\)-cardinality assignment problem
- The inverse-parametric knapsack problem
- Non-standard approaches to integer programming
- On the representability of totally unimodular matrices on bidirected graphs
- How to allocate hard candies fairly
- Optimization models for targeted offers in direct marketing: exact and heuristic algorithms
- A generalized Benders decomposition based algorithm for an inventory location problem with stochastic inventory capacity constraints
- An LP-based proof for the non-existence of a pair of orthogonal Latin squares of order 6.
- New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints
- A polynomially solvable special case of the unbounded knapsack problem
- Video distribution under multiple constraints
- Pareto optimization for subset selection with dynamic cost constraints
- Solving a fuzzy set-covering problem
- On tightening cover induced inequalities
- Lower bounds for the two-stage uncapacitated facility location problem
- Efficient solution generation for multiple objective linear programming based on extreme ray generation method
- An algorithm for the planar three-index assignment problem
- An alternative formulation for certain fuzzy set-covering problems
- Approximation algorithms for the Euclidean bipartite TSP
- A fixed interval due-date scheduling problem with earliness and due-date costs
- Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs
- A graph-theoretic heuristic for designing loop-layout manufacturing systems
- Sell or hold: A simple two-stage stochastic combinatorial optimization problem
- A robustness approach to uncapacitated network design problems
- Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
- Efficient reformulation for 0-1 programs -- methods and computational results
- An exact penalty function approach for nonlinear integer programming problems
- The design of a 0-1 integer optimizer and its application in the Carmen system
- Lifting cover inequalities for the precedence-constrained knapsack problem
- Covering non-uniform hypergraphs
- Using DEA to obtain efficient solutions for multi-objective 0--1 linear programs
- An approximate algorithm for nonlinear integer programming
- Classification of orthogonal arrays by integer programming
- Beam search heuristic to solve stochastic integer problems under probabilistic constraints
- ATM VP-based network design
- Improving computational capabilities for addressing volume constraints in forest harvest scheduling problems
- Decomposition schemes and acceleration techniques in application to production-assembly-distribution system design
- Orthogonal drawings of graphs with vertex and edge labels
- Stock selection heuristics for interdependent items
- A computationally efficient robust tube based MPC for linear switched systems
- A pegging approach to the precedence-constrained knapsack problem
- An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem
- A partial enumeration algorithm for pure nonlinear integer programming
- Polyhedral characterizations and perfection of line graphs
- On the convex hull of feasible solutions to certain combinatorial problems
- A primogenitary linked quad tree approach for solution storage and retrieval in heuristic binary optimization
- A Lagrangian relax-and-cut approach for the two-stage capacitated facility location problem
- Buyer-supplier games: optimization over the core
- Graph coloring with rejection
- A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
- An exact algorithm for the constraint satisfaction problem: Application to logical inference
- A method of transferring polyhedron between the intersection-form and the sum-form
- A class of web-based facets for the generalized vertex packing problem
- Cutting plane algorithms for the inverse mixed integer linear programming problem
- A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization
- Balancing problems in acyclic networks
- An approximate algorithm for nonlinear integer programming
- On the minors of an incidence matrix and Smith normal form
- Lagrangian approaches for a class of matching problems in computational biology
- An extended formulation approach to the edge-weighted maximal clique problem
- Supermodular functions and the complexity of MAX CSP
- Bounds on the size of branch-and-bound proofs for integer knapsacks
- A flexible ILP formulation for hierarchical clustering
- Complexity of local search for the \(p\)-median problem
- Adaptive modeling, adaptive data assimilation and adaptive sampling
- A column generation based algorithm for the robust graph coloring problem
- Facets of the \(p\)-cycle polytope
- A search heuristic for the sequence-dependent economic lot scheduling problem
- A polyhedral approach to edge coloring
- Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
- A theory of complexity for continuous time systems
- Robustness analysis of elementary flux modes generated by column generation
- On \(n\)-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets
- Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
- \((r|p)\)-centroid problems on networks with vertex and edge demand
- Pseudo-Boolean optimization
- A characterization of knapsacks with the max-flow--min-cut property
- Unimodularity of the Clar number problem
- Vehicle routing problem with trailers
- Tight linear programming relaxations of uncapacitated \(p\)-hub median problems
- Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
- GRASP for set packing problems.
- Preprocessing and cutting for multiple allocation hub location problems.
- Railway scheduling by network optimization
- Mathematical programming formulations for machine scheduling: A survey
- Generalized submodular cover problems and applications
- Vote trading in public elections
- Minimization of ordered, symmetric half-products
- New results on the completion time variance minimization
- Operations research in the space industry
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
- A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem
- A survey of computational complexity results in systems and control
- Minimizing maximum indegree
- A dynamic convexized method for nonconvex mixed integer nonlinear programming
- An exact algorithm for the knapsack sharing problem with common items
- Individuals, populations and fluid approximations: a Petri net based perspective
- Activity nets: A guided tour through some recent developments
This page was built for publication: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3923934)
