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 (39)

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

This page was built for publication: Recent Developments in Discrete Convex Analysis