The assignment problem with nearly Monge arrays and incompatible partner indices

DOI10.1016/j.dam.2016.04.019zbMath1355.90037OpenAlexW2344946706WikidataQ57949068 ScholiaQ57949068MaRDI QIDQ335350

Mohammad Hasan, M. Dambrine

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)

Related Items

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, Scheduling a proportionate flow shop of batching machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• 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
• Three-dimensional axial assignment problems with decomposable cost coefficients
• Perspectives of Monge properties in optimization
• On the recognition of permuted Supnick and incomplete Monge matrices
• Improved approximation algorithms for the max edge-coloring problem
• Monge properties, discrete convexity and applications
• A General Class of Greedily Solvable Linear Programs
• Assignment Problems
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• Reducibility among Combinatorial Problems
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Flow shop-sequencing problem with synchronous transfers and makespan minimization