Complexity and algorithms for nonlinear optimization problems
From MaRDI portal
Publication:2480263
DOI10.1007/s10479-007-0172-6zbMath1159.90485OpenAlexW2051716090MaRDI QIDQ2480263
Publication date: 31 March 2008
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-007-0172-6
Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)
Related Items
Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ Ameso optimization: a relaxation of discrete midpoint convexity ⋮ Scaling, proximity, and optimization of integrally convex functions ⋮ Constrained state estimation for stochastic jump systems: moving horizon approach ⋮ Resource allocation problems with expensive function evaluations ⋮ Discrete Midpoint Convexity ⋮ A complex-valued gradient flow for the entangled bipartite low rank approximation ⋮ Mean‐standard deviation model for minimum cost flow problem ⋮ A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems ⋮ Optimal procurement and production planning for multi-product multi-stage production under yield uncertainty ⋮ Selfish splittable flows and NP-completeness ⋮ A faster algorithm for the resource allocation problem with convex cost functions ⋮ A heuristic method for the supplier selection and order quantity allocation problem ⋮ A Polynomial-Time Descent Method for Separable Convex Optimization Problems with Linear Constraints ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ Network Flow Optimization with Minimum Quantities ⋮ Decreasing minimization on M-convex sets: background and structures ⋮ Decreasing minimization on M-convex sets: algorithms and applications ⋮ Decreasing minimization on base-polyhedra: relation between discrete and continuous cases
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear time algorithms for some separable quadratic programming problems
- Some proximity and sensitivity results in quadratic integer programming
- A polynomial algorithm for minimum quadratic cost flow problems
- A theorem on flows in networks
- A parametric algorithm for convex cost network flow and related problems
- An O(n) algorithm for quadratic knapsack problems
- Complexity and algorithms for convex network optimization and other nonlinear problems
- A strongly polynomial minimum cost circulation algorithm
- Unimodular functions
- A solvable case of quadratic 0-1 programming
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- A simplex algorithm for piecewise-linear programming. II: Finiteness, feasibility and degeneracy
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- The complexity of selection and ranking in X+Y and matrices with sorted columns
- On an instance of the inverse shortest paths problem
- A polynomial algorithm for an integer quadratic non-separable transportation problem
- The empirical performance of a polynomial algorithm for constrained nonlinear optimization
- On the use of an inverse shortest paths algorithm for recovering linearly correlated costs
- Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs
- Time bounds for selection
- The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
- A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
- A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization
- A nonlinear knapsack problem
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
- Solving the Convex Cost Integer Dual Network Flow Problem
- Lower Bounds for Computations with the Floor Operation
- Inverse Optimization
- Efficient Algorithms for the Inverse Spanning-Tree Problem
- Solving integer minimum cost flows with separable convex cost objective polynomially
- Optimal Flows in Networks with Multiple Sources and Sinks, with Applications to Oil and Gas Lease Investment Programs
- The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
- A new approach to the maximum-flow problem
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Fast Approximation Algorithms for Knapsack Problems
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Maximal Closure of a Graph and Applications to Combinatorial Problems
- Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources
- Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
- Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications
- Minimizing a Convex Cost Closure Set
- A Fast Parametric Maximum Flow Algorithm and Applications
- Network Optimization Problems: Algorithms, Applications and Complexity
- On the Complexity of the Production-Transportation Problem
- Computationally Related Problems
- An efficient algorithm for image segmentation, Markov random fields and related problems
- On Hochbaum's Proximity-Scaling Algorithm for the General Resource Allocation Problem
- Convex separable optimization is not much harder than linear optimization
