Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
From MaRDI portal
Publication:3923934
DOI10.1016/S0304-0208(08)73471-6zbMath0469.90052MaRDI QIDQ3923934
Nemhauser, George I., 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
Related Items (only showing first 100 items - show all)
Discrete models for data imputation ⋮ Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems ⋮ A column generation approach to the coalition formation problem in multi-agent systems ⋮ Hybrid genetic algorithm for optimization problems with permutation property ⋮ Minimizing maximum indegree ⋮ Efficient solution generation for multiple objective linear programming based on extreme ray generation method ⋮ Monge matrices make maximization manageable ⋮ Batch scheduling to minimize total completion time ⋮ A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope ⋮ Permuting matrices to avoid forbidden submatrices ⋮ The application of valid inequalities to the multi-stage lot-sizing problem ⋮ A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization ⋮ A branch-and-cut algorithm for the minimum branch vertices spanning tree problem ⋮ Cardinality-restricted chains and antichains in partially ordered sets ⋮ The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs ⋮ Tighter representations for set partitioning problems ⋮ \(\varepsilon\)-approximation minimization of convex functions in fixed dimension ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ On solving the continuous data editing problem ⋮ Short rational generating functions for solving some families of fuzzy integer programming problems ⋮ Some heuristic methods for solving \(p\)-median problems with a coverage constraint ⋮ Real-time freight locomotive rescheduling and uncovered train detection during disruption ⋮ Maximum coverage problem with group budget constraints ⋮ A two-stage stochastic programming approach for multi-activity tour scheduling ⋮ A simple finite cutting plane algorithm for integer programs ⋮ Container shipping service selection and cargo routing with transshipment limits ⋮ Relocation problems arising in conservation biology ⋮ Preprocessing and cutting for multiple allocation hub location problems. ⋮ Multi-objective design of team oriented assembly systems. ⋮ On the directed hop-constrained shortest path problem ⋮ Models for representing piecewise linear cost functions ⋮ Valid integer polytope (VIP) penalties for branch-and-bound enumeration ⋮ A two-stage stochastic programming approach for influence maximization in social networks ⋮ Valid inequalities for the single arc design problem with set-ups ⋮ Local search inequalities ⋮ Multi-commodity variable upper bound flow models ⋮ Fathoming rules for biobjective mixed integer linear programs: review and extensions ⋮ Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes ⋮ Facets for continuous multi-mixing set with general coefficients and bounded integer variables ⋮ 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 ⋮ Multicommodity flows and Benders decomposition for restricted continuous location problems ⋮ A generalized Benders decomposition based algorithm for an inventory location problem with stochastic inventory capacity constraints ⋮ An exact solution framework for the multiple gradual cover location problem ⋮ Two-echelon, multi-commodity supply chain network design with mode selection, lead-times and inventory costs ⋮ A class of web-based facets for the generalized vertex packing problem ⋮ Minimization of ordered, symmetric half-products ⋮ A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem ⋮ A provable better Branch and Bound method for a nonconvex integer quadratic programming problem ⋮ Applying the minimax criterion in stochastic recourse programs ⋮ Partial convexification cuts for 0--1 mixed-integer programs ⋮ Large-scale influence maximization via maximal covering location ⋮ An improved Lagrangian relaxation and dual ascent approach to facility location problems ⋮ A probabilistic analysis of the maximal covering location problem ⋮ A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems ⋮ Note on combinatorial optimization with max-linear objective functions ⋮ Efficient reformulation for 0-1 programs -- methods and computational results ⋮ A branch-and-bound method for multicommodity location with balancing requirements ⋮ Deterministic network interdiction ⋮ On the minors of an incidence matrix and Smith normal form ⋮ New results on the completion time variance minimization ⋮ The base-matroid and inverse combinatorial optimization problems. ⋮ A generalized dual phase-2 simplex algorithm. ⋮ An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope. ⋮ Pareto optimization for subset selection with dynamic cost constraints ⋮ An exact cutting plane method for \(k\)-submodular function maximization ⋮ A computational study of using preprocessing and stronger formulations to solve large general fixed charge problems ⋮ Approximation algorithms for knapsack problems with cardinality constraints ⋮ Unbounded knapsack problem: Dynamic programming revisited ⋮ The asymmetric traveling salesman problem with replenishment arcs ⋮ Consistency problems in ER-schemas for database systems ⋮ An improved approximation algorithm of MULTIWAY CUT. ⋮ The simple plant location problem: Survey and synthesis ⋮ Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands ⋮ Service network design in freight transportation ⋮ A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles ⋮ A Lagrangian relax-and-cut approach for the two-stage capacitated facility location problem ⋮ Valid inequalities for a class of assembly system problems ⋮ Using DEA to obtain efficient solutions for multi-objective 0--1 linear programs ⋮ A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths ⋮ The maximum capture problem with random utilities: problem formulation and algorithms ⋮ The transportation problem with exclusionary side constraints and two branch-and-bound algorithms ⋮ A search heuristic for the sequence-dependent economic lot scheduling problem ⋮ Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line ⋮ Generalized submodular cover problems and applications ⋮ A network-flow-based lower bound for the minimum weighted integer coloring problem ⋮ Covering non-uniform hypergraphs ⋮ Graph imperfection. I ⋮ Combinatorial optimization: current successes and directions for the future ⋮ Simultaneous loading, routing, and assembly plan selection in a flexible assembly system ⋮ Optimal project selection when borrowing and lending rates differ ⋮ A theory of complexity for continuous time systems ⋮ On the linear description of the 3-cycle polytope ⋮ Erratum to ``Comparison of column generation models for channel assignment in cellular networks ⋮ A model and methodologies for the location problem with logistical components ⋮ A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems ⋮ Two alternative models for farm management: Discrete versus continuous time horizon ⋮ Stock selection heuristics for interdependent items ⋮ Totally tight Chvatal-Gomory cuts ⋮ Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
This page was built for publication: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
