Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems

Romaric Duvignau, Noël Gillet, Ralf Klasing

Finding a maximum-weight matching is a classical and well-studied problem in computer science, solvable in cubic time in general graphs. We consider the specialization called assig…