Linear and combinatorial optimization in ordered algebraic structures

Publication date: 1981

Published in: Annals of Discrete Mathematics (Search for Journal in Brave)

semigroups combinatorial optimization duality graph theory lattices semirings branch and bound method semimodules matroid theory relaxations independence systems algebraic optimization greedy method stability of matrices maximum spanning tree algebraic flow problems algebraic matching problems algebraic path problems ordered algebraic systems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Extremal problems in graph theory (05C35) Integer programming (90C10) Linear programming (90C05) Commutative semigroups (20M14) Deterministic network models in operations research (90B10) Enumeration in graph theory (05C30) Paths and cycles (05C38) Programming in abstract spaces (90C48) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Combinatorial aspects of matroids and geometric lattices (05B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Combinatorial aspects of packing and covering (05B40) Lattices (06B99) Ordered structures (06Fxx)

Related Items

Algebraic solutions of tropical optimization problems, Orbits in max--min algebra, Balancing problems in acyclic networks, Max-algebra: The linear algebra of combinatorics?, Equational theories of tropical semirings, A uniform synchronization problem over max-plus algebra, Linear and combinatorial sharing problems, Periodicity and critical circuits in a generalized max-algebra setting, Eigenspace structure of a max-drast fuzzy matrix, Min-max functions, Bases in max-algebra, Max-balanced flows in oriented matroids, Weighted automata and weighted logics with discounting, Strong linear independence in bottleneck algebra, Monotone eigenspace structure in max-min algebra, Extremal eigenproblem for bivalent matrices, Solvability and unique solvability of max-min fuzzy equations, Discrete-event dynamic systems: The strictly convex case, Powers of circulants in bottleneck algebra, An improved algorithm for finding the generators of the solution space for \(A\otimes \mathbf{x}\ge \mathbf{x} \), Computing matrix period in max--min algebra, Skew and infinitary formal power series, Discrete optimization in public rail transport, A generalization of the pentomino exclusion problem: dislocation of graphs, Matrices over semirings, Max-plus definite matrix closures and their eigenspaces, The Minkowski theorem for max-plus convex sets, Generators, extremals and bases of max cones, Identifying codes in some subgraphs of the square lattice, Algebraic approach to fasciagraphs and rotagraphs, Unique solvability of max-min fuzzy equations and strong regularity of matrices over fuzzy algebra, Maxpolynomial equations, On the solvability of interval max-min matrix equations, On invertible matrices over antirings, Perspectives of Monge properties in optimization, The spectra of irreducible matrices over completed idempotent semifields, Time depending shortest-path problems with applications to railway networks, The cardinality of bases in semilinear spaces over commutative semirings, The generators of the solution space for a system of inequalities, Inner products on semimodules over a commutative semiring., Invertible matrices and semilinear spaces over commutative semirings, On transformations of formal power series., On the \(\lambda \)-robustness of matrices over fuzzy algebra, Finding all essential terms of a characteristic maxpolynomial., Which matrices are immune against the transportation paradox?, Bases in semilinear spaces over zerosumfree semirings, Tropical linear-fractional programming and parametric mean payoff games, Universal solvability of interval max-plus matrix equations, Strong regularity of matrices in a discrete bottleneck algebra, Optimal cocircuits in regular matroids and applications, Minimization on submodular flows, Computing orbit period in max-min algebra, On spectral theory in discrete programming, Duality and separation theorems in idempotent semimodules., Inclines and incline matrices: A survey., Algorithms for approximate subtropical matrix factorization, On aperiodic and star-free formal power series in partially commuting variables, Minimax algebra and applications, A note on tropical linear and integer programs, The optimization problem over a distributive lattice, Linear matrix period in max-plus algebra, On nilpotent matrices over antirings, Moduloïds and pseudomodules. I: Dimension theory, On the generality of the greedy algorithm for solving matroid base problems, Linear independence in bottleneck algebras, Eigenspace structure of a max-prod fuzzy matrix, A polynomial algorithm for solving system of inequalities in max-plus algebra, Eigenvectors in Bottleneck algebra, Characterizations of max-balanced flows, Standard orthogonal vectors in semilinear spaces and their applications, Discrete optimization: an Austrian view, On generalized fuzzy matrices with periods, A preference-based approach to spanning trees and shortest paths problems, On nilpotent subsemigroups of the matrix semigroup over an antiring., Necessary solvability conditions of systems of linear extremal equations, On nilpotency of matrices over antirings, On nilpotency of generalized fuzzy matrices, Duality for balanced submodular flows, An incremental mechanical development of systolic solutions to the algebraic path problem, Solving a tropical optimization problem with application to optimal scheduling, Direct solution to constrained tropical optimization problems with application to project scheduling, A survey on fuzzy relational equations. I: Classification and solvability, Inequalities for the spectral radius of non-negative functions, An analogue of Hoffman's circulation conditions for max-balanced flows, Sufficient and necessary conditions for solution finding in valuation-based systems, An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra., On the powers of matrices in bottleneck/fuzzy algebra, Towards systolizing compilation, Structure and dimension of the eigenspace of a concave Monge matrix, An orthogonal systolic array for the algebraic path problem, The solvable conditions of linear system over commutative semirings, Matrix period in max-algebra, Simple image set of (max,+) linear mappings, An out-of-kilter method for the algebraic circulation problem, The Kleene-Schützenberger theorem for formal power series in partially commuting variables., Eigenfunctions and optimal orbits, Strong regularity of matrices -- a survey of results, Optimal control of a class of DEDS: Flow-shops with state-dependent processing times, Iterates of fuzzy circulant matrices, The equation \(A \otimes x = B \otimes y\) over \((\max,+)\), Orthogonal complements and extending orthogonal subsets of semimodules, The power algorithm in max algebra, On Eigenproblem for Circulant Matrices in Max-Algebra, Methods and applications of (max,+) linear algebra, Dioïds and semirings: Links to fuzzy sets and other applications, Tropicalizing the Simplex Algorithm, Flow symmetry and algebraic flows, Dynamic analysis of repetitive decision-free discrete-event processes: The algebra of timed marked graphs and algorithmic issues, Geometrical aspects of possibility measures on finite domain MV-clans, Eigenproblem for optimal-node matrices in max-plus algebra, Unnamed Item, The further study of semimodules over commutative semirings, Solution of a tropical optimization problem with linear constraints, Algorithms for non-linear and stochastic resource constrained shortest path, Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games, Semirings for social networks analysis, Weighted Automata and Weighted Logics with Discounting, Optimal \((0, 1)\)-matrix completion with majorization ordered objectives, Tropical Complementarity Problems and Nash Equilibria, Unnamed Item, Bases in semimodules over commutative semirings, Diagonability of matrices over commutative semirings, Solution sets of finite fuzzy relation equations with sup-inf composition over bounded Brouwerian lattices, On the job rotation problem, Computing an eigenvector of a Monge matrix in max-plus algebra, Structure of the eigenspace of a Monge matrix in max-plus algebra, Contributions to max-min convex geometry. I: Segments, Generalized matrix period in max-plus algebra, Bottleneck Capacity Expansion Problems with General Budget Constraints, Boolean Methods of Optimization over Independence Systems, A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Some optimization problems with extremal operations, Lattice properties in dioids, On strongly invertible matrices over semirings, The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields, The bideterminants of matrices over semirings, Free sets and free subsemimodules in a semimodule, Set Optimization—A Rather Short Introduction, Hierarchical Multiobjective Shortest Path Problems, The applications of the bideterminant of a matrix over commutative semirings, On Universal Shortest Paths, Eigenvectors of interval matrices over max--plus algebra, \(\ell\)-parametric eigenproblem in max-algebra, Ordered optimal solutions and parametric minimum cut problems, A multidimensional tropical optimization problem with a non-linear objective function and linear constraints, Powers of matrices over distributive lattices -- a review, Extension of free sets over commutative semirings, Unnamed Item, On abstract duality in mathematical programming