Convexity and Steinitz's exchange property
From MaRDI portal
Publication:677484
DOI10.1006/aima.1996.0084zbMath0867.90092OpenAlexW2035186046MaRDI QIDQ677484
Publication date: 28 May 1997
Published in: Advances in Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/aima.1996.0084
convex analysissubmodular functionsweighted matroid intersectiondiscrete separation theoremsFrenchel-type min-max theoreminteger lattice points
Convex programming (90C25) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items
Convexity and Steinitz's exchange property, Quadratic M-convex and L-convex functions, Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems, PARAMETRIC POLYMATROID OPTIMIZATION AND ITS GEOMETRIC APPLICATIONS, Convex analysis and duality over discrete domains, M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System, 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, Characterizing and recognizing generalized polymatroids, Identifying combinatorial valuations from aggregate demand, Strategyproof allocation mechanisms with endowments and M-convex distributional constraints, On the Construction of Substitutes, The geometry of geometries: matroid theory, old and new, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint, Characterization and algorithm for bivariate multi-unit assignment valuations, Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids, Characterizations of the set of integer points in an integral bisubmodular polyhedron, The quadratic M-convexity testing problem, A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs, Gross substitution, discrete convexity, and submodularity, Quasi M-convex and L-convex functions -- quasiconvexity in discrete optimization, New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities., Optimization problems with cone constraints in groups and semigroups: an approach based on image space analysis, 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., DISCRETE CONCAVITY FOR POTENTIAL GAMES, Discrete convexity built on differences, Application of M-convex submodular flow problem to mathematical economics, A polynomial-time algorithm for a stable matching problem with linear valuations and bounded side payments, Simpler exchange axioms for M-concave functions on generalized polymatroids, Time bounds for iterative auctions: a unified approach by discrete convex analysis, Buyback problem with discrete concave valuation functions, On circuit valuation of matroids, Discrete convexity and unimodularity. I., Conjugacy relationship between M-convex and L-convex functions in continuous variables, \(M\)-convex functions and tree metrics, Discrete convexity and equilibria in economies with indivisible goods and money, Applications of discrete convex analysis to mathematical economics, A general two-sided matching market with discrete concave utility functions, Coordinatewise domain scaling algorithm for M-convex function minimization, A note on discrete convexity and local optimality, A capacity scaling algorithm for M-convex submodular flow, Cone superadditivity of discrete convex functions, Subdivisions of integral base polytopes, Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella., Congestion games viewed from M-convexity, Submodular function minimization, Induction of M-convex functions by linking systems, Computing Walrasian equilibria: fast algorithms and structural properties, Even factors, jump systems, and discrete convexity, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function, Convex Analysis in $\mathbb{Z}^n$ and Applications to Integer Linear Programming, A Tractable Class of Binary VCSPs via M-Convex Intersection, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Matroidal Choice Functions, Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2, Fenchel-type duality for matroid valuations, Discrete convex analysis, \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, A survey of fundamental operations on discrete convex functions of various kinds, On basic operations related to network induction of discrete convex functions, Extension of M-convexity and L-convexity to polyhedral convex functions, On the Lattice Structure of Stable Allocations in a Two-Sided Discrete-Concave Market, Substitutes and complements in network flows viewed as discrete convexity, Discrete polymatroids
