Generalized assignment problem

Generalized assignment problem

In applied mathematics, the maximum general assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task might vary from one agent to the other.

This problem in its most general form is as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost and profit that may vary depending on the agent-task assignment. Moreover, each agent has a budget and the sum of the costs of task assigned to it cannot exceed this budget. It is required to find an assignment in which all agents do not exceed their budget and total profit of the assignment is maximized.

pecial cases

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the maximum assignment problem. When the costs and profits of all agents-task assignment are equal, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the Knapsack problem.

Definition

In the following, we have "n" kinds of items, x_1 through x_n and "m" kinds of bins b_1 through b_m. Each bin b_i is associated with a budget w_i. For a bin b_i, each item x_j has a profit p_{ij} and a weight w_{ij}. A solution is subset of items "U" and an assignment from "U" to the bins. A feasible solution is a solution in which for each bin b_i the weights sum of assigned items is at most w_i. The solution's profit is the sum of profits for each item-bin assignment. The goal is to find a maximum profit feasible solution.

Mathematically the generalized assignment problem can be formulated as::maximize sum_{i=1}^msum_{j=1}^n p_{ij} x_{ij}.:subject to sum_{j=1}^n w_{ij} x_{ij} le w_i qquad i=1, ldots, m;:: sum_{i=1}^m x_{ij} leq 1 qquad j=1, ldots, n;:: x_{ij} in {0,1} qquad i=1, ldots, m, quad j=1, ldots, n;

The generalized assignment problem is NP-hard, and it is even APX-hard to approximation. Recently it was shown that it is (e/(e-1) - epsilon) hard to approximate for every epsilon.

Greedy approximation algorithm

Using any algorithm ALG alpha-approximation algorithm for the knapsack problem, it is possible to construct a ( alpha+1)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept.The algorithm constructs a schedule in iterations, where during iteration j a tentative selection of items to bin b_j is selected.The selection for bin b_j might change as items might be reselected in a later iteration for other bins.The residual profit of an item x_i for bin b_j is p_{ij} if x_i is not selected for any other bin or p_{ij}p_{ik} if x_i is selected for bin b_k.

Formally: We use a vector T to indicate the tentative schedule during the algorithm. Specifically, T [i] =j means the item x_i is scheduled on bin b_j and T [i] =-1 means that item x_i is not scheduled. The residual profit in iteration j is denoted by P_j, where P_j [i] =p_{ij} if item x_i is not scheduled (i.e. T [i] =-1) and P_j [i] =p_{ij}-p_{ik} if item x_i is scheduled on bin b_k (i.e. T [i] =k).

Formally:: Set T [i] =-1 for all i = 1ldots n: For j=1...m do::: Call ALG to find a solution to bin b_j using the residual profit function P_j. Denote the selected items by S_j.:: Update T using S_j, i.e., T [i] =j for all i in S_j.

ee also

*Assignment problem

References

Further reading

* Katzir Cohen and Raz (2006). [http://www.cs.technion.ac.il/~lirank/pubs/2006-IPL-Generalized-Assignment-Problem.pdf "An Efficient Approximation for the Generalized Assignment Problem"] ,
* Fleischer, Goemans, Mirrokni, and Sviridenko (2006). [http://www-math.mit.edu/~goemans/ga-soda06.pdf "Tight Approximation Algorithms for Maximum General Assignment Problems"] ,
* Hans Kellerer and U. Pferschy D. Pisinger (2005). "Knapsack Problems ". Springer Verlag ISBN 3-540-40286-1


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Route assignment — Route assignment, route choice, or traffic assignment concerns the selection of routes (alternative called paths) between origins and destinations in transportation networks. It is the fourth step in the conventional transportation forecasting… …   Wikipedia

  • Constraint satisfaction problem — Constraint satisfaction problems (CSP)s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite… …   Wikipedia

  • Counterfeit coin problem — Information theory was created in 1948 by Claude Shannon. This theory has notably enriched the field of research into mathematics, economics, biology, psychology, semantics, etc. As an example, this theory recently contributed to quantum… …   Wikipedia

  • David Shmoys — Fields Computer Science, Computational complexity theory Institutions Cornell …   Wikipedia

  • Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Operations research — For the academic journal, see Operations Research: A Journal of the Institute for Operations Research and the Management Sciences. Operations research (also referred to as decision science, or management science) is an interdisciplinary… …   Wikipedia

  • Memetic algorithm — Memetic algorithms (MA) represent one of the recent growing areas of research in evolutionary computation. The term MA is now widely used as a synergy of evolutionary or any population based approach with separate individual learning or local… …   Wikipedia

  • GAP — steht für: Gap (Hautes Alpes), eine Stadt in Ostfrankreich Gap Inc., eine US amerikanische Modekette Gap steht für: (gæp, engl. für „Aussparung, Lücke, Spalt, Leerstelle“) GAAP oder Generally Accepted Accounting Procedures, ein auch von der… …   Deutsch Wikipedia

  • Gap — steht für: Gap (Hautes Alpes), eine Stadt in Ostfrankreich Gap (Pennsylvania), Vereinigte Staaten Gap Mills (West Virginia), Vereinigte Staaten Gap Springs Township (Polk County, Arkansas), Vereinigte Staaten Gap Township (Montgomery County,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”