Recent Developments in Discrete Convex Analysis

DOI10.1007/978-3-540-76796-1_11zbMath1359.05020OpenAlexW50901504MaRDI QIDQ2971611

Kazuo Murota

Publication date: 7 April 2017

Published in: Research Trends in Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-76796-1_11

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Other problems of combinatorial convexity (52A37)

Related Items

Least-squares estimation of a convex discrete distribution, An overview of structural systems theory, Discrete Fenchel duality for a pair of integrally convex and separable convex functions, A parametric propagator for pairs of \textsc{Sum} constraints with a discrete convexity property, Discrete convexity in joint winner property, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection., Scaling, proximity, and optimization of integrally convex functions, Recent progress on integrally convex functions, Capacity Games with Supply Function Competition, Discrete Midpoint Convexity, Continuous Relaxation for Discrete DC Programming, Total positivity in multivariate extremes, The quadratic M-convexity testing problem, 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., Monotone optimal control for a class of Markov decision processes, Projection and convolution operations for integrally convex functions, Antimatroids induced by matchings, Stiefel tropical linear spaces, Valuated matroid-based algorithm for submodular welfare problem, A framework of discrete DC programming by discrete convex analysis, A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions, Continuous relaxation for discrete DC programming, Buyback problem with discrete concave valuation functions, Some specially structured assemble-to-order systems, Discrete Convex Functions on Graphs and Their Algorithmic Applications, The Finite Matroid-Based Valuation Conjecture is False, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, Preservation of Structural Properties in Optimization with Decisions Truncated by Random Variables and Its Applications, Multiple Exchange Property for M^♮-Concave Functions and Valuated Matroids, A Tractable Class of Binary VCSPs via M-Convex Intersection, Convex and quasiconvex functions in metric graphs, A survey of fundamental operations on discrete convex functions of various kinds, On basic operations related to network induction of discrete convex functions, On the Lattice Structure of Stable Allocations in a Two-Sided Discrete-Concave Market, Bisubmodular polyhedra, simplicial divisions, and discrete convexity, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases, Note on the polyhedral description of the Minkowski sum of two L-convex sets, Coordinating Inventory Control and Pricing Strategies for Perishable Products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• The Buneman index via polyhedral split decomposition
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Valuated matroids: A new look at the greedy algorithm
• Submodular function minimization
• Induction of M-convex functions by linking systems
• New algorithms for convex cost tension problem with application to computer vision
• Submodular flow problem with a nonseparable cost function
• Matroid matching and some applications
• A canonical decomposition theory for metrics on a finite set
• Valuated matroids
• Stable bundles, representation theory and Hermitian operators
• Fenchel-type duality for matroid valuations
• Discrete convex analysis
• Dirichlet forms and symmetric Markov processes
• Submodular functions and electrical networks
• A discrete fixed point theorem and its applications.
• A labor market with heterogeneous firms and workers
• Discrete-event control of stochastic networks: multimodularity and regularity.
• Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
• A note on maximizing a submodular set function subject to a knapsack constraint
• Notes on L-/M-convex functions and the separation theorems
• Conjugacy relationship between M-convex and L-convex functions in continuous variables
• \(M\)-convex functions and tree metrics
• Applications of discrete convex analysis to mathematical economics
• Coordinatewise domain scaling algorithm for M-convex function minimization
• A capacity scaling algorithm for M-convex submodular flow
• Concave cocirculations in a triangular grid
• Extension of M-convexity and L-convexity to polyhedral convex functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Proximity theorems of discrete convex functions
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• \(T\)-theory: An overview
• Stable matching in a common generalization of the marriage and assignment models
• Solving discrete zero point problems
• A geometric study of the split decomposition
• Combinatorial auctions with decreasing marginal utilities
• Even factors, jump systems, and discrete convexity
• The assignment game. I: The core
• Submodular functions and optimization.
• Discrete fixed point theorem reconsidered
• M-Convex Function on Generalized Polymatroid
• Multimodularity, Convexity, and Optimization Properties
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• On the Structure of Lost-Sales Inventory Models
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• A Simplicial Approach for Discrete Fixed Point Theorems
• ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
• Tropical Linear Spaces
• Extremal Splittings of Point Processes
• Complexity of Matroid Property Algorithms
• A weighted matroid intersection algorithm
• An analysis of approximations for maximizing submodular set functions—I
• Discrete Convex Analysis
• The honeycomb model of 𝐺𝐿_{𝑛}(ℂ) tensor products II: Puzzles determine facets of the Littlewood-Richardson cone
• On Steepest Descent Algorithms for Discrete Convex Functions
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• An Algorithm for Submodular Functions on Graphs
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
• The tropical Grassmannian
• Eigenvalues, invariant factors, highest weights, and Schubert calculus
• A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Operations on M‐Convex Functions on Jump Systems
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Convex Analysis
• On Minimizing Nonseparable Functions Defined on the Integers with an Inventory Application
• A Fixed-Point Approach to Stable Matchings and Some Applications
• Note on Multimodularity and L-Convexity
• Theory of Matroids
• College Admissions and the Stability of Marriage
• Geometry of cuts and metrics
• Matrices and matroids for systems analysis
• Combinatorial optimization. Theory and algorithms.
• On circuit valuation of matroids