Skip to main content
MathOverflow

Return to Question

edited body
Source Link
Thomas Edison
Thomas Edison
  • 221
  • 1
  • 7

Suppose we want to assign $n$ items to $m$ customers ($m \geq n$$n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here, we must assign every item; therefore, a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.

This can be modeled as an integer linear program. However, I wonder whether there might be a better approach, namely, a polynomial algorithm. Note that if we do not require that each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?

Suppose we want to assign $n$ items to $m$ customers ($m \geq n$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here, we must assign every item; therefore, a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.

This can be modeled as an integer linear program. However, I wonder whether there might be a better approach, namely, a polynomial algorithm. Note that if we do not require that each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?

Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here, we must assign every item; therefore, a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.

This can be modeled as an integer linear program. However, I wonder whether there might be a better approach, namely, a polynomial algorithm. Note that if we do not require that each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?

Minor edits
Source Link
edit approved Jun 30, 2018 at 8:41
Rodrigo de Azevedo
edit approved Jun 30, 2018 at 8:41
Rodrigo de Azevedo
  • 1
  • 3
  • 16
  • 35

An variation of an assignment problem in combinatorics: Assignassign items to customers

Suppose we want to assign $n$ items to $m$ customers ($m \geq n$). Each assignment fromof an item $i$ to a customer $j$ will has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here, we must assign every item,item; therefore, a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.

This problem can be modeled as an integer linear programmingprogram. However, I wonder whether there might be a better approach (a, namely, a polynomial algorithm??). Note that if we do not require that each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?

An variation of an assignment problem in combinatorics: Assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($m \geq n$). Each assignment from an item $i$ to a customer $j$ will has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here we must assign every item, therefore a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.

This problem can be modeled as an integer linear programming. However, I wonder there might be a better approach (a polynomial algorithm??). Note that if we do not require each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?

An variation of an assignment problem in combinatorics: assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($m \geq n$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here, we must assign every item; therefore, a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.

This can be modeled as an integer linear program. However, I wonder whether there might be a better approach, namely, a polynomial algorithm. Note that if we do not require that each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?

Source Link
Thomas Edison
Thomas Edison
  • 221
  • 1
  • 7

An variation of an assignment problem in combinatorics: Assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($m \geq n$). Each assignment from an item $i$ to a customer $j$ will has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. Here we must assign every item, therefore a customer might receive more than one item. Moreover, we require that each customer must receive at least one item.

This problem can be modeled as an integer linear programming. However, I wonder there might be a better approach (a polynomial algorithm??). Note that if we do not require each customer must receive at least one item, then we just assign each item to the customer with the maximum cost. Does anyone have any idea?