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)
- 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
- A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem
- The multiple depot, multiple traveling salesmen facility-location problem: Vehicle range, service frequency, and heuristic implementations
- Polyhedral results for the bipartite induced subgraph problem
- A heuristic genetic algorithm for product portfolio planning
- Solving the car sequencing problem via branch \& bound
- Optimizing nuclear power plant refueling with mixed-integer programming
- Knapsack problems with setups
- Non-linear anonymous pricing combinatorial auctions
- Cutting planes in integer and mixed integer programming
- Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem
- \(k\)-interchange heuristic as an optimization procedure for material handling applications
- Mathematical models for applying cell suppression methodology in statistical data protection.
- Improved complexity bounds for location problems on the real line
- The asymmetric traveling salesman problem with replenishment arcs
- A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles
- Nonlinear integer programming by Darwin and Boltzmann mixed strategy
- Foundation-penalty cuts for mixed-integer programs.
- On the directed hop-constrained shortest path problem
- Applying the minimax criterion in stochastic recourse programs
- A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths
- Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands
- The maximum capture problem with random utilities: problem formulation and algorithms
- A model and methodologies for the location problem with logistical components
- Two alternative models for farm management: Discrete versus continuous time horizon
- Batch scheduling to minimize total completion time
- Some heuristic methods for solving \(p\)-median problems with a coverage constraint
- A model for the capacitated \(p\)-facility location problem in global environments
- Two-echelon, multi-commodity supply chain network design with mode selection, lead-times and inventory costs
- Partial convexification cuts for 0--1 mixed-integer programs
- Multi-objective design of team oriented assembly systems.
- An improved Lagrangian relaxation and dual ascent approach to facility location problems
- A generalized dual phase-2 simplex algorithm.
- Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty
- New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints
- A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
- Tighter representations for set partitioning problems
- Stochastic lot-sizing problem with deterministic demands and Wagner-Whitin costs
- A probabilistic analysis of the maximal covering location problem
- MINTO, a Mixed INTeger Optimizer
- Permuting matrices to avoid forbidden submatrices
- Loading and scheduling of a flexible assembly system by mixed integer programming.
- 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
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)
