A primal-dual algorithm for the maximum charge problem with capacity constraints
dc.contributor.author | Bhattacharjee, Sangita | |
dc.contributor.author | University of Lethbridge. Faculty of Arts and Science | |
dc.contributor.supervisor | Gaur, Daya | |
dc.contributor.supervisor | Hossain, Shahadat | |
dc.date.accessioned | 2011-11-09T23:28:14Z | |
dc.date.available | 2011-11-09T23:28:14Z | |
dc.date.issued | 2010 | |
dc.degree.level | Masters | |
dc.description | ix, 96 leaves : ill. ; 29 cm | en_US |
dc.description.abstract | In this thesis, we study a variant of the maximum cardinality matching problem known as the maximum charge problem. Given a graph with arbitrary positive integer capacities assigned on every vertex and every edge, the goal is to maximize the assignment of positive feasible charges on the edges obeying the capacity constraints, so as to maximize the total sum of the charges. We use the primal-dual approach. We propose a combinatorial algorithm for solving the dual of the restricted primal and show that the primal-dual algorithm runs in a polynomial time. | en_US |
dc.identifier.uri | https://hdl.handle.net/10133/2557 | |
dc.language.iso | en_US | en_US |
dc.publisher | Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2010 | en_US |
dc.publisher.department | Department of Mathematics and Computer Science | en_US |
dc.publisher.faculty | Arts and Science | en_US |
dc.relation.ispartofseries | Thesis (University of Lethbridge. Faculty of Arts and Science) | en_US |
dc.subject | Matching theory | en_US |
dc.subject | Combinatorial optimization | en_US |
dc.subject | Graph theory | en_US |
dc.subject | Dissertations, Academic | en_US |
dc.title | A primal-dual algorithm for the maximum charge problem with capacity constraints | en_US |
dc.type | Thesis | en_US |