About strongly polynomial time algorithms for quadratic optimization over submodular constraints

zbMATH Open0844.90061MaRDI QIDQ1908017FDOQ1908017

Authors: Dorit S. Hochbaum, Sung-Pil Hong 

Publication date: 10 April 1996

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

Recommendations

• A strongly polynomial time algorithm for a constrained submodular optimization problem
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A faster strongly polynomial time algorithm for submodular function minimization
• A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

zbMATH Keywords

Kuhn-Tucker conditionsstrongly polynomial algorithmsparametric maximum flowlexicographically optimal flowconvex separable quadratic minimization over submodular constraints

Mathematics Subject Classification ID

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

Cited In (40)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908017)