The assignment problem with nearly Monge arrays and incompatible partner indices

DOI10.1016/J.DAM.2016.04.019MaRDI QIDQ335350zbMATHOpenAlexWikidataFDO

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

zbMATH Keywords

assignment problemMonge arrayMonge property

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

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

Cites work

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

Cited in

(7)

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

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)