An Improved Approximation for Maximum k-Dependent Set on Bipartite Graphs
Presentation for the 2021 INFORMS Annual Meeting.
The talk is based on the following paper:
Seyedmohammadhossein Hosseinian and Sergiy Butenko. An improved approximation for Maximum -dependent Set on bipartite graphs. Discrete Applied Mathematics, 307: 95-101, 2022.
https://www.sciencedirect.com/science...
00:00 Opening
00:44 Introduction
07:26 The Algorithm and Its Analysis
20:13 Concluding Remarks