The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks.
Now consider the following generalization: Instead of specifying a cost of a single agent-task pair, assume that you can specify a cost of an arbitrary set of agent-task pairs. The problem is then defined by a set of constraints, where each constraint is a cost c and a set S of task-agent pairs. Meaning of a such constraint is that a cost c occurs when all pairs in S are "satisfied", and the overall cost is the sum of costs of all satisfied constraints.
Note that this problem can be encoded as Weighted Partial MAX-SAT, where hard clauses encode one-to-one assignment between agents and tasks, and each constraint is a (weighted) soft clause.
However, I am interested if this can be reduced to something simpler or if this is a known problem, but so far wasn't able to find an answer.
Thanks for your help.
-
$\begingroup$ Thank you for the advice. Is it possible to delete this question from here? $\endgroup$Ivan– Ivan2015年01月20日 03:46:33 +00:00Commented Jan 20, 2015 at 3:46
-
$\begingroup$ Please don't. I like interesting questions - even if I don't know the answer! $\endgroup$Mike– Mike2015年01月20日 07:19:12 +00:00Commented Jan 20, 2015 at 7:19
1 Answer 1
Seems to me that the submodular welfare problem falls under your description. Have a look at http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf chapter 4; here we assume that the utility function of subsets is submodular. In general, your problem is just the combinatorial auction problem which is hard to approximate without any assumptions on the valuation function.
-
$\begingroup$ I took a quick look, and I don't see an immediate connection, but will try to go into more details later. Thanks. $\endgroup$Ivan– Ivan2015年01月24日 06:27:33 +00:00Commented Jan 24, 2015 at 6:27