Show simple item record

Matching and Edge Covering Algorithms.

dc.contributor.authorPerin Filho, Clovis
dc.date.accessioned2020-09-08T23:30:54Z
dc.date.available2020-09-08T23:30:54Z
dc.date.issued1980
dc.identifier.urihttps://hdl.handle.net/2027.42/157806
dc.description.abstractThis study deals with the minimum weight 1-matching/covering problem defined here as follows: given an undirected network G = (N,A,c) where N is a nonempty set of n nodes, A is a set of m edges, and c is a vector of edge weights, find a 0-1 vector x = {x(i;j)} to minimize (SIGMA)(,ij) {c(i;j) x(i;j) : (i;j) (ELEM) A} (LESSTHEQ) 1 for i (ELEM) N('-) subject to (SIGMA)(,j) {x(i;j) : (i;j) (ELEM) A} = 1 for i (ELEM) N('1) (GREATERTHEQ) 1 for i (ELEM) N('+) unconstrained for i (ELEM) N('0) x(i;j) = 0, 1 for (i;j) (ELEM) A where N('-),N('1),N('+),N('0) is a given partition. The minimum weight 1-matching/covering problem is an extension of well known problems like the minimum weight 1-matching (N = N('-)), the minimum weight 1-perfect matching (N = N('1)), and the minimum weight 1-edge covering (N = N('+)). A primal dual algorithm with time complexity O(n('2)m) is developed for solving the problem; such time complexity can be further improved to O(n('3)). Like many other combinatorial optimization problems, appropriate constraints - blossom constraints - are introduced in the problem in order to obtain the optimality conditions through Linear Programming Theory. Computer results are discussed based on a PL1 implementation of the algorithm. As a remark, the computer program can be seen as a simple extension of a computer program for the minimum weight 1-matching problem. Another O(n('2)m) algorithm is developed in order to deal with sensitivity analysis; by sensitivity analysis is meant the study of the changes in the optimal solution when modifications are introduced either in the structure of the network or in the edge weights; furthermore, we discuss how to solve the modified problem starting from the old optimal solution. A very promising application of the minimum weight 1-matching/covering problem is proposed; it appears in a branch and bound approach for solving the set covering problem; the approach is based on the Lagrangian Relaxation of the c and idate problems into minimum weight 1-matching/covering problems, which are efficiently solved in order to obtain good lower bounds for the objective value of the original set covering problem. The Lagrangian Relaxation technique requires the c and idate problem to be solved with a sequence of different objective functions; these c and idate problems maintain a certain initial structure and change the cost coefficient of the objective function. The efficient computation of the c and idate problems with so many objective functions is made possible by the successive application of the sensitivity analysis results, because the changes in the objective function correspond to changes in the edge weights of the network.
dc.format.extent232 p.
dc.languageEnglish
dc.titleMatching and Edge Covering Algorithms.
dc.typeThesis
dc.description.thesisdegreenamePhDen_US
dc.description.thesisdegreedisciplineIndustrial engineering
dc.description.thesisdegreegrantorUniversity of Michigan
dc.subject.hlbtoplevelEngineering
dc.contributor.affiliationumcampusAnn Arbor
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/157806/1/8017337.pdfen_US
dc.owningcollnameDissertations and Theses (Ph.D. and Master's)


Files in this item

Show simple item record

Remediation of Harmful Language

The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.

Accessibility

If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.