About: Multidimensional assignment problem

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by . This problem can be seen as a generalization of the linear assignment problem. In words, the problem can be described as follows: Alternatively, describing the problem using graph theory: The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.

Property Value
dbo:abstract
  • The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by . This problem can be seen as a generalization of the linear assignment problem. In words, the problem can be described as follows: An instance of the problem has a number of agents (i.e., cardinality parameter) and a number of job characteristics (i.e., dimensionality parameter) such as task, machine, time interval, etc. For example, an agent can be assigned to perform task X, on machine Y, during time interval Z. Any agent can be assigned to perform a job with any combination of unique job characteristics at some cost. These costs may vary based on the assignment of agent to a combination of job characteristics - specific task, machine, time interval, etc. The problem is to minimize the total cost of assigning the agents so that the assignment of agents to each job characteristic is an injective function, or one-to-one function from agents to a given job characteristic. Alternatively, describing the problem using graph theory: The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. (en)
dbo:wikiPageID
  • 70020816 (xsd:integer)
dbo:wikiPageLength
  • 6509 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1097591717 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • The multidimensional assignment problem (MAP) is a fundamental combinatorial optimization problem which was introduced by . This problem can be seen as a generalization of the linear assignment problem. In words, the problem can be described as follows: Alternatively, describing the problem using graph theory: The multidimensional assignment problem consists of finding, in a weighted multipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. (en)
rdfs:label
  • Multidimensional assignment problem (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License