Improved Greedy for Non-Regular Graphs