Solving combinatorial problems with combined min-max-min-sum objective and applications. (English) Zbl 0682.90076

Minoux, M.

Math. Program., Ser. B 45, No. 2, 361-372 (1989).

Summary: 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.

MSC:

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

Keywords:

bottleneck cost function; linear cost function; matchings; matroid intersection; weighted edge coloring; bicriterion analysis

Software:

heapsort

References:

[1]	A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). · Zbl 0326.68005
[2]	P.M. Camerini, F. Maffioli, S. Martello and P. Toth, ”Most and least uniform spanning trees,”Discrete Applied Mathematics 15 (1986) 181–197. · Zbl 0611.05014
[3]	E.W. Dijkstra, ”A note on two problems in connection with graphs,”Numerische Mathematik 1 (1959) 269–271. · Zbl 0092.16002
[4]	E.A. Dinic, ”Algorithm for solution of a problem of maximum flow in a network with power estimation,”Soviet Mathematics. Doklady 11 (1970) 1277–1280. · Zbl 0219.90046
[5]	J. Edmonds, ”Maximum matching and a polyhedron with 0–1 vertices,”Journal of Research of the National Bureau of Standards. Section B 69 (1965) 125–130. · Zbl 0141.21802
[6]	J. Edmonds, ”Submodular functions, matroids and certain polyhedra,” in: R. Guy, ed.,Combinatorial Structures and their Applications (Gordon and Breach, New York, 1970) pp. 69–87. · Zbl 0268.05019
[7]	J. Edmonds, ”Matroids and the greedy algorithm,”Mathematical Programming 1 (1971) 127–136. · Zbl 0253.90027
[8]	J. Edmonds, ”Matroid intersection,”Annals of Discrete Mathematics 4 (1979) 39–49. · Zbl 0416.05025
[9]	H.N. Gabow, ”Implementations of algorithms for maximum matchings on nonbipartite graphs,” Ph.D. Dissertation, Computer Science Department, Stanford University (Stanford, CA, 1973).
[10]	M.R. Garey and D.S. Johnson,Computers and Intractability. An Introduction to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979). · Zbl 0411.68039
[11]	M. Gondran and M. Minoux,Graphes et Algorithmes (Eyrolles, Paris, 1979). [Translated as:Graphs and Algorithms (Wiley, New York, 1984).]
[12]	P. Hansen, ”Bicriterion path problems,” in: G. Fandel and T. Gal, eds.,Multiple Criteria Decision Making, Theory and Applications (Springer, Berlin, 1980) pp. 109–127. · Zbl 0444.90098
[13]	Y. Ito, Y. Urano, T. Muratani and M. Yamaguchi, ”Analysis of a switch matrix for an SS/TDMA system,”Proceedings of the IEEE 65 (1977) 411–419.
[14]	E. Johnson, ”On shortest paths and sorting,”Proceedings of Annual Conference of ACM (ACM, New York, 1972) 510.
[15]	E.L. Lawler,Combinatorial Optimization. Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). · Zbl 0413.90040
[16]	M. Minoux,Programmation Mathématique: Théorie et Algorithmes (Dunod, Paris, 1983). [Translated as:Mathematical Programming: Theory and Algorithms (Wiley, New York, 1986).]
[17]	M. Minoux, ”Optimal traffic assignment in a SS/TDMA frame: A new approach by set covering and column generation,”RAIRO 20 (1986) 1–13. · Zbl 0608.90076
[18]	M. Minoux, ”A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations,”RAIRO 21 (1987) 105–136. · Zbl 0644.90061
[19]	R.C. Prim, ”Shortest connection networks and some generalizations,”The Bell System Technical Journal 36 (1957) 1389.
[20]	R.E. Tarjan, ”A simple version of Karzanov’s blocking flow algorithm,”Operations Research Letters 2 (1984) 265–268. · Zbl 0542.05057
[21]	J.W.J. Williams, ”Algorithm 232: Heapsort,”Communications of the ACM 7 (1984) 347–348.