O problema da designação e sua variante parametrica

TL;DRAbstract

This d1ssertation is a.bout the Assignment Problem: given a.n edge-we. ighted bipartite graph, find a perfect ma.tching of minimum weight. ln the first part of this work we present a det.ailed survey of the literature on this problem. including basic concepts and main results. In the second part, we discuss a parametric variant of this problem. In this variant, the weight of each edge e is given by c; + c;, where c: and c; are constants and ). is the parameler. that is, a real value that can vary. tor a given range of ). values we want to find ali solutions to the corresponding assignment problems in the least possible t1me. ln this part of Lhe work we initially present a survey of techniques for solving general Combinatorial Optimization parametric problems. We then present a. technique, a]so from the litera.t.ure. for solving the parametric minimum cost ftow problcm 1 of which the assignment problem is a special case. This technique is based on the network simplex algorithm. \Ve then

Chat with Paper

AI Agents for this Paper