Valuated matroids: A new look at the greedy algorithm
From MaRDI portal
Publication:913805
DOI10.1016/0893-9659(90)90009-ZzbMath0701.05014OpenAlexW2094571546MaRDI QIDQ913805
Walter Wenzel, Andreas W. M. Dress
Publication date: 1990
Published in: Applied Mathematics Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0893-9659(90)90009-z
Related Items
Convexity and Steinitz's exchange property, Gérard-Levelt membranes, Well-layered maps and the maximum-degree \(k \times k\)-subdeterminant of a matrix of rational functions, Finding optimal minors of valuated bimatroids, Well-layered maps---a class of greedily optimizable set functions, Pfaffian forms and \(\Delta\)-matroids with coefficients, Note on exchange axioms for valuated matroids and valuated delta-matroids, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, Two algorithms for valuated \(\Delta\)-matroids, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection., A constructive proof for the induction of M-convex functions through networks, Shortest bibranchings and valuated matroid intersection, Gross substitutability: an algorithmic survey, Minimization of an M-convex function, On the Construction of Substitutes, Uniform semimodular lattices and valuated matroids, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, The quadratic M-convexity testing problem, A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs, New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities., Recent Developments in Discrete Convex Analysis, A proof of Cunningham's conjecture on restricted subgraphs and jump systems, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., A `non-additive' characterization of \(\wp\)-adic norms., Projective equivalence of matroids with coefficients, Valuated matroid-based algorithm for submodular welfare problem, Perfect matroids, A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions, A greedy-algorithm characterization of valuated \(\Delta\)-matroids, A Grassmann algebra for matroids, Valuated matroids, Buyback problem with discrete concave valuation functions, Legendre duality in combinatorial study of matrix pencils, On circuit valuation of matroids, Coordinatewise domain scaling algorithm for M-convex function minimization, Congestion games viewed from M-convexity, Induction of M-convex functions by linking systems, Computing Walrasian equilibria: fast algorithms and structural properties, The Finite Matroid-Based Valuation Conjecture is False, Pfaffian forms and \(\Delta\)-matroids, Even factors, jump systems, and discrete convexity, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, A disturbed version of the greedy algorithm, Multiple Exchange Property for M♮-Concave Functions and Valuated Matroids, A Tractable Class of Binary VCSPs via M-Convex Intersection, The geometry of gaussoids, Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings, Matroidal Choice Functions, Fenchel-type duality for matroid valuations, Discrete convex analysis, Two-best solutions under distance constraints: The model and exemplary results for matroids, \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids, A survey of fundamental operations on discrete convex functions of various kinds, Extension of M-convexity and L-convexity to polyhedral convex functions, Discrete 2-convex functions, Computing valuations of the Dieudonné determinants, \(\Delta\)-matroids with the strong exchange conditions
Cites Work
