Talk:Assignment problem
 | This  level-5 vital article is rated Start-class on Wikipedia's content assessment scale.It is of interest to the following WikiProjects: |
||||||||||
| |||||||||||
Old talk edit
does anyone know why an assignment problem is intersting? Jfeckstein 14:18, 4 Aug 2003 (UTC)
- Not I. But, I haven't studied any assignment problems, so I shouldn't expect to. Do you think that it isn't encyclopedic? It is probably useful, and maybe some mathematician will come in and give us some interesting examples. Paullusmagnus 14:31, 4 Aug 2003 (UTC)
It seems encyclopedic, and it is informative, but it could be even better. Jfeckstein 14:34, 4 Aug 2003 (UTC)
- It could be better for sure. Sorry I was paranoid. Paullusmagnus 14:49, 4 Aug 2003 (UTC)
This should be linked to matching. Deco 22:45, 18 November 2005 (UTC)
The solution in "Solving an assignment problem" appears to lack symmetry, and could be wrong. It is definitely hard to read.
Also a proper article about the problem should present the known lower bound for it and an asymptotic algorithm for best (or most popular) existing algorithms. Otherwise the reader cannot see how hard the problem is. Wazow 17:42, 4 March 2006 (UTC)
Order of preference edit
What do you call the problem when agents rank the tasks in order of preference instead of assigning them costs? If that is also called the "assignment problem", it would be nice to describe it in this article; otherwise, it would be nice to link to a page that does describe the problem. Hashproduct 23:22, 5 November 2006 (UTC)
- That is a trivial reduction. Let preference = cost (i.e. rated 1-5, 1 is highest) or cost = 1/preference owise Joseph.Re 20:15, 16 July 2007 (UTC)
- Not exactly. First of all, there is a problem with the question itself (to ask a proper question is just as important as to give a proper answer). Now, the Assignment problems consists of two parts: weight function and cost function, both of them make the assignment problem the assigment problem. In your answer you assumed that the asking person wants the sum to be the cost function. But if it were so, I believe he would not have asked the question at all, since it is trivial to understand that it does not matter what to sum: weights or places, like when skating is judged. What was asked is the problem of ranking, which is indeed undercovered in wikipedia. There are many situations when summation is bad idea for ranking, and more complex rank functions are used (the simplest example (again, from sports competitions) is when the highest and the lowest individual ranks are discarded and the rest is summed), and the best total rank is no longer modelled by the assignment problem. `'Míkka 20:30, 16 July 2007 (UTC)
- Ah, I see what you mean. In that case, I agree it would be worthwhile to add. Joseph.Re 16:28, 20 July 2007 (UTC)
- Not exactly. First of all, there is a problem with the question itself (to ask a proper question is just as important as to give a proper answer). Now, the Assignment problems consists of two parts: weight function and cost function, both of them make the assignment problem the assigment problem. In your answer you assumed that the asking person wants the sum to be the cost function. But if it were so, I believe he would not have asked the question at all, since it is trivial to understand that it does not matter what to sum: weights or places, like when skating is judged. What was asked is the problem of ranking, which is indeed undercovered in wikipedia. There are many situations when summation is bad idea for ranking, and more complex rank functions are used (the simplest example (again, from sports competitions) is when the highest and the lowest individual ranks are discarded and the rest is summed), and the best total rank is no longer modelled by the assignment problem. `'Míkka 20:30, 16 July 2007 (UTC)
dupe? edit
is this a dupe of Activity selection problem? I'm too tired to tell right now. Spencerk (talk) 22:16, 28 August 2014 (UTC)
- No, it's a different problem. In the activity selection problem we try to maximize a number of tasks that can be executed in a given timeframe without overlapping. In the assignment problem, we try to assign tasks to workers, where every worker has a cost assigned to each task.143.215.144.105 (talk) 15:24, 6 May 2016 (UTC)
Please consider incorporating material from the above draft submission into this article. Drafts are eligible for deletion after 6 months of inactivity. ~Kvng (talk) 13:22, 18 November 2019 (UTC)
Confusing Definition edit
The first definition of the problem states that the goal is to maximize the number of completed task while minimizing cost, but from later parts I understood that the problem is only cost minimization while all tasks need to be completed. This is a bit confusing and I'm not sure what the right definition is. YotamEdit (talk) 18:32, 7 July 2021 (UTC)
- I think https://en.wikipedia.org/wiki/Hungarian_algorithm has a better explanation. Workers can only work on one task (and a task is only assigned 1 worker). So there will always be the same amount of tasks completed.
- This problem tries to minimize the total cost. Kinda like your second definition, but sometimes if there are less workers than tasks, some tasks won't get a worker, and won't be completed. AltoStev (talk) 01:04, 31 December 2022 (UTC)