This project is aimed to develop a lagrangian relaxation based upper bound for finding weighted maximum b-matching. The targets of the project is
- Develop an effiecient computational approach for finding a good upper bound on maximum weighted b-matching in graph.
- Development of a heuristic for finding feasible soluton
- Exploration of parallel and distributed algorithms.
For learning about b-matching read the paper https://www.cs.purdue.edu/homes/apothen/Papers/bMatching-SISC-2016.pdf
For learning about lagrangian relaxation for combinatorial optimization see the paper http://www.ece.utah.edu/~kalla/phy_des/lagrange-relax-tutorial-fisher.pdf
We have used subgradient methods for solving the dual problem. See