Greediest solutions are sometimes optimal
How does a greedy solution perform in terms of approximation? In our recent paper Approximation by lexicographically maximal solutions in matching and matroid intersection problems, we study how good a lexicographically maximal solution is in the weighted matching and matroid intersection problems. A solution is lexicographically maximal if it takes as many heaviest elements as…