project_selection_problem (467B)
1 # Project selection problem 2 3 https://en.wikipedia.org/wiki/Project_selection_problem 4 5 you have projects and machines and want to optimize profit (revenue of selected projects minus cost of selected machines), and each project requires a specific subset of machines 6 7 reduces to [network_flow] 8 9 also works for arbitrary [directed_graphs] not just [bipartite_graphs] 10 - cf https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Project_Selection.pdf 11 12 Up: [network_flow]