Everything About ___
Live briefing

Everything about Assignment problem

Combinatorial optimization problem

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized. Wikipedia →

🧭 Start here: a 6-step reading path

  1. Read the overview: Assignment problemA 5-minute orientation
  2. Skim a recent paper: Berth allocation and quay crane assignment/scheduling problem under uncertainty: A surveyInfluential work since 2022
  3. Pick up a classic book: Dynamic Allocation and PricingThe most-reprinted book on the subject
  4. Read the landmark paper: The Hungarian method for the assignment problemCited 10,892 times
  5. Go sideways: Minimum-cost flow problemA closely related topic
  6. Go sideways: Maximum-weight matchingA closely related topic

📖 Definitions

Noun A fundamental combinatorial optimization problem in which a number of agents must be assigned to perform a number of tasks, each incurring some cost specific to that agent-task combination, with the goal of performing as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, and with minimal total cost.

🗂️ The subject at a glance

  1. Examples
  2. Formal definition
  3. Algorithms
  4. Many-to-many assignment
  5. Generalization

🏆 Landmark papers (most cited)

🆕 Influential since 2022

📚 Books worth reading

Ranked by number of editions on Open Library, a rough measure of how lasting a book is.

🔗 Related topics