On the supermodular knapsack problem
From MaRDI portal
Publication:1824552
DOI10.1007/BF01589108zbMath0682.90063WikidataQ56050298 ScholiaQ56050298MaRDI QIDQ1824552
Publication date: 1989
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Related Items
A column generation approach to job grouping for flexible manufacturing systems, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Knapsack problems with dependencies through non-additive measures and Choquet integral, The Expressive Power of Binary Submodular Functions, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, Recognition problems for special classes of polynomials in 0-1 variables, Classes of submodular constraints expressible by graph cuts, Global optimality conditions and optimization methods for quadratic knapsack problems, Efficient minimization of higher order submodular functions using monotonic Boolean functions, On reduction of duality gap in quadratic knapsack problems, The expressive power of binary submodular functions, Pseudo-Boolean optimization, A branch-and-bound algorithm for multi-dimensional quadratic 0–1 knapsack problems, Approximability issues for unconstrained and constrained maximization of half-product related functions, Linear programming for the \(0-1\) quadratic knapsack problem, Lagrangean methods for the 0-1 quadratic knapsack problem, Combinatorial optimization models for production scheduling in automated manufacturing systems, The submodular knapsack polytope, Polynomially Computable Bounds for the Probability of the Union of Events, A note on semidefinite relaxation for 0-1 quadratic knapsack problems, The quadratic 0-1 knapsack problem with series-parallel support, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Quasimonotone Boolean Functions and Bistellar Graphs
- Quadratic knapsack problems
- An analysis of approximations for maximizing submodular set functions—I
- Minimizing a Submodular Function on a Lattice
- A Fast Parametric Maximum Flow Algorithm and Applications