About strongly polynomial time algorithms for quadratic optimization over submodular constraints

zbMath0844.90061MaRDI QIDQ1908017

Publication date: 10 April 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

Kuhn-Tucker conditions strongly polynomial algorithms parametric maximum flow lexicographically optimal flow convex separable quadratic minimization over submodular constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Linear programming (90C05)

Related Items (39)

Quadratic M-convex and L-convex functions ⋮ A survey of scheduling with controllable processing times ⋮ Algorithms for the continuous nonlinear resource allocation problem -- new implementations and numerical studies ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ Quadratic resource allocation with generalized upper bounds ⋮ Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost ⋮ On a Reduction for a Class of Resource Allocation Problems ⋮ A fast algorithm for quadratic resource allocation problems with nested constraints ⋮ A Newton's method for the continuous quadratic knapsack problem ⋮ A class of nonlinear nonseparable continuous Knapsack and multiple-choice knapsack problems ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance ⋮ Theory of Principal Partitions Revisited ⋮ Inverse scheduling: Two-machine flow-shop problem ⋮ Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints ⋮ Maximize a monotone function with a generic submodularity ratio ⋮ Variable fixing algorithms for the continuous quadratic Knapsack problem ⋮ A survey on the continuous nonlinear resource allocation problem ⋮ A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions ⋮ Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Breakpoint searching algorithms for the continuous quadratic knapsack problem ⋮ Two-machine open shop problem with controllable processing times ⋮ Fast algorithm for singly linearly constrained quadratic programs with box-like constraints ⋮ Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ Simple solution methods for separable mixed linear and quadratic knapsack problem ⋮ Resource allocation problems in decentralized energy management ⋮ The newsvendor problem with capacitated suppliers and quantity discounts ⋮ A Decomposition Algorithm for Nested Resource Allocation Problems ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ Variable fixing method by weighted average for the continuous quadratic knapsack problem ⋮ Inverse scheduling with maximum lateness objective ⋮ Discrete convex analysis ⋮ Decreasing minimization on M-convex sets: background and structures ⋮ Decreasing minimization on M-convex sets: algorithms and applications ⋮ The nonlinear knapsack problem - algorithms and applications ⋮ Decreasing minimization on base-polyhedra: relation between discrete and continuous cases ⋮ An Efficient Hybrid Algorithm for the Separable Convex Quadratic Knapsack Problem

This page was built for publication: About strongly polynomial time algorithms for quadratic optimization over submodular constraints