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)
- 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
- 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
- Decomposition based hybrid metaheuristics
- A branch-price-and-cut algorithm for the minimum evolution problem
- A branch-price-and-cut method for the vegetable crop rotation scheduling problem with minimal plot sizes
- A branch-cut-and-price algorithm for the piecewise linear transportation problem
- The data transfer problem in a system of systems
- Multi-level facility location as the maximization of a submodular set function
- Deterministic network interdiction
- Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing
- Combinatorial optimization: current successes and directions for the future
- A column generation heuristic for a dynamic generalized assignment problem
- Optimization and analysis of the profitability of tariff structures with two-part tariffs
- An approximate dynamic programming approach for the vehicle routing problem with stochastic demands
- Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms
- Climate change and optimal energy technology R\&D policy
- A discrete dynamic convexized method for nonlinear integer programming
- Parametric mixed-integer 0-1 linear programming: The general case for a single parameter
- Properties of some ILP formulations of a class of partitioning problems
- The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem
- The multi-level uncapacitated facility location problem is not submodular
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)
