The assignment problem with nearly Monge arrays and incompatible partner indices
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Weiss, C. | |
dc.contributor.author | Knust, S. | |
dc.contributor.author | Shakhlevich, N. V. | |
dc.contributor.author | Waldherr, S. | |
dc.date.accessioned | 2021-12-23T16:11:12Z | - |
dc.date.available | 2021-12-23T16:11:12Z | - |
dc.date.issued | 2016 | |
dc.identifier.issn | 0166218X | |
dc.identifier.uri | https://osnascholar.ub.uni-osnabrueck.de/handle/unios/9582 | - |
dc.description.abstract | In this paper we study the d-dimensional assignment problem in which entries of the cost array satisfy the Monge property, except for infinity-entries, which may violate it. We assume that the infinity-entries are incurred by incompatible partner indices and their number is bounded by an upper bound lambda for each index. We show that the problem can be solved in linear time for fixed d and lambda, and it becomes strongly NP-hard if d or lambda is part of the input. (C) 2016 The Authors. Published by Elsevier B.V. | |
dc.description.sponsorship | Engineering and Physical Sciences Research CouncilUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [1446781, 1640570, EP/K041274/1] Funding Source: researchfish; EPSRCUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/K041274/1] Funding Source: UKRI | |
dc.language.iso | en | |
dc.publisher | ELSEVIER SCIENCE BV | |
dc.relation.ispartof | DISCRETE APPLIED MATHEMATICS | |
dc.subject | ALGORITHMS | |
dc.subject | Assignment problem | |
dc.subject | COMPLEXITY | |
dc.subject | Mathematics | |
dc.subject | Mathematics, Applied | |
dc.subject | Monge array | |
dc.subject | Monge property | |
dc.subject | NUMBER | |
dc.subject | RECOGNITION | |
dc.title | The assignment problem with nearly Monge arrays and incompatible partner indices | |
dc.type | journal article | |
dc.identifier.doi | 10.1016/j.dam.2016.04.019 | |
dc.identifier.isi | ISI:000380082400017 | |
dc.description.volume | 211 | |
dc.description.startpage | 183 | |
dc.description.endpage | 203 | |
dc.contributor.orcid | 0000-0003-0577-9933 | |
dc.identifier.eissn | 18726771 | |
dc.publisher.place | PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS | |
dcterms.isPartOf.abbreviation | Discret Appl. Math. | |
dcterms.oaStatus | hybrid, Green Published | |
crisitem.author.dept | FB 06 - Mathematik/Informatik | - |
crisitem.author.dept | FB 06 - Mathematik/Informatik | - |
crisitem.author.deptid | fb06 | - |
crisitem.author.deptid | fb06 | - |
crisitem.author.parentorg | Universität Osnabrück | - |
crisitem.author.parentorg | Universität Osnabrück | - |
crisitem.author.netid | KnSi808 | - |
crisitem.author.netid | WaSt588 | - |
Seitenaufrufe
7
Letzte Woche
0
0
Letzter Monat
2
2
geprüft am 07.06.2024