A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program

DOI10.1016/0166-218X(87)90006-0zbMath0616.90063OpenAlexW2024416283MaRDI QIDQ1821694

Toshihide Ibaraki, Naoki Katoh

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90006-0

zbMATH Keywords

quasiconcave functionpolynomial timeapproximation schemeauxiliary problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Nonlinear programming (90C30) Sensitivity, stability, parametric optimization (90C31) Stochastic programming (90C15) Boolean programming (90C09)

Related Items

On the complexity and approximation of the maximum expected value all-or-nothing subset ⋮ A convex analysis approach for convex multiplicative programming ⋮ An \(\varepsilon\)-approximation scheme for combinatorial optimization problems with minimum variance criterion ⋮ A fully polynomial time approximation scheme for minimum cost-reliability ratio problems ⋮ An outer approximation method for minimizing the product of several convex functions on a convex set ⋮ An outcome space approach for generalized convex multiplicative programs ⋮ EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION ⋮ C-programming and the minimization of pseudolinear and additive concave functions ⋮ A Solution Strategy for a Class of Nonlinear Knapsack Problems ⋮ The simplex method as a global optimizer: A \(C\)-programming perspective

Cites Work

• C-programming problems: A class of non-linear optimization problems
• Analysis of a class of proxy problems
• C-programming. An outline
• C-programming: A nonlinear parametric optimization method
• Stochastic spanning tree problem
• A polynomial time algorithm for a chance-constrained single machine scheduling problem
• Recursive constraints and stochastic linear programming
• Finite state Markovian decision processes
• Combinatorial Optimization with Rational Objective Functions
• Computational complexity of parametric linear programming
• MINIMUM SPANNING TREE WITH NORMAL VARIATES AS WEIGHTS
• A Successive Underestimation Method for Concave Minimization Problems
• A Stochastic Programming Model
• On Some Properties of Programming Problems in Parametric form Pertaining to Fractional Programming
• On Nonlinear Fractional Programming
• Solving Bicriterion Mathematical Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item