Solving combinatorial problems with combined Min-Max-Min-Sum objective and applications

Solving combinatorial problems with combined Min-Max-Min-Sum objective and applications

0.00 Avg rating0 Votes
Article ID: iaor19891004
Country: Netherlands
Volume: 45
Issue: 2
Start Page Number: 361
End Page Number: 372
Publication Date: Oct 1989
Journal: Mathematical Programming
Authors:
Abstract:

The purpose of this paper is to introduce and study a new class of combinatorial optimization problems in which the objective function is the algebraic sum of a bottleneck cost function (Min-Max) and a linear cost function (Min-Sum). General algorithms for solving such problems are described and general complexity results are derived. A number of examples of application involving matchings, paths and cutsets, matroid bases, and matroid intersection problems are examined, and the general complexity results are specialized to each of them. The interest of these various problems comes in particular from their strong relation to other important and difficult combinatorial problems such as: weighted edge coloring of a graph; optimum weighted covering with matroid bases; optimum weighted partitioning with matroid intersections, etc. Another important area of application of the algorithms given in the paper is bicriterion analysis involving a Min-Max criterion and a Min-Sum one.

Reviews

Required fields are marked *. Your email address will not be published.