Minimum deviation and balanced optimization: A unified approach

DOI10.1016/0167-6377(91)90085-4MaRDI QIDQ806674zbMATH OpenOpenAlexFDO

Authors A. Volgenant, Cees Duin

Publication date 1991

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(91)90085-4

zbMATH Keywords

balanced optimizationbottleneck criteriaminimum deviationpathsspanning treesSteiner trees

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Review text

In minimum deviation problems one seeks to minimize the difference between maximum and average weight in a solution. This paper introduces a general solution scheme that is also suited for balanced optimization, i.e. the problem to find a solution that has a minimal deviation between the largest and the smallest weight. The approach is analyzed with respect to computational complexity for spanning trees, paths and Steiner trees in graphs.

Recommendations

• The balanced minimum evolution problem under uncertain data
• On generalized balanced optimization problems
• Min-max formulation of the balance number in multiobjective global optimization.
• Balanced optimization problems
• Unified minimax methods
• On min-norm and min-max methods of multi-objective optimization
• Optimization with some uncontrollable variables: a min-equilibrium approach
• scientific article; zbMATH DE number 5618680
• Balanced Optimization with Vector Costs

Cites work

• A note on two problems in connexion with graphs
• An edge elimination test for the Steiner problem in graphs
• Balanced optimization problems
• scientific article; zbMATH DE number 3989103 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3575371 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Minimum deviation problems
• Optimal traffic assignment in a SS/TDMA frame : a new approach by set covering and column generation
• Solving combinatorial problems with combined min-max-min-sum objective and applications
• The Min-Max Spanning Tree Problem and some extensions
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees

Cited in

(19)

• Minimum deviation problems
• An O(m n) algorithm for the max+sum spanning tree problem
• Minimum dispersion problems
• Solving some lexicographic multi-objective combinatorial problems
• Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector
• Constrained balanced optimization problems
• The quadratic balanced optimization problem
• Quadratic bottleneck knapsack problems
• Some inverse optimization problems under the Hamming distance
• The Deviation Constraint
• A Survey on Multiple Objective Minimum Spanning Tree Problems
• scientific article; zbMATH DE number 1286742 (Why is no real title available?)
• scientific article; zbMATH DE number 1052832 (Why is no real title available?)
• Inverse max + sum spanning tree problem by modifying the sum-cost vector under weighted \(l_\infty \) norm
• On the generality of the greedy algorithm for solving matroid base problems
• Quadratic bottleneck problems
• The balanced traveling salesman problem
• Inverse max+sum spanning tree problem under weighted l₁ norm by modifying the sum-cost vector
• Assignment problems: a golden anniversary survey

This page was built for publication: Minimum deviation and balanced optimization: A unified approach

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