An \(\varepsilon\)-approximation scheme for combinatorial optimization problems with minimum variance criterion

DOI10.1016/0166-218X(92)90037-BzbMath0751.90062MaRDI QIDQ1183333

Naoki Katoh

Publication date: 28 June 1992

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

zbMATH Keywords

polynomial timefinding a feasible subsetfully polynomial time approximationminimum variance problem

Mathematics Subject Classification ID

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

Related Items (6)

Minimum dispersion problems ⋮ The Rank-One Quadratic Assignment Problem ⋮ The balanced traveling salesman problem ⋮ Generalized Bottleneck Problems^∗ ⋮ Constrained balanced optimization problems ⋮ The quadratic balanced optimization problem

Cites Work

• Unnamed Item
• Unnamed Item
• Balanced optimization problems
• C-programming problems: A class of non-linear optimization problems
• C-programming. An outline
• Stochastic spanning tree problem
• 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
• Complexity of some parametric integer and network programming problems
• VARIANCE CONSTRAINED MARKOV DECISION PROCESS
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• MINIMUM SPANNING TREE WITH NORMAL VARIATES AS WEIGHTS
• Minimal Cost-Reliability Ratio Spanning Tree
• A Stochastic Programming Model
• On Some Properties of Programming Problems in Parametric form Pertaining to Fractional Programming
• On Nonlinear Fractional Programming

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