Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms

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)

zbMATH Keywords

branch-and-bound algorithmlocationlogisticsgreedy heuristicsmaximization of submodular functions0-1 quadratic programconstraint generation algorithm

Mathematics Subject Classification ID

Quadratic programming (90C20) Inventory, storage, reservoirs (90B05) Boolean programming (90C09)

Cited In (only showing first 100 items - show all)

• Cardinality-restricted chains and antichains in partially ordered sets
• A cutting-plane approach to mixed 0-1 stochastic integer programs
• Material compatibility constraints for make-to-order production planning.
• A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing
• Optimization with binet matrices
• Mathematical models for optimal usage of tributary cards in wavelength assignment for DWDM ring networks
• A compact formulation of the ring loading problem with integer demand splitting
• An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.
• Cutting plane algorithms for \(0-1\) programming based on cardinality cuts
• On the linear description of the 3-cycle polytope
• A note on the MIR closure
• Neural network methods in combinatorial optimization
• Rerouting tunnels for MPLS network resource optimization
• Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
• Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
• Using penalty function and tabu search to solve cell formation problems with fixed cell cost.
• Conley's spectral sequence via the sweeping algorithm
• Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems
• Probabilistic partial set covering with an oracle for chance constraints
• Container vessel scheduling with bi-directional flows
• Integer programming approach to production scheduling for make-to-order manufacturing
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Solution methods for the balancing of jet turbines
• Process planning in a fuzzy environment
• Multiprogramming genetic algorithm for optimization problems with permutation property
• Differential approximation schemes for half-product related functions and their scheduling applications
• Approximability issues for unconstrained and constrained maximization of half-product related functions
• On dominated terms in the general knapsack problem
• A discrete mechanics approach to dislocation dynamics in BCC crystals
• A lexicographic approach to bi-objective loading of a flexible assembly system
• Solving the generalised assignment problem using polyhedral results
• Adjacency on the constrained assignment problem
• Optimal multicast route packing
• Channel allocation in cellular radio networks
• Partitioning of sequentially ordered systems using linear programming
• Cardinality constrained Boolean quadratic polytope
• Complexity of searching an immobile hider in a graph
• Optimal control on a graph with application to train scheduling problems
• The stable set polytope of icosahedral graphs
• Hybrid genetic algorithm for optimization problems with permutation property
• On solving the continuous data editing problem
• A polyhedral approach to bisubmodular function minimization
• The minimum flow cost Hamiltonian cycle problem: a comparison of formulations
• Distributed processing of divisible jobs with communication startup costs
• Branch and cut methods for network optimization
• Discrete models for data imputation
• Seasonal clustering technique for time series data
• Goal programming in the context of the assignment problem and a computationally effective solution method
• A branch-and-price algorithm for the Steiner tree packing problem.
• A branch-and-bound method for multicommodity location with balancing requirements
• A two-stage stochastic programming approach for multi-activity tour scheduling
• Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
• A sensitivity analysis of matching coin game strategies
• Upper and lower bounding strategies for the generalized minimum spanning tree problem
• An exact solution framework for the multiple gradual cover location problem
• Polymatroids and mean-risk minimization in discrete optimization
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• Point of presence design in internet protocol networks with performance guarantees
• Coloring planar Toeplitz graphs and the stable set polytope.
• Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line
• Minimum fractional dominating functions and maximum fractional packing functions
• Polytopes related to interval vectors and incidence matrices
• An optimization framework for ``build-or-buy decisions in software architecture
• Constrained 0-1 quadratic programming: basic approaches and extensions
• On a class of mixed-integer sets with a single integer variable
• Lifting facets of the cut polytope
• Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems
• The complexity of multidimensional periodic scheduling
• Graph imperfection. I
• Resolution search
• A dynamic model of controlling invasive species
• Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems
• Stochastic set packing problem
• Erratum to ``Comparison of column generation models for channel assignment in cellular networks
• Integer programming, Barvinok's counting algorithm and Gomory relaxations.
• A provable better Branch and Bound method for a nonconvex integer quadratic programming problem
• Balancedness of edge covering games
• Optimization and reconstruction of \(hv\)-convex (0,1)-matrices
• An improved approximation algorithm of MULTIWAY CUT.
• On the adjustment problem for linear programs
• Models and algorithms for network reduction
• Obtaining cell counts for contingency tables from rounded conditional frequencies
• Lifted Euclidean inequalities for the integer single node flow set with upper bounds
• The weighted uncapacitated planned maintenance problem: complexity and polyhedral properties
• Algorithms and implementation of a set partitioning approach for modular machining line design
• Size-constrained graph partitioning polytopes
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Strengthening the reliability fixed-charge location model using clique constraints
• A new filled function method for nonlinear integer programming problem
• On mixed-integer zero-one representations for separable lower-semicontinuous piecewise-linear functions
• A comparison of heuristics and relaxations for the capacitated plant location problem
• Upper bounds and heuristics for the 2-club problem
• Exact algorithms for procurement problems under a total quantity discount structure
• Modeling and solving a crew assignment problem in air transportation
• Exact solution procedures for the balanced unidirectional cyclic layout problem
• Nodes selection strategy in cooperative tracking problem
• Facets of the \((s,t)-p\)-path polytope
• A greedy approximation for minimum connected dominating sets
• Decomposition, reformulation, and diving in university course timetabling
• Optimal matrix-segmentation by rectangles

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)