An -approximation scheme for combinatorial optimization problems with minimum variance criterion

DOI10.1016/0166-218X(92)90037-BMaRDI QIDQ1183333zbMATH OpenFDO

Authors Naoki Katoh

Publication date 28 June 1992

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

Full work available at URL https://doi.org/10.1016/0166-218X(92)90037-B

zbMATH Keywords

polynomial timefinding a feasible subsetfully polynomial time approximationminimum variance problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• AN ε-APPROXIMATION SCHEME FOR MINIMUM VARIANCE PROBLEMS
• A fully polynomial time approximation scheme for minimum cost-reliability ratio problems
• Balanced optimization problems
• Fast fully polynomial approximation schemes for minimizing completion time variance
• A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A Stochastic Programming Model
• A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program
• A polynomial time algorithm for a chance-constrained single machine scheduling problem
• Balanced optimization problems
• C-programming problems: A class of non-linear optimization problems
• C-programming. An outline
• Complexity of some parametric integer and network programming problems
• MINIMUM SPANNING TREE WITH NORMAL VARIATES AS WEIGHTS
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• Minimal Cost-Reliability Ratio Spanning Tree
• On Nonlinear Fractional Programming
• On Some Properties of Programming Problems in Parametric form Pertaining to Fractional Programming
• Stochastic spanning tree problem
• VARIANCE CONSTRAINED MARKOV DECISION PROCESS

Cited in

(8)

• The Rank-One Quadratic Assignment Problem
• Minimum dispersion problems
• Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\)
• AN ε-APPROXIMATION SCHEME FOR MINIMUM VARIANCE PROBLEMS
• The balanced traveling salesman problem
• Generalized Bottleneck Problems^∗
• Constrained balanced optimization problems
• The quadratic balanced optimization problem

This page was built for publication: An \(\varepsilon\)-approximation scheme for combinatorial optimization problems with minimum variance criterion

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