The assignment problem with nearly Monge arrays and incompatible partner indices

DOI10.1016/J.DAM.2016.04.019zbMATH Open1355.90037OpenAlexW2344946706WikidataQ57949068 ScholiaQ57949068MaRDI QIDQ335350FDOQ335350

Authors: C. Weiß, Sigrid Knust, N. V. Shakhlevich, Stefan Waldherr 

Publication date: 2 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.04.019

Recommendations

• Weak Monge arrays in higher dimensions
• A Monge property for the \(d\)-dimensional transportation problem
• Recognition of \(d\)-dimensional Monge arrays
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• A note on the parity assignment problem

zbMATH Keywords

assignment problemMonge arrayMonge property

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Cites Work

• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Title not available (Why is that?)
• Assignment Problems
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Three-dimensional axial assignment problems with decomposable cost coefficients
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Perspectives of Monge properties in optimization
• On the recognition of permuted Supnick and incomplete Monge matrices
• Extreme Hamiltonian lines
• Minimizing the number of tardy job units under release time constraints
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results
• On the complexity of decomposing matrices arising in satellite communication
• Pyramidal tours with step-backs and the asymmetric traveling salesman problem
• Recognition of \(d\)-dimensional Monge arrays
• A Monge property for the \(d\)-dimensional transportation problem
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• Improved approximation algorithms for the max edge-coloring problem
• Monge properties, discrete convexity and applications
• A general class of greedily solvable linear programs
• Title not available (Why is that?)
• Flow shop-sequencing problem with synchronous transfers and makespan minimization
• On the max-weight edge coloring problem
• A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
• Complexity results for flow shop problems with synchronous movement

Cited In (7)

• Tropical reproducing kernels and optimization
• Scheduling a proportionate flow shop of batching machines
• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
• Open shop scheduling with synchronization
• Allocation under a general substitution structure
• Weak Monge arrays in higher dimensions
• A note on the parity assignment problem

This page was built for publication: The assignment problem with nearly Monge arrays and incompatible partner indices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q335350)