graph-theory icon indicating copy to clipboard operation
graph-theory copied to clipboard

More examples of assignment problems

Open root-11 opened this issue 5 years ago • 0 comments

Here's a list:

    - Assignment problems (AP)
      - Explain that AP is special case of GAP with just one agent.
       - Explain why the hungarian algorithm is subperformant relative to alternating iterative auction.

    - The Knapsack problem (code done, tutorial missing)
        - Cutting stock problem (https://en.wikipedia.org/wiki/Cutting_stock_problem)
        - 3D bin packing problem

    - Maximum flow (code done, tutorial missing)
    - Minimum costs (code done? )
    - Assignment problem with allowed groups

    - Quadratic assignment problem (https://en.wikipedia.org/wiki/Quadratic_assignment_problem)
      and Facility location problem (https://en.wikipedia.org/wiki/Facility_location_problem)
        - Explain that the problem resembles that of the assignment problem, except that the
          cost function is expressed in terms of quadratic inequalities, hence the name.
        - Example: The problem is to assign all facilities to different locations with the
          goal of minimizing the sum of the distances multiplied by the corresponding flows.

          Hint: Use XY-graph for solving the problem.

root-11 avatar Sep 22 '20 14:09 root-11