Discrete convex analysis
From MaRDI portal
Publication:1290668
DOI10.1007/BF02680565zbMATH Open0920.90103OpenAlexW4297069203MaRDI QIDQ1290668FDOQ1290668
Authors: Kazuo Murota 
Publication date: 3 June 1999
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02680565
Recommendations
Lagrange dualityconjugacyduality theoremssubmodular functionsdiscrete convex analysisdiscrete separation theorem
Cites Work
- Title not available (Why is that?)
- Convex Analysis
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimizing a Submodular Function on a Lattice
- Title not available (Why is that?)
- Submodular functions and optimization
- Generalized polymatroids and submodular flows
- ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- About strongly polynomial time algorithms for quadratic optimization over submodular constraints
- Title not available (Why is that?)
- A weighted matroid intersection algorithm
- Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
- The dependence graph for bases in matroids
- Valuated matroids
- Matroid Intersection
- Title not available (Why is that?)
- Convexity and Steinitz's exchange property
- Valuated matroids: A new look at the greedy algorithm
- Title not available (Why is that?)
- Greedoids
- A polynomial algorithm for an integer quadratic non-separable transportation problem
- Valuated Matroid Intersection I: Optimality Criteria
- Valuated Matroid Intersection II: Algorithms
- AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
- Finding optimal minors of valuated bimatroids
- Rewarding maps: On greedy optimization of set functions
- An Algorithm for Submodular Functions on Graphs
- Title not available (Why is that?)
- Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
- Solving integer minimum cost flows with separable convex cost objective polynomially
- Title not available (Why is that?)
- Sandwich theorems for set functions
- Submodular flow problem with a nonseparable cost function
- Title not available (Why is that?)
- On the subdifferential of a submodular function
- Fenchel-type duality for matroid valuations
- Minimization of an M-convex function
- Well-layered maps and the maximum-degree \(k \times k\)-subdeterminant of a matrix of rational functions
- Well-layered maps---a class of greedily optimizable set functions
- Title not available (Why is that?)
- Convexity and Steinitz's exchange property
Cited In (only showing first 100 items - show all)
- A new approach to two-location joint inventory and transshipment control via $L^{\text{natural}}$-convexity
- Extension of M-convexity and L-convexity to polyhedral convex functions
- Projection and convolution operations for integrally convex functions
- Applications of discrete convex analysis to mathematical economics
- Agreeable bets with multiple priors
- Submodular function minimization
- Discrete convexity and polynomial solvability in minimum 0-extension problems
- A discrete fixed point theorem and its applications.
- Dijkstra's algorithm and L-concave function maximization
- Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability
- Quasi M-convex and L-convex functions -- quasiconvexity in discrete optimization
- Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella.
- Scaling, proximity, and optimization of integrally convex functions
- A general two-sided matching market with discrete concave utility functions
- Theoretical and algorithmic results for a class of hierarchical fleet mix problems
- Cone superadditivity of discrete convex functions
- On equivalence of \(M^\natural\)-concavity of a set function and submodularity of its conjugate
- Quadratic M-convex and L-convex functions
- Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications
- Independence systems in gross-substitute valuations
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- Buyback problem with discrete concave valuation functions
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities.
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Application of M-convex submodular flow problem to mathematical economics
- Discrete convexity and unimodularity. I.
- A note on the implications of approximate submodularity in discrete optimization
- \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids
- Conjugacy relationship between M-convex and L-convex functions in continuous variables
- Convex analysis in \(\mathbb{Z}^n\) and applications to integer linear programming
- Discrete polymatroids
- Convex models of high dimensional discrete data
- Coordinatewise domain scaling algorithm for M-convex function minimization
- A capacity scaling algorithm for M-convex submodular flow
- A note on discrete convexity and local optimality
- Convex analysis and duality over discrete domains
- Pooling, pricing and trading of risks
- Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation
- Ideal hierarchical secret sharing schemes
- Discrete Convex Analysis
- Convex optimization on mixed domains
- Bisubmodular polyhedra, simplicial divisions, and discrete convexity
- Valuated matroid-based algorithm for submodular welfare problem
- A framework of discrete DC programming by discrete convex analysis
- Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions
- Discrete convexity and equilibria in economies with indivisible goods and money
- Optimization problems with cone constraints in groups and semigroups: an approach based on image space analysis
- Discrete convexity: Convexity for functions defined on discrete spaces
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- Title not available (Why is that?)
- Matroid rank functions and discrete concavity
- New algorithms for convex cost tension problem with application to computer vision
- A polynomial-time algorithm for a stable matching problem with linear valuations and bounded side payments
- New sufficient conditions for strong unimodality of multivariate discrete distributions
- Recent developments in discrete convex analysis
- The Lovász extension of market games
- Notes on L-/M-convex functions and the separation theorems
- Streaming submodular maximization under \(d\)-knapsack constraints
- On circuit valuation of matroids
- Decreasing minimization on M-convex sets: algorithms and applications
- Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
- A discrete convex min-max formula for box-TDI polyhedra
- 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
- Integrality of subgradients and biconjugates of integrally convex functions
- Coxeter submodular functions and deformations of Coxeter permutahedra
- Discrete convex functions on graphs and their algorithmic applications
- Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems
- Discrete convexity built on differences
- Intersection pairings for higher laminations
- Compression of \(\mathrm{M}^\natural\)-convex functions -- flag matroids and valuated permutohedra
- An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint
- Discrete midpoint convexity
- Matroid bases with cardinality constraints on the intersection
- Discrete Fenchel duality for a pair of integrally convex and separable convex functions
- Robust budget allocation via continuous submodular functions
- Directed discrete midpoint convexity
- Dynamic inventory control with payment delay and credit limit
- A tractable class of binary VCSPs via M-convex intersection
- Characterization and algorithm for bivariate multi-unit assignment valuations
- Substitutes and complements in network flows viewed as discrete convexity
- Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- Recent progress on integrally convex functions
- Theory of principal partitions revisited
- Technical note: Error noted in ``Order-based cost optimization in assemble-to-order systems by Lu and Song (2005)
- Fair integral submodular flows
- Preservation of structural properties in optimization with decisions truncated by random variables and its applications
- Multi-attribute based influence maximization in social networks: algorithms and analysis
- On basic operations related to network induction of discrete convex functions
- The secretary problem with multiple job vacancies and batch candidate arrivals
- Approximate sampling and counting of graphs with near-regular degree intervals
- A trust-region framework for derivative-free mixed-integer optimization
- Shapley-Folkman-type theorem for integrally convex sets
- Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
- Strategyproof allocation mechanisms with endowments and M-convex distributional constraints
- Convex and quasiconvex functions in metric graphs
- MAP inference algorithms without approximation for collective graphical models on path graphs via discrete difference of convex algorithm
- A fair and truthful mechanism with limited subsidy
This page was built for publication: Discrete convex analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1290668)
