Perspectives of Monge properties in optimization

DOI10.1016/0166-218X(95)00103-XzbMath0856.90091OpenAlexW2105016507WikidataQ56170870 ScholiaQ56170870MaRDI QIDQ1923588

Bettina Klinz, Rüdiger Rudolf, Rainer E. Burkard

Publication date: 9 October 1996

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

Full work available at URL: https://doi.org/10.1016/0166-218x(95)00103-x

zbMATH Keywords

Monge matrix recognition problems

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial optimization (90C27)

Related Items

Tractability of explaining classifier decisions, Sometimes travelling is easy: The master tour problem, Independence versus indetermination: basis of two canonical clustering criteria, Inventory allocation with full downward substitution and monotone cost differences, A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case, An LP-based characterization of solvable QAP instances with chess-board and graded structures, A New Tractable Case of the QAP with a Robinson Matrix, Equilibrated anti-Monge matrices, Unnamed Item, On the traveling salesman problem with a relaxed Monge matrix, An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays, Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search, Online dynamic programming speedups, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, The Expressive Power of Binary Submodular Functions, Supermodular functions and the complexity of MAX CSP, A sparse multiscale algorithm for dense optimal transport, The assignment problem with nearly Monge arrays and incompatible partner indices, Technical note: Split algorithm in \(O(n)\) for the capacitated vehicle routing problem, Efficiently solvable special cases of hard combinatorial optimization problems, Optimal couplings are totally positive and more, Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon, An inverse problem for the collapsing sum, Technical Note—A Monge Sequence-Based Approach to Characterize the Competitive Newsvendor Problem, Submodular linear programs on forests, Speeding up the AIFV-2 dynamic programs by two orders of magnitude using range minimum queries, Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems, Computing an eigenvector of an inverse Monge matrix in max-plus algebra, Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks, Pyramidal tours and multiple objectives, Spanning trees and shortest paths in Monge graphs, On scheduling a single machine with resource dependent release times, Traditional Inventory Models for Better Price Competitiveness, Wasserstein distances in the analysis of time series and dynamical systems, The doubly graded matrix cone and Ferrers matrices, On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices, Polynomially solvable special cases of the quadratic bottleneck assignment problem, Monge properties of sequence alignment, Sequence Alignment Algorithms for Run-Length-Encoded Strings, The cone of Monge matrices: Extremal rays and applications, The multi-stripe travelling salesman problem, Monge properties, discrete convexity and applications, Open shop scheduling with synchronization, Estimation of Monge matrices, A multi-objective interpretation of optimal transport, Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems, Interval matrices with Monge property., A fast algorithm for approximating the detour of a polygonal chain., Sparse Monge matrices arising from scheduling problems, The fundamental theorem of linear programming: extensions and applications, Equally weighted cardinality constrained portfolio selection via factor models, Efficiently solvable cases of quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices, Dynamic discrete tomography, A sparse algorithm for dense optimal transport, Data aggregation for \(p\)-median problems, Allocation under a general substitution structure, Easy capacitated facility location problems, with connections to lot-sizing, A pricing problem under Monge property, Note on pseudolattices, lattices and submodular linear programs, Computing an eigenvector of a Monge matrix in max-plus algebra, Structure of the eigenspace of a Monge matrix in max-plus algebra, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, On almost Monge all scores matrices, Another well-solvable case of the QAP: maximizing the job completion time variance, Discrete optimization: an Austrian view, What the transportation problem did for me, The expressive power of binary submodular functions, Selected topics on assignment problems, A note on the parity assignment problem, Local search heuristics for the multidimensional assignment problem, The algebraic Monge property and path problems, Equivalent instances of the simple plant location problem, Minimizing a sum of submodular functions, Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability, The Northwest corner rule revisited, Unnamed Item, A Fast ℒ_p Spike Alignment Metric, Tropical totally positive matrices, Semi-local longest common subsequences in subquadratic time, Cooperative assignment games with the inverse Monge property, Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costs, An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra., Domain decomposition for entropy regularized optimal transport, Some aspects on solving transportation problem, Tropical planar networks, Scheduling with gaps: new models and algorithms, A fast bipartite network flow algorithm for selective assembly, Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems, Properties of the \(d\)-dimensional Earth mover's problem, Structure and dimension of the eigenspace of a concave Monge matrix, Traveling salesman games with the Monge property, Subclasses of solvable problems from classes of combinatorial optimization problems, Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem, The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases, The nucleon of cooperative games and an algorithm for matching games, Eigenvectors of interval matrices over max--plus algebra, Comparison and classification of linear systems over idempotent semirings inspired by total positivity, Weak Monge arrays in higher dimensions, Four-point conditions for the TSP: the complete complexity classification, Robotic-cell scheduling: special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices, A unified approach to simple special cases of extremal permutation problems, Monge strikes again: Optimal placement of web proxies in the internet, Unnamed Item, Well-solvable cases of the QAP with block-structured matrices, An asymmetric analog of van der Veen conditions and the traveling salesman problem. II, Fast distance multiplication of unit-Monge matrices, Resequencing a set of strings based on a target string, Minimization with respect to divergences and applications, Subtotally positive and Monge matrices

Cites Work