Metraipolis › archive › dc_0617be635a09
Assignment problem — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Assignment_problem
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T04:37:04.776Z
- SHA-256 of the archived text
17d6b7ba05e5a4a8c206867ae8c91a6f1ceed853b50cc85b257eb282bff56869- Stable URL of this page
https://metraipolis.com/documento/dc_0617be635a09
How to cite
Assignment problem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Assignment_problem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_0617be635a09 (Metraipolis archive dc_0617be635a09, sha256 17d6b7ba05e5a4a8c206867ae8c91a6f1ceed853b50cc85b257eb282bff56869)
BibTeX
@misc{dc0617be635a09,
title = {Assignment problem — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Assignment_problem},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_0617be635a09; sha256 17d6b7ba05e5a4a8c206867ae8c91a6f1ceed853b50cc85b257eb282bff56869},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Assignment_problem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Alternatively, describing the problem using graph theory: The assignment problem consists of finding, in a weighted bipartite graph, a matching of maximum size, in which the sum of weights of the edges is minimum. If the numbers of agents and tasks are equal, then the problem is called balanced assignment, and the graph-theoretic version is called minimum-cost perfect matching. Otherwise, it is called unbalanced assignment. If the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called linear assignment. Commonly, when speaking of the assignment problem without any additional qualification, then the linear balanced assignment problem is meant. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico). Fonte: Wikipedia in inglese, voce «Assignment problem» — https://en.wikipedia.org/wiki/Assignment_problem Wikidata Q620614: «combinatorial optimization problem» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q620614 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Assignment_problem?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1384649504, consultata il 2026-11-10T04:34:07.080Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1f34d62672bccbb0e306c23015633cfc877fe08e38f97f0e36703f719acdfdbf