Convex separable optimization is not much harder than linear optimization
From MaRDI portal
Publication:5753748
DOI10.1145/96559.96597zbMath0721.90060OpenAlexW2053352956MaRDI QIDQ5753748
J. George Shanthikumar, Dorit S. Hochbaum
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/96559.96597
polynomial algorithmlinear constraintspolynomial solvabilityproximity resultsscaling algorithmsnonlinear separable convex objective function
Programming involving graphs or networks (90C35) Convex programming (90C25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items (76)
Tensors in computations ⋮ A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks ⋮ Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Quadratic M-convex and L-convex functions ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization ⋮ A unified approach for a 1D generalized total variation problem ⋮ Proximity in concave integer quadratic programming ⋮ Refined proximity and sensitivity results in linearly constrained convex separable integer programming ⋮ The complexity of vector partition ⋮ A nonlinear knapsack problem ⋮ A capacity scaling algorithm for convex cost submodular flows ⋮ Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms ⋮ Improving the Cook et al. proximity bound given integral valued constraints ⋮ Ameso optimization: a relaxation of discrete midpoint convexity ⋮ A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables ⋮ Tail mutual exclusivity and Tail-VaR lower bounds ⋮ A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs ⋮ On a Reduction for a Class of Resource Allocation Problems ⋮ Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach ⋮ Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids ⋮ Scaling, proximity, and optimization of integrally convex functions ⋮ Approximate separable multichoice optimization over monotone systems ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Discrete Midpoint Convexity ⋮ Streaming graph computations with a helpful advisor ⋮ Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube ⋮ An approximation algorithm for indefinite mixed integer quadratic programming ⋮ A multi-stage stochastic programming approach in master production scheduling ⋮ A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems ⋮ Scheduling for electricity cost in a smart grid ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Efficient methods for selfish network design ⋮ Balancing of agricultural census data by using discrete optimization ⋮ Selfish splittable flows and NP-completeness ⋮ Slack allocation algorithm for parallel machines ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ Using quadratic programming to solve high multiplicity scheduling problems on parallel machines ⋮ Improved randomized approximation algorithms for lot-sizing problems ⋮ A polynomial algorithm for an integer quadratic non-separable transportation problem ⋮ Graver basis and proximity techniques for block-structured separable convex integer minimization problems ⋮ A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices ⋮ Strongly polynomial algorithm for a production-transportation problem with concave production cost ⋮ Complexity and algorithms for nonlinear optimization problems ⋮ Design of manufacturing systems using queueing models ⋮ Vector and matrix apportionment problems and separable convex integer optimization ⋮ On polynomial solvability of the high multiplicity total weighted tardiness problem ⋮ Global optimization for first order Markov random fields with submodular priors ⋮ Analysis of a joint pricing and seat allocation model in a hub-to-hub airline network ⋮ Maximum network flows with concave gains ⋮ On the relationship between the integer and continuous solutions of convex programs ⋮ Parameterized shifted combinatorial optimization ⋮ Mathematical programming for network revenue management revisited ⋮ Convergent Lagrangian and domain cut method for nonlinear knapsack problems ⋮ Distances between optimal solutions of mixed-integer programs ⋮ A Polynomial-Time Descent Method for Separable Convex Optimization Problems with Linear Constraints ⋮ When is rounding allowed in integer nonlinear optimization? ⋮ Subdeterminants and Concave Integer Quadratic Programming ⋮ A Decomposition Algorithm for Nested Resource Allocation Problems ⋮ On Proximity for k-Regular Mixed-Integer Linear Optimization ⋮ Scheduling multiple products on parallel machines with setup costs ⋮ Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ Optimizing flow rates in a queueing network with side constraints ⋮ Scheduling meets \(n\)-fold integer programming ⋮ New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems ⋮ Exact and approximate algorithms for high-multiplicity parallel machine scheduling ⋮ Inverse optimization for linearly constrained convex separable programming problems ⋮ A Polyhedral Frobenius Theorem with Applications to Integer Optimization ⋮ The nestedness property of the convex ordered median location problem on a tree ⋮ Bounds for global optimization of capacity expansion and flow assignment problems ⋮ Unnamed Item ⋮ Optimal preemptive scheduling for general target functions ⋮ The empirical performance of a polynomial algorithm for constrained nonlinear optimization ⋮ Scheduling for Electricity Cost in Smart Grid
This page was built for publication: Convex separable optimization is not much harder than linear optimization
