Solving combinatorial problems with combined min-max-min-sum objective and applications

DOI10.1007/BF01589111zbMath0682.90076MaRDI QIDQ1824562

Michel Minoux

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

matchingsmatroid intersectionbicriterion analysislinear cost functionweighted edge coloringbottleneck cost function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

Related Items (18)

On combined minmax-minsum optimization ⋮ On ranking of feasible solutions of a bottleneck linear programming problem ⋮ On weighting two criteria with a parameter in combinatorial optimization problems ⋮ A bilevel bottleneck programming problem ⋮ Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector ⋮ On bilevel fractional programming ⋮ Generalized multiple objective bottleneck problems ⋮ 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 ⋮ The fair OWA one-to-one assignment problem: NP-hardness and polynomial time special cases ⋮ Inverse max+sum spanning tree problem under weighted \(l_1\) norm by modifying the sum-cost vector ⋮ Kruskal with embedded C-semirings to solve MST problems with partially-ordered costs ⋮ Multiple bottleneck assignment problem ⋮ An \(O(m\log n)\) algorithm for the max+sum spanning tree problem ⋮ A Survey on Multiple Objective Minimum Spanning Tree Problems ⋮ Inverse max+sum spanning tree problem under weighted \(l_{\infty}\) norm by modifying max-weight vector ⋮ The stochastic bottleneck linear programming problem ⋮ Minimum deviation and balanced optimization: A unified approach

Uses Software

• heapsort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A simple version of Karzanov's blocking flow algorithm
• Most and least uniform spanning trees
• Matroid Intersection
• Optimal traffic assignment in a SS/TDMA frame : a new approach by set covering and column generation
• A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
• Maximum matching and a polyhedron with 0,1-vertices
• Matroids and the greedy algorithm

This page was built for publication: Solving combinatorial problems with combined min-max-min-sum objective and applications